[POI2007]驾驶考试egz

题目

BZOJ

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

做法

\(i\)能作为起始点，当\(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\n",ans-free);

	return 0;

}