[BZOJ1852] [MexicoOI06]最长不下降序列

额我也不知道是不是水过去的。。。和网上的另一篇题解对拍过了，但是拍不出来。。。

经过和神仙的讨论基本可以确定是对的了

考虑如下贪心

（我将问题反过来考虑，也就是要满足\(A_i > \max_{j=1}^{j < i}{B_j}\)）

按照\(b\)的值排序后，对于每一个\(i\)记录最大的\(B\)是\(B_i\)的最优解\(Max_i\)(注意这个其实是累过前缀和的)

接下来考虑每个\(i\)，我们强制它产生贡献，找到前面最后一个\(B_j<A_i\)，接在\(Max_j\)后面

由于这样做会跳过中间这一段，但事实上它们可能会产生贡献，所以我考虑将它们接在\(i\)的后面能否成立

也就是求\(\left| \lbrace A_k>B_i,{k \in [j+1,i-1]} \rbrace \right|\)，这个我们可以离散+主席树在线搞定，或者可以离线

如此得到答案\(Max_n\) (在代码里就是\(dp\)数组。。)

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<iostream>

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)

inline void cmax(int &a,int b){ ((a<b)&&(a=b));}

inline void cmin(int &a,int b){ ((a>b)&&(a=b));}

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;

const int R=1e5;

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);

}

离线做法

#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);

}