http://acm.hdu.edu.cn/showproblem.php?pid=4614
HDU 4614 Vases and Flowers (2013多校第二场线段树)
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int MOD = 1e9+;
#define LL long long
#define mi() (l+r)>>1
double const pi = acos(-);
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
struct Edge {
int l,r;
int lazy,sum;
} e[N<<]; void pushdown(int rt) {
e[rt].sum=e[rt<<].sum+e[rt<<|].sum;
}
void pushup(int rt) {
if(e[rt].lazy!=-) {
e[rt<<].lazy=e[rt<<|].lazy=e[rt].lazy;
e[rt<<].sum=(e[rt<<].r-e[rt<<].l+)*e[rt].lazy;
e[rt<<|].sum=(e[rt<<|].r-e[rt<<|].l+)*e[rt].lazy;
e[rt].lazy=-;
}
} void build(int l,int r,int rt) {
e[rt].l=l;
e[rt].r=r;
e[rt].lazy=-;
if(l==r) {
e[rt].sum=;
return;
}
int mid=mi();
build(lson);
build(rson);
pushdown(rt);
} int query(int l,int r,int rt) {
if(e[rt].l==l&&e[rt].r==r) {
return e[rt].sum;
}
pushup(rt);
int mid=(e[rt].l+e[rt].r)>>;
if(r<=mid) return query(l,r,rt<<);
else if(l>mid) return query(l,r,rt<<|);
else return query(l,mid,rt<<)+query(mid+,r,rt<<|);
} void update(int l,int r,int rt,int c){
if(e[rt].l==l&&e[rt].r==r){
e[rt].lazy=c;
e[rt].sum=(e[rt].r-e[rt].l+)*c;
return;
}
pushup(rt);
int mid=(e[rt].l+e[rt].r)>>;
if(r<=mid) update(l,r,rt<<,c);
else if(l>mid) update(l,r,rt<<|,c);
else {
update(l,mid,rt<<,c);
update(mid+,r,rt<<|,c);
}
pushdown(rt);
} int main() {
// fre();
int T;
scanf("%d",&T);
while(T--) {
int n,q;
cin>>n>>q;
build(,n,);
while(q--) {
int op,a,b;
cin>>op>>a>>b;
if(op==) {
int L=a+,R=n;
int st,ed;
if((n-L+-query(L,n,))==) {
printf("Can not put any one.\n");
continue;
}
st=inf;
while(L<=R) {
int mid=(L+R)>>;
if((mid-(a+)+-query(a+,mid,))>=) {
st=min(st,mid);
R=mid-;
} else {
L=mid+;
}
}
int tem=n-st+-query(st,n,);
if(tem<b) b=tem;
ed=inf;
L=st,R=n;
while(L<=R) {
int mid=(L+R)>>;
tem=mid-st+-query(st,mid,);
if(tem==b) {
ed=min(ed,mid);
R=mid-;
} else if(tem>b) {
R=mid-;
} else {
L=mid+;
}
}
printf("%d %d\n",st-,ed-);
update(st,ed,,);
} else {
printf("%d\n",query(a+,b+,));
update(a+,b+,,);
}
}
cout<<endl;
}
return ;
}