| 11946317 |
2014-10-23 09:08:28 |
Accepted |
4614 |
437MS |
2348K |
3340 B |
G++ |
KinderRiven
|
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
/********************************
KinderRiven
*******************************/
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 55555;
struct Node{
int l,r;
int v,col;
}node[maxn << 2];
int N,M;
void pushdown(int pos){
if(node[pos].col >= 0){
node[lson].col = node[pos].col; node[rson].col = node[pos].col;
node[lson].v = (node[lson].r - node[lson].l + 1) * node[pos].col;
node[rson].v = (node[rson].r - node[rson].l + 1) * node[pos].col;
node[pos].col = -1;
}
}
void pushup(int pos){
node[pos].v = node[lson].v + node[rson].v;
}
void BuildTree(int L,int R,int pos){
node[pos].l = L;
node[pos].r = R;
node[pos].col= -1;
if(L == R){
node[pos].v = 1;
return;
}
int m = (L + R) >> 1;
BuildTree(L,m,lson);
BuildTree(m + 1,R,rson);
pushup(pos);
return;
}
void UpDate(int L,int R,int pos,int value){
//printf("%d %d
",node[pos].l,node[pos].r);
if(L <= node[pos].l && node[pos].r <= R){
node[pos].v = (node[pos].r - node[pos].l + 1) * value;
node[pos].col = value;
return;
}
pushdown(pos);
int m = (node[pos].l + node[pos].r) >> 1;
if(L <= m)
UpDate(L,R,lson,value);
if(R > m)
UpDate(L,R,rson,value);
pushup(pos);
}
int Query_sum(int L,int R,int pos){
if(L <= node[pos].l && node[pos].r <= R){
return node[pos].v;
}
pushdown(pos);
int m = (node[pos].l + node[pos].r) >> 1;
int ret = 0;
if(L <= m)
ret += Query_sum(L,R,lson);
if(R > m)
ret += Query_sum(L,R,rson);
pushup(pos);
return ret;
}
void Query(int value,int pos,int &p){
if(node[pos].l == node[pos].r){
p = node[pos].l;
return;
}
pushdown(pos);
int m = (node[pos].l + node[pos].r) >> 1;
if(node[lson].v >= value)
Query(value,lson,p);
else
Query(value - node[lson].v,rson,p);
pushup(pos);
return;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
BuildTree(0,N - 1,1);
int op,a,b;
for(int i = 0;i < M;i ++){
scanf("%d%d%d",&op,&a,&b);
//printf("%d
",Query_sum(0,N-1,1));
if(op == 1){ //须要改动
int sum = Query_sum(0,N - 1,1);
int k1 = Query_sum(a,N - 1,1);
int v = sum - k1;
//printf("%d
",k1);
int p,q;
if(k1 == 0){
printf("Can not put any one.
");
continue;
}
if(k1 < b) b = k1;
Query(v + 1,1,p);
Query(v + b,1,q);
UpDate(p,q,1,0);
printf("%d %d
",p,q);
}
else if(op == 2){
int value = Query_sum(a,b,1);
UpDate(a,b,1,1);
printf("%d
",b - a + 1 - value);
}
}
printf("
");
}
return 0;
}