题意:有两种操作,第一种从A开始插花,如果有花就跳到下一个,然后输出最后一个花瓶的编号,如果花瓶不够把多余的花丢掉。操作2把区间清空
分析:很明显的线段树操作,就是插花的时候麻烦一下,需要先找出来他剩余的花瓶数,要不没办法更新。
*******************************************************************
#include<algorithm>
#include<stdio.h>
using namespace std; #define lson r<<1
#define rson r<<1|1 const int MAXN = 1e5+; struct stgmentTree
{//sum花瓶的剩余量
int x, y, sum, cover;//cover, 操作1赋值为释放花瓶,操作2沾满花瓶
int mid(){return (x+y)>>;}
int len(){return y-x+;}
}a[MAXN<<];
int ans;
void Build(int r, int x, int y)
{
a[r].x = x, a[r].y = y;
a[r].sum = a[r].len(), a[r].cover = ; if(x == y)
return ; Build(lson, x, a[r].mid());
Build(rson, a[r].mid()+, y);
}
void Down(int r)
{
if(a[r].x != a[r].y && a[r].cover)
{
a[lson].cover = a[rson].cover = a[r].cover;
a[lson].sum = a[r].cover== ? : a[lson].len();
a[rson].sum = a[r].cover== ? : a[rson].len(); a[r].cover = ;
}
}
void Insert(int r, int x, int y, int op)
{
if(a[r].x == x && a[r].y == y)
{
ans += a[r].len()-a[r].sum;
a[r].cover = op;
a[r].sum = (op== ? : a[r].len()); return ;
} Down(r); if(y <= a[r].mid())
Insert(lson, x, y, op);
else if(x > a[r].mid())
Insert(rson, x, y, op);
else
{
Insert(lson, x, a[r].mid(), op);
Insert(rson, a[r].mid()+, y, op);
} a[r].sum = a[rson].sum + a[lson].sum;
}
int QueryPreSum(int r, int k)//求k前面的空花瓶数
{
Down(r); if(a[r].x == a[r].y)
return ;
if(k <= a[r].mid())
return QueryPreSum(lson, k);
else
return a[lson].sum + QueryPreSum(rson, k);
}
int QueryLast(int r, int p)//查找第p个花瓶位置
{
Down(r); if(a[r].x == a[r].y)
return a[r].x; if(a[lson].sum >= p)
return QueryLast(lson, p);
else
return QueryLast(rson, p-a[lson].sum);
} int main()
{
int T; scanf("%d", &T); while(T--)
{
int N, M, op, x, y, L, R; scanf("%d%d", &N, &M); Build(, , N-); while(M--)
{
scanf("%d%d%d", &op, &x, &y);
if(op == )
{
int PreSum = QueryPreSum(, x); if(PreSum == a[].sum)
printf("Can not put any one.\n");
else
{
L = QueryLast(, PreSum+); if(PreSum+y >= a[].sum)
PreSum = a[].sum;
else
PreSum += y;
R = QueryLast(, PreSum); Insert(, L, R, ); printf("%d %d\n", L, R);
}
}
else
{
ans = ;
Insert(, x, y, );
printf("%d\n", ans);
}
} printf("\n");
} return ;
}
/*
2
10 8
1 2 5
2 3 4
1 0 8
2 2 5
1 6 1
1 4 4
1 2 3
*/