我好蒻啊 题题看题解
线段树维护从左端点开始的最长连续空房、右端点结束的最长连续空房、整段区间的最长连续空房、区间非空房的个数。
http://blog.csdn.net/qq_39553725/article/details/77604572 此处题解。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<iostream> #include<cctype> #define left (rt<<1) #define right (rt<<1|1) #define mid ((l+r)>>1) #define lson l,mid,left #define rson mid+1,r,right #define root 1,n,1 #define len (r-l+1) inline long long max(long long a,long long b){ return a>b?a:b; } inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int tag[1000010]; struct Node{ int linel,liner,linem,sum; }tree[1000010]; inline void pushup(int rt,int m){ tree[rt].linel=tree[left].sum?tree[left].linel:(m-(m>>1))+tree[right].linel; tree[rt].liner=tree[right].sum?tree[right].liner:(m>>1)+tree[left].liner; tree[rt].sum=tree[left].sum+tree[right].sum; tree[rt].linem=max(tree[rt].linel,tree[rt].liner); tree[rt].linem=max(tree[rt].linem,tree[left].liner+tree[right].linel); tree[rt].linem=max(tree[rt].linem,max(tree[left].linem,tree[right].linem)); } inline void pushdown(int rt,int m){ if(!tag[rt]) return; if(tag[rt]==1){ tree[left].linel=tree[left].liner=tree[left].linem=0;tree[left].sum=(m-(m>>1)); tree[right].linel=tree[right].liner=tree[right].linem=0;tree[right].sum=(m>>1); tag[left]=tag[right]=1; tag[rt]=0; } if(tag[rt]==2){ tree[left].linel=tree[left].liner=tree[left].linem=(m-(m>>1)); tree[left].sum=0; tree[right].linel=tree[right].liner=tree[right].linem=(m>>1); tree[right].sum=0; tag[left]=tag[right]=2; tag[rt]=0; } } void build(int l,int r,int rt){ if(l==r){ tree[rt]=(Node){1,1,1,0}; return; } build(lson); build(rson); pushup(rt,len); } void clear(int from,int to,int l,int r,int rt){ if(from<=l&&to>=r){ tree[rt]=(Node){ len,len,len,0 }; tag[rt]=2; return; } pushdown(rt,len); if(from<=mid) clear(from,to,lson); if(to>mid) clear(from,to,rson); pushup(rt,len); return; } void update(int from,int to,int l,int r,int rt){ if(from<=l&&to>=r){ tree[rt]=(Node){ 0,0,0,len }; tag[rt]=1; return; } pushdown(rt,len); if(from<=mid) update(from,to,lson); if(to>mid) update(from,to,rson); pushup(rt,len); return; } int query(int size,int l,int r,int rt){ if(tree[rt].linem<size) return 0x7fffffff; pushdown(rt,len); if(tree[left].linem>=size) return query(size,lson); if(tree[right].linel+tree[left].liner>=size) return mid-tree[left].liner+1; if(tree[right].linem>=size) return query(size,rson); return 0x7fffffff; } int main(){ int n=read(),m=read(); build(root); for(int i=1;i<=m;++i){ int opt=read(); if(opt==1){ int x=read(); int ans=query(x,root); if(ans==0x7fffffff){ printf("0 "); continue; } printf("%d ",ans); update(ans,ans+x-1,root); } if(opt==2){ int x=read(),y=read(); clear(x,x+y-1,root); } } return 0; }