題目大意：。。。不是很好敘述自己看吧。注意要剪掉初始就能到達所有終點的點的數量
OTZ 這做法實在是太優雅了！
#include#include #include #include #define M 100100 using namespace std; struct abcd{ int pos,val; abcd() {} abcd(int _,int __): pos(_),val(__) {} }a1[M],a2[M]; int tot1,tot2; int n,m,p,k,ans; int l[M],r[M]; bool Compare1(const abcd &x,const abcd &y) { if( x.pos != y.pos ) return x.pos < y.pos ; return x.val < y.val ; } bool Compare2(const abcd &x,const abcd &y) { if( x.pos != y.pos ) return x.pos > y.pos ; return x.val < y.val ; } struct BIT{ int c[M]; void Update(int x,int y) { for(;x;x-=x&-x) c[x]=max(c[x],y); } int Get_Ans(int x) { int re=0; for(;x<=m;x+=x&-x) re=max(re,c[x]); return re; } }b1,b2; int main() { int i,j,x,y,z; cin>>n>>m>>p>>k;++m; for(i=1;i<=p;i++) { scanf(%d%d%d,&x,&y,&z);++y; if(z) new (&a1[++tot1])abcd(x+1,y); else new (&a2[++tot2])abcd(x,y); } sort(a1+1,a1+tot1+1,Compare1); sort(a2+1,a2+tot2+1,Compare2); l[0]=r[n+1]=-1; for(j=1,i=1;i<=n;i++) { l[i]=l[i-1]+1; for(;j<=tot1&&a1[j].pos==i;j++) { int temp=b1.Get_Ans(a1[j].val)+1; l[i]=min(l[i],(i-1)-temp); b1.Update(a1[j].val,temp); } } for(j=1,i=n;i;i--) { r[i]=r[i+1]+1; for(;j<=tot2&&a2[j].pos==i;j++) { int temp=b2.Get_Ans(a2[j].val)+1; r[i]=min(r[i],(n-i)-temp); b2.Update(a2[j].val,temp); } } for(j=1,i=1;i<=n;i++) { for(;i-j+1&&l[i]+r[j]>k;j++); ans=max(ans,i-j+1); } for(i=1;i<=n;i++) if(!l[i]&&!r[i]) --ans; cout<
