題意：給你N個花瓶，編號是0 到 N - 1 ，初始狀態花瓶是空的，每個花瓶最多插一朵花。
然後有2個操作。
操作1，a b c ，往在a位置後面(包括a)插b朵花，輸出插入的首位置和末位置。
操作2,a b ,輸出區間[a , b ]范圍內的花的數量，然後全部清空。
很顯然這是一道線段樹。區間更新，區間求和，這些基本的操作線段樹都可以logN的時間范圍內完成。
操作2，很顯然就是線段樹的區間求和，求出[a , b]范圍內的花朵的數量，區間更新，將整個區間全部變成0。
操作1，這裡我們首先需要找出他的首位置和末位置，所以需要二分他的位置。
首先我們二分他的首位置, l = a , r = n ，在這個區間內二分，找出第一個0的位置，那就是該操作的首位置pos1。
然後再二分他的末位置，l = pos1 , r = n ，找到第c個0，就是該操作的末位置pos2，然後區間更新[pos1 ,pos2]全部置為1。
tmp = n - minn + 1 - query(minn,n,1) ; 表示【minn,n】區間內空花瓶的個數，如果需要插的花束多余tmp，則只能插tmp束花。
這題重點在於二分找位置，找了半天終於在別人的幫助下調試出來了............
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;
struct node {
int r,l,mid;
int lazy,sum;
} edge[4*MAX];
void up(int num) {
edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;
}
void build(int l,int r,int num) {
edge[num].l = l;
edge[num].r = r;
edge[num].mid = (l+r) >> 1;
edge[num].lazy = -1;
if(l == r) {
edge[num].sum = 0;
return ;
}
build(l,edge[num].mid,L(num));
build(edge[num].mid+1,r,R(num));
//
up(num);
}
void down(int num) {
//if(edge[num].l == edge[num].r) return ;
if(edge[num].lazy != -1) {
edge[L(num)].lazy = edge[num].lazy;
edge[R(num)].lazy = edge[num].lazy;
edge[L(num)].sum = (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;
edge[R(num)].sum = (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;
edge[num].lazy = -1;
}
}
void update(int l,int r,int num,int k) {
if(l == edge[num].l && r == edge[num].r) {
edge[num].lazy = k;
edge[num].sum = (edge[num].r - edge[num].l + 1) * k;
return ;
}
down(num);
if(r <= edge[num].mid) {
update(l,r,L(num),k);
} else if(l > edge[num].mid) {
update(l,r,R(num),k);
} else {
update(l,edge[num].mid,L(num),k);
update(edge[num].mid + 1,r,R(num),k);
}
up(num);
}
int query(int l,int r,int num) {
if(l == edge[num].l && r == edge[num].r) {
return edge[num].sum;
}
down(num);
if(r <= edge[num].mid) {
return query(l,r,L(num));
} else if(l > edge[num].mid) {
return query(l,r,R(num));
} else {
return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));
}
}
void test(int n) {
for(int i=1; i<=3*n; i++) {
printf("l:%d r:%d sum:%d lazy:%d\n",edge[i].l,edge[i].r,edge[i].sum,edge[i].lazy);
}
}
int main() {
int n,m,i,t;
cin >> t;
while(t --) {
scanf("%d%d",&n,&m);
int a,b,c;
build(1,n,1);
for(i=0; i<m; i++) {
scanf("%d%d%d",&a,&b,&c);
if(a == 1) {
int low = b + 1,high = n,mid,minn = 2*n;
if(n - low + 1 - query(low , n , 1) == 0) {
printf("Can not put any one.\n");
continue;
}
while(low <= high) {
mid = (low + high) >> 1;
if(mid - (b + 1) + 1- query(b+1,mid,1) >= 1) {
minn = min(minn,mid);
high = mid - 1;
} else {
low = mid + 1;
}
}
int tmp = n - minn + 1 - query(minn,n,1) ;
if(c >= tmp) c = tmp; ·
low = minn,high = n;
int maxx = INF;
while(low <= high) {
mid = (low + high) >> 1;
tmp = mid - minn + 1 - query(minn,mid,1) ;
if(tmp == c) {
maxx = min(maxx,mid);
high = mid - 1;
} else if(tmp > c) {
high = mid - 1;
} else {
low = mid + 1;
}
}
printf("%d %d\n",minn-1,maxx-1);
update(minn,maxx,1,1);
} else {
printf("%d\n",query(b+1,c+1,1));
update(b+1,c+1,1,0);
}
}
puts("");
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;
struct node {
int r,l,mid;
int lazy,sum;
} edge[4*MAX];
void up(int num) {
edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;
}
void build(int l,int r,int num) {
edge[num].l = l;
edge[num].r = r;
edge[num].mid = (l+r) >> 1;
edge[num].lazy = -1;
if(l == r) {
edge[num].sum = 0;
return ;
}
build(l,edge[num].mid,L(num));
build(edge[num].mid+1,r,R(num));
//
up(num);
}
void down(int num) {
//if(edge[num].l == edge[num].r) return ;
if(edge[num].lazy != -1) {
edge[L(num)].lazy = edge[num].lazy;
edge[R(num)].lazy = edge[num].lazy;
edge[L(num)].sum = (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;
edge[R(num)].sum = (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;
edge[num].lazy = -1;
}
}
void update(int l,int r,int num,int k) {
if(l == edge[num].l && r == edge[num].r) {
edge[num].lazy = k;
edge[num].sum = (edge[num].r - edge[num].l + 1) * k;
return ;
}
down(num);
if(r <= edge[num].mid) {
update(l,r,L(num),k);
} else if(l > edge[num].mid) {
update(l,r,R(num),k);
} else {
update(l,edge[num].mid,L(num),k);
update(edge[num].mid + 1,r,R(num),k);
}
up(num);
}
int query(int l,int r,int num) {
if(l == edge[num].l && r == edge[num].r) {
return edge[num].sum;
}
down(num);
if(r <= edge[num].mid) {
return query(l,r,L(num));
} else if(l > edge[num].mid) {
return query(l,r,R(num));
} else {
return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));
}
}
void test(int n) {
for(int i=1; i<=3*n; i++) {
printf("l:%d r:%d sum:%d lazy:%d\n",edge[i].l,edge[i].r,edge[i].sum,edge[i].lazy);
}
}
int main() {
int n,m,i,t;
cin >> t;
while(t --) {
scanf("%d%d",&n,&m);
int a,b,c;
build(1,n,1);
for(i=0; i<m; i++) {
scanf("%d%d%d",&a,&b,&c);
if(a == 1) {
int low = b + 1,high = n,mid,minn = 2*n;
if(n - low + 1 - query(low , n , 1) == 0) {
printf("Can not put any one.\n");
continue;
}
while(low <= high) {
mid = (low + high) >> 1;
if(mid - (b + 1) + 1- query(b+1,mid,1) >= 1) {
minn = min(minn,mid);
high = mid - 1;
} else {
low = mid + 1;
}
}
int tmp = n - minn + 1 - query(minn,n,1) ;
if(c >= tmp) c = tmp; ·
low = minn,high = n;
int maxx = INF;
while(low <= high) {
mid = (low + high) >> 1;
tmp = mid - minn + 1 - query(minn,mid,1) ;
if(tmp == c) {
maxx = min(maxx,mid);
high = mid - 1;
} else if(tmp > c) {
high = mid - 1;
} else {
low = mid + 1;
}
}
printf("%d %d\n",minn-1,maxx-1);
update(minn,maxx,1,1);
} else {
printf("%d\n",query(b+1,c+1,1));
update(b+1,c+1,1,0);
}
}
puts("");
}
return 0;
}
