这两天做比赛的状态实在是太差了,尤其是那天就睡了4个小时,早上到学校,下午就去做比赛了,什么题都不想写。其实就是个线段树,不过今天写了好久也没写出来,最近确实做题太少了,之前没有想到二分找点的位置,看了题解才知道,第一次二分还写错了,不过想了一下就调好了,其实还是挺简单的成段更新的线段树。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define MAXN 50005 struct Node { int sum,left,right,lazy; }tree[MAXN<<2]; int n; void build(int l,int r,int rt) { tree[rt].sum=(r-l+1); tree[rt].left=l; tree[rt].right=r; tree[rt].lazy=-1; if(l==r) return; int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); } void pushup(int rt) { tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; tree[rt].left=min(tree[rt<<1].left,tree[rt<<1|1].left); tree[rt].right=max(tree[rt<<1].right,tree[rt<<1|1].right); } void pushdown(int l,int r,int rt) { if(tree[rt].lazy==1) { int m=(l+r)>>1; tree[rt<<1].sum=0; tree[rt<<1|1].sum=0; tree[rt<<1].left=MAXN; tree[rt<<1].right=0; tree[rt<<1|1].left=MAXN; tree[rt<<1|1].right=0; tree[rt<<1].lazy=tree[rt<<1|1].lazy=1; tree[rt].lazy=-1; } else if(tree[rt].lazy==0) { int m=(l+r)>>1; tree[rt<<1].sum=m-l+1; tree[rt<<1|1].sum=r-m; tree[rt<<1].left=l; tree[rt<<1].right=m; tree[rt<<1|1].left=m+1; tree[rt<<1|1].right=r; tree[rt<<1].lazy=tree[rt<<1|1].lazy=0; tree[rt].lazy=-1; } } void update(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { tree[rt].sum=0; tree[rt].lazy=1; return; } pushdown(l,r,rt); int m=(l+r)>>1; if(L<=m) update(L,R,l,m,rt<<1); if(R>m) update(L,R,m+1,r,rt<<1|1); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return tree[rt].sum; } pushdown(l,r,rt); int m=(l+r)>>1,res=0; if(L<=m) res+=query(L,R,l,m,rt<<1); if(R>m) res+=query(L,R,m+1,r,rt<<1|1); pushup(rt); return res; } int drop(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { int num=(r-l+1)-tree[rt].sum; tree[rt].lazy=0; tree[rt].sum=r-l+1; tree[rt].left=l; tree[rt].right=r; return num; } pushdown(l,r,rt); int m=(l+r)>>1,res=0; if(L<=m) res+=drop(L,R,l,m,rt<<1); if(R>m) res+=drop(L,R,m+1,r,rt<<1|1); pushup(rt); return res; } int find1(int l,int r) { int a=l,pos=-1; while(l<=r) { int m=(l+r)>>1; if(query(a,m,1,n,1)) { r=m-1; pos=m; } else l=m+1; } return pos; } int find2(int l,int r,int v) { int a=l,pos=-1; while(l<=r) { int m=(l+r)>>1; if(query(a,m,1,n,1)>=v) { r=m-1; pos=m; } else l=m+1; } return pos; } int main() { int t; scanf("%d",&t); while(t--) { int m; scanf("%d%d",&n,&m); build(1,n,1); for(int i=0;i<m;i++) { int k; scanf("%d",&k); if(k==1) { int p,v; scanf("%d%d",&p,&v); p++; int num=query(p,n,1,n,1); num=min(num,v); if(num==0) printf("Can not put any one.\n"); else { int pos1=find1(p,n),pos2=find2(p,n,min(query(p,n,1,n,1),v)); update(pos1,pos2,1,n,1); printf("%d %d\n",pos1-1,pos2-1); } } else if(k==2) { int x,y; scanf("%d%d",&x,&y); x++,y++; printf("%d\n",drop(x,y,1,n,1)); } } cout<<endl; } }