[POI2007]驾驶考试egz

题目

BZOJ
神仙题，可比那些氵紫题有意思多了

做法

(i)能作为起始点，当(i)能到达(1)~(i-1)和(i+1)~(n)
这样处理显然会麻烦，因为要从每个点都特判一次
所以我们转换条件，当且仅当(i)能到达(1)和(n)

这样虽然判断次数少了，但是仍然要每个点跑一遍

转换问题：连反向边，则当且仅当(1)和(n)能到达(i)，由于单调性，跑的次数为常数级别
考虑增加边，(i)能到达(1)，转换为且单调序列的补集

显然，向左向右的补集有单调性，扫一遍就好了

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=1e6+9;
LL n,ans,m,p,k;
LL tree[maxn],L[maxn],R[maxn];
inline LL Lowbit(LL x){ return x&-x; }
inline void Modify(LL x,LL val){ for(;x<=m;x+=Lowbit(x)) tree[x]=max(tree[x],val); }
inline LL Qmx(LL x){ LL ret(0); for(;x;x-=Lowbit(x)) ret=max(ret,tree[x]); return ret; }

struct node{
	LL to,nxt,val;
}Ldis[maxn],Rdis[maxn];
LL Lnum,Rnum;
LL Lhead[maxn],Rhead[maxn];
inline void RI(LL u,LL v){
	Rdis[++Rnum]=(node){v,Rhead[u],0}; Rhead[u]=Rnum;
}
inline void LI(LL u,LL v){
	Ldis[++Lnum]=(node){v,Lhead[u],0}; Lhead[u]=Lnum;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&p,&k); ++m;
	for(LL i=1;i<=p;++i){
		LL x,y,op; scanf("%d%d%d",&x,&y,&op);
		y=m-y;
		if(!op) RI(x,y);
		else LI(x+1,y);
	}
	for(LL i=2;i<=n;++i){
		for(LL j=Lhead[i];j;j=Ldis[j].nxt) L[i]=max(L[i],Ldis[j].val=Qmx(Ldis[j].to)+1);
		for(LL j=Lhead[i];j;j=Ldis[j].nxt) Modify(Ldis[j].to,Ldis[j].val);
		L[i+1]=L[i]; L[i]=i-1-L[i];
	}
	memset(tree,0,sizeof(tree));
	for(LL i=n-1;i>=1;--i){
		for(LL j=Rhead[i];j;j=Rdis[j].nxt) R[i]=max(R[i],Rdis[j].val=Qmx(Rdis[j].to)+1);
		for(LL j=Rhead[i];j;j=Rdis[j].nxt) Modify(Rdis[j].to,Rdis[j].val);
		R[i-1]=R[i]; R[i]=n-i-R[i];
	}
	LL r=1,free(0);
	for(LL l=1;l<=n;++l){
	    while(r<=n && L[r]+R[l]<=k) ++r;
		ans=max(ans,r-l);
		if(!L[l] && !R[l]) ++free;
	}
	printf("%d
",ans-free);
	return 0;
}