https://www.luogu.org/PRoblem/show?pid=2894#sub 這道題第一天我覺得賊難，感覺很復雜； 第二天看便有了思路，但覺得寫起來不簡單； 第三天發現，只不過是線段樹里面多維護了幾個東西罷了； 以后的練習，估計線段樹不再僅僅是維護一下數值就好了；
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#define Ll long longusing namespace std;struct tree{ int xx,yy,l,r,m,p;//xx，yy是這個區間的范圍，l,r代表這段區間的左右最長連續空位，m就是整段區間的連續空位，p是lazy標記 }T[500000*8+1];int n,m,x,y,z,ans;void clean(int num){//這個顯然就是lazy的下傳 if(T[num].xx==T[num].yy)return; if(!T[num].p)return; int k=num+num; if(T[num].p==1){ T[k].l=T[k].m=T[k].r=T[k+1].l=T[k+1].m=T[k+1].r=0; T[k].p=T[k+1].p=1; }else{ T[k].l=T[k].m=T[k].r=T[k].yy-T[k].xx+1; T[k+1].l=T[k+1].m=T[k+1].r=T[k+1].yy-T[k+1].xx+1; T[k].p=T[k+1].p=2; } T[num].p=0;}void maketree(int x,int y,int num){ T[num].xx=x;T[num].yy=y; T[num].l=T[num].r=T[num].m=y-x+1;//一開始全空房 if(x==y)return; int mid=(x+y)>>1;num=num<<1; maketree(x,mid ,num ); maketree(mid+1,y,num+1);}int find(int x,int num){//找一個長度位x的區間，現搜索到第num個區間 clean(num);clean(num*2);clean(num*2+1); if(T[num].l>=x)return T[num].xx;//如果這個區間的左連續區間足夠，那么直接住在最左邊吧 if(T[num*2].m>=x)return find(x,num*2);//如果左半段區間的最大值滿足x，說明可以住在左子兒子的區間 if(T[num*2].r+T[num*2+1].l>=x)return T[num*2].yy-T[num*2].r+1;//這時判斷中間的一塊區域 return find(x,num*2+1); //因為一定可以找到區間，但前面都找不到，那只可能在右半段的區間里了 }void gaoji(int num){//ohly~ohlyohlyohly~~ wearethegay~~~wearethegay~~~~~~~~隨便取的函數命 int k=num<<1; clean(k);clean(k+1); T[num].l=T[k ].l;//顯然大區間的l是左小區間的l，但是如果左小區間全空，顯然大區間的l要加上右小區間的l if(T[k ].l==T[k ].yy-T[k ].xx+1)T[num].l+=T[k+1].l; T[num].r=T[k+1].r;//同理 if(T[k+1].r==T[k+1].yy-T[k+1].xx+1)T[num].r+=T[k ].r; T[num].m=max(T[k].m,T[k+1].m);//這個很顯然啊 T[num].m=max(T[num].m,T[k].r+T[k+1].l);}void dec(int x,int y,int num){//這些和基本線段樹差不多 clean(num); if(x<=T[num].xx&&T[num].yy<=y){T[num].l=T[num].r=T[num].m=0;T[num].p=1;return;} num=num<<1; if(x<=T[num ].yy)dec(x,y,num ); if(y>=T[num+1].xx)dec(x,y,num+1); gaoji(num/2);}void pluss(int x,int y,int num){ clean(num); if(x<=T[num].xx&&T[num].yy<=y){T[num].l=T[num].r=T[num].m=T[num].yy-T[num].xx+1;T[num].p=2;return;} num=num<<1; if(x<=T[num ].yy)pluss(x,y,num ); if(y>=T[num+1].xx)pluss(x,y,num+1); gaoji(num/2);}int main(){ scanf("%d%d",&n,&m); maketree(1,n,1); while(m--){ scanf("%d",&x); if(x==1){ scanf("%d",&x); if(T[1].m<x){printf("0/n");continue;}//T[1].m是整個區間中的最大連續空位，這個判斷顯然成立 ans=find(x,1);//通過了上面一個判斷，一定可以找出答案 printf("%d/n",ans); dec(ans,ans+x-1,1);//把新住進來的房間重置 }else{ scanf("%d%d",&x,&y); pluss(x,x+y-1,1);//把新走出去的房間重置 } }}新聞熱點
疑難解答
