제목.

제목의 대의.

0101 서열이 있습니다.구간 한 무더기를 드리겠습니다. 구간마다 111시가 있습니다.가장 많이 물어본 11시 개수.

사고 과정

이 문제는 아주 고전적인 것 같아서 어디서 본 것 같기도 하고 본 적이 없는 것 같기도 하다.처음에는 욕심 쪽으로 생각했는데...생각이 안 났어요...나중에 DP를 생각해도 생각이 안 났어요...WHH 할아버지가 달려와서 흥분해서'차별 제약 아닙니까!그래서 나는 멘탈이 붕괴되어 문제를 풀러 갔는데......그런데 찾은 것은 모두 DP였다......DP의 방법을 이해했다. 이해는 했지만 극도로 서투르다......그런데 이 문제는 코드 능력에 대한 시련이 매우 강하다......나는 스스로 극도로 징그러운 방법을 내놓으려고 했지만 나중에 문제풀이(그리고) 절차를 자세히 보았다.거의 마크에 맞았어.. 멘탈이 붕괴됐어..

정해

DP부터 말해.fi f 설정ifi는 ii를 가장 많이 선택한 11점 수를 나타낸다.방정식은 f i = max ⁡ f j + 1 fi=\max f_j+1fi=maxfj+1이것은 사람의 분석 능력을 매우 시험한다. 두 가지 측면에서 고려하면.

유일성: ii를 포함한 모든 구간에서 다른 것을 선택할 수 없습니다.이렇게 하면 오른쪽 경계를 구할 수 있어요. R i R.ii, ii를 포함하는 구간의 최소 왼쪽 경계 - 1 - 1 - 1 - 1.

필요성: ii를 포함하지 않는 모든 구간(ii 이전) 중 하나를 선택해야 합니다.이렇게 하면 오른쪽 경계 L i L 을 구할 수 있습니다.i i i i가 포함되지 않은 구간의 최대 왼쪽 경계

이렇게 L i Li Li 및 R i R이리야, 옮길 수 있어.코드의 완벽을 애써 추구하지 않는다면 사실 이럴 때 라인 트리로 이동을 보조하면 된다. 간단하고 거칠다(시합이라면 나는 틀림없이 이렇게 칠 것이다).하지만 실제로는 최적화할 수 있다.먼저 L L L 과 R R R R 은 모두 점증한다는 결론을 입증할 수 있다.만약 L i -3 1 > L i L{i-1}>L_i Li -3 1 > Li, i i가 포함된 구간에도 i -3 1 i-1 i -3 1(구간 왼쪽 경계가 i i i가 아닌 한 L i -3 ≤ L i L{i-1}\leq L i Li -3 ≤ Li), L i -3 1 L{i-1} Li -3 1은 i -3 1 i-1 i -3 1구간을 포함하는 최소 왼쪽 경계 -1 -3 1이므로 L i -3 1 L{i-1} Li -3 1은 업데이트될 수 있으므로 구성되지 않습니다.만약 R i -3 1 > R i R{i-1}>R_i Ri -3 1>Ri, i -3 1 i-1 i -3 1이 포함되지 않은 구간에 i i i, R i Ri Ri는 i i i 구간을 포함하지 않는 최대 오른쪽 경계이기 때문에 R i RiRi는 업데이트될 수 있기 때문에 설립되지 않습니다.
기왕 점차적으로 증가한 이상 즐겁게 단조로운 대기열 DP를 만들 수 있다......여러 가지 단조로운 성질이 생겼고 코드도 훨씬 간단할 수 있다. 라인 트리를 치거나 쌓을 필요도 없다. 그러나......시합이라면 이런 시간을 라인 트리를 치는 것이 낫다.
또 다른 방법은 차분 구속이다.만약에 우리가 접두사와 구간 [l,r][l,r][l,r]를 한 번 한다면 sl+1=srs 가 있을 것이다l+1=s_rsl+1=sr, sl+1≥srsl+1\geq s_rsl+1≥sr 및 sr-3-1≥slsr-1\geq s_l sr​−1≥sl​.그리고 각 좌우 단점을 xi x 로 정렬합니다ixi, 그럼 xi-3-1≤xix{i-1}\leq x_ixi-4-1≤xi차분 구속하면 돼...물론 난 안 해봤으니까 순전히 삐걱삐걱...

코드

using namespace std;
#include 
#include 
#include 
#define N 200010
int n,m;
struct Section{
	int l,r;
} s[N];
inline bool cmps(const Section &a,const Section &b){
	return a.l<b.l || a.l==b.l && a.r<b.r;
}
int L[N],R[N];
int q[N],head,tail;
int f[N];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n+1;++i)
		R[i]=i-1;
	for (int i=1;i<=m;++i){
		scanf("%d%d",&s[i].l,&s[i].r);
		L[s[i].r+1]=max(L[s[i].r+1],s[i].l);
		R[s[i].r]=min(R[s[i].r],s[i].l-1);
	}
	for (int i=n;i>=1;--i)
		R[i]=min(R[i],R[i+1]);
	for (int i=2;i<=n+1;++i)
		L[i]=max(L[i],L[i-1]);
	memset(f,127,sizeof f);
	f[0]=0;
	for (int i=1,j=0;i<=n+1;++i){
		for (;j<=R[i];++j){
			if (f[j]==0x7f7f7f7f)
				continue;
			while (head<=tail && f[q[tail]]<f[j])
				tail--;
			q[++tail]=j;
		}
		while (head<=tail && q[head]<L[i])
			head++;
		if (head<=tail)
			f[i]=f[q[head]]+1;
	}
	if (f[n+1]==0x7f7f7f7f)
		printf("-1
");
	else
		printf("%d
",f[n+1]-1);
	return 0;
}

총결산

정말 단조로운 대열의 좋은 문제다.물론 시합이라면 나는 틀림없이 라인 트리를 선택할 것이다.