悬5关

题号：HDU 4614

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int sum,left,right,lazy;
}tree[200005];
int a[200005];
int n,m;
void pushup(int x){
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}
void build(int x,int l,int r){
	tree[x].left=l;
	tree[x].right=r;
	if(l==r){
		tree[x].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void pushdown(int x){
	int la=tree[x].lazy;
	if(la!=0){
		tree[x<<1].sum=la*(tree[x<<1].right-tree[x<<1].left+1);
		tree[x<<1].lazy=la;
		tree[x<<1|1].sum=la*(tree[x<<1|1].right-tree[x<<1|1].left+1);
		tree[x<<1|1].lazy=la;
		tree[x].lazy=0;
	}
}
void update(int x,int from,int to,int v){
	if(from<=tree[x].left&&to>=tree[x].right){
		tree[x].lazy=v;
		tree[x].sum=v*(tree[x].right-tree[x].left+1);
		return ;
	}
	pushdown(x);
	int mid=(tree[x].left+tree[x].right)>>1;
	if(from<=mid){
		update(x<<1,from,to,v);
	}
	if(to>mid){
		update(x<<1|1,from,to,v);
	}
	pushup(x);
}
int query(int x,int l,int r){
	if(l<=tree[x].left&&r>=tree[x].right){
		return tree[x].sum;
	}
	pushdown(x);
	int mid=(tree[x].left+tree[x].right)>>1;
	int ans=0;
	if(l<=mid){
		ans+=query(x<<1,l,r);
	}
	if(r>mid){
		ans+=query(x<<1|1,l,r);
	}
	return ans;
}
int ef(int x,int num){
	int l=x,r=n;
	int ans=0,mid=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(query(1,x,m)>=num){
			ans=m;
			r=m-1;
		}
		else{
			l=m+1;
		}
	}
	return ans;
}
signed main(){
	int t;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		memset(a,0,sizeof a);
		build(1,1,n);
		for(int i=1;i<=m;i++){
			int opt,x,y;
			scanf("%lld%lld%lld",&opt,&x,&y);
			if(opt==1){
				x++;
				int cnt=query(1,x,n);
				if(cnt==0){
					printf("Can not put any one.\n");
				}
				else{
					int l=ef(x,1);
					int r=ef(x,min(y,cnt));
					update(1,l,r,0);
					printf("%d %d\n",l-1,r-1);
				}
			}
			else{
				x++,y++;
				printf("%d\n",y-x+1-query(1,x,y));
				update(1,x,y,1);
			}
		}
	}
	return 0;
}