[BZOJ1852] [MexicoOI06]最长不下降序列(贪心)

考虑如下贪心

（我将问题反过来考虑，也就是要满足Ai>maxj=1j<iBj）

首先对于读入的(A,B)，按照B的值递增排序

(选出的答案序列不一定是其中一个有序的子序列)

答案序列存在若干个B递增的位置，设它们是{ai},ai−1<ai

合法的递增序列需要满足的限制是Aai>Bai−1

考虑剩下的部分即j∈[ai−1+1,ai−1]，那么这些点放在ai后面一定是最优的(因为此时不会改变最大的B)，此时限制它们的B就是Bai

即这一部分中满足Aj>Bai的j均可以选出来

为了便于表示，设C(l,r)=|{i|i∈[l,r],Ai>Br+1}|，可以通过一个主席树维护

定义dpi表示当前以i为最大的B的答案，特别的，dp0表示序列为空A0=B0=−∞

枚举每个i进行转移

朴素的转移就是可以枚举上一个位置j，O(n2)转移

需要找到前面第一个能把i接上去的j即可，即第一个Br<Ai(j≥0)的位置，那么合法的决策位置就是[0,r]

则dpi=max0r{dpj+1+C(j+1,i−1)}

设最优决策点为k∈[0,r]，影响最优决策点位置的有两个方面

从[j+1,i−1]这一段点考虑，j越小时，就会有越多的点对被Bi限制，也就是说j越大，对于中间这一段来说越优

但是从dpj的角度考虑，并不是j越大越好，因为可能存在一个Aj特别小限制了前面递增点列的选择

推论：如果前面存在一个Aj>Bi，那么k≥j

事实上应该说成dpj+C(j+1,i−1)≥∀d∈[0,j−1],dpd+C(d+1,i−1)

综合上面两条来看，如果Aj>Bi意味着把它放进递增序列里绝对是优的，因为不会对前面的点产生不良限制

消除了不良限制之后，就满足最优性了

所以发现最优决策点的范围缩小到了[l=max{k|Ak>Bi},r]

发现决策范围内的C(l+1,i−1)=C(l+2,i−1)=⋯=C(r+1,i−1)

所以dpi=maxlr{dpj}+C(r+1,i−1)=max0r{dpj}+C(r+1,i−1)

所以可以直接维护一个前缀最大值，每次二分找到那个r，求出C(r+1,i−1)即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
const int N=2e5+10,K=15;
 
int n;
 
struct Node{
    int a,b;
    bool operator < (const Node __) const {
        return b<__.b;
    }
}A[N];
int h[N],hc;
int dp[N];
 
int rt[N*K],s[N*K],ls[N*K],rs[N*K],cnt;
void Add(int p,int pre,int l,int r,int x) {
    s[p]=s[pre]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    ls[p]=ls[pre],rs[p]=rs[pre];
    x<=mid?Add(ls[p]=++cnt,ls[pre],l,mid,x):Add(rs[p]=++cnt,rs[pre],mid+1,r,x);
}
 
int Que(int pl,int pr,int l,int r,int ql,int qr) {
    if(ql>qr) return 0;
    if(ql==l&&qr==r) return s[pr]-s[pl];
    int mid=(l+r)>>1;
    if(qr<=mid) return Que(ls[pl],ls[pr],l,mid,ql,qr);
    else if(ql>mid) return Que(rs[pl],rs[pr],mid+1,r,ql,qr);
    else return Que(ls[pl],ls[pr],l,mid,ql,mid)+Que(rs[pl],rs[pr],mid+1,r,mid+1,qr);
}
 
int main(){
    rep(i,1,n=rd()) {
        A[i].a=rd(),A[i].b=rd();
        h[++hc]=A[i].a,h[++hc]=A[i].b;
    }
    sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
    sort(A+1,A+n+1);
    rep(i,1,n) {
        A[i].a=lower_bound(h+1,h+hc+1,A[i].a)-h;
        A[i].b=lower_bound(h+1,h+hc+1,A[i].b)-h;
        Add(rt[i]=++cnt,rt[i-1],1,hc,A[i].a);
    }
    rep(i,1,n) {
        int l=1,r=i-1,res=0;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(A[mid].b<A[i].a) l=mid+1,res=mid;
            else r=mid-1;
        }
        dp[i]=max(dp[i-1],dp[res]+1+Que(rt[res],rt[i-1],1,hc,A[i].b+1,hc));
    }
    int ans=dp[n];
    printf("%d\n",ans);
}

附：离线做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) f|=(IO=='-');
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,K=15;

int n;
struct Node{
	int a,b;
	bool operator < (const Node __)const{ return b<__.b; }
}A[N];
struct Query{
	int x,p,id,k;
	bool operator < (const Query __)const{ return p<__.p; }
}Q[N<<1];

int qc,h[N],hc,dp[N];
int L[N],Ans[N];

int s[N];
void Add(int p,int x){ while(p) s[p]+=x,p-=p&-p; }
int Que(int p){
	int res=0;
	while(p<=hc) res+=s[p],p+=p&-p;
	return res;
}

int main(){
	rep(i,1,n=rd()) {
		A[i].a=rd(),A[i].b=rd();
		h[++hc]=A[i].a,h[++hc]=A[i].b;
	}
	sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
	sort(A+1,A+n+1);
	rep(i,1,n) {
		A[i].a=lower_bound(h+1,h+hc+1,A[i].a)-h;
		A[i].b=lower_bound(h+1,h+hc+1,A[i].b)-h;
	}
	rep(i,1,n) {
		int l=1,r=i-1,res=0;
		while(l<=r) {
			int mid=(l+r)>>1;
			if(A[mid].b<A[i].a) l=mid+1,res=mid;
			else r=mid-1;
		}
		L[i]=res;
		if(i-1>L[i]) Q[++qc]=(Query){A[i].b+1,i-1,i,1},Q[++qc]=(Query){A[i].b+1,L[i],i,-1};
	}
	sort(Q+1,Q+qc+1);
	int p=1;
	rep(i,0,n) {
		if(i) Add(A[i].a,1);
		while(p<=qc && Q[p].p<=i) Ans[Q[p].id]+=Q[p].k*Que(Q[p].x),p++;
	}
	rep(i,1,n) dp[i]=max(dp[i-1],dp[L[i]]+1+Ans[i]);
	int ans=dp[n];
	printf("%d\n",ans);
}