HDU 4614 Vases and Flowers
选段树区间更新
题目描述:插花，每个花瓶只允许插入一枝花。插花操作是从第A个花瓶开始插花，如果第A个花瓶空着，就插入一枝花，否则判断第Ａ＋１个花瓶，知道插完全部的Ｆ只花，或者是没有花瓶可插，把剩余的花弃掉，操作终止。输出插花的第一个花瓶和最后一个花瓶，如果一枝花都无法插入，那输出Can not put any one.。清理操作：清理区间［Ａ，Ｂ］内的话，输出清理的花的数目。
解题分析：线段区间内维护三个量，区间内插的花的数目，区间内第一个空花瓶，最后一个空花瓶。模拟即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 50000 + 10;
struct Node
{
int l,r;
int add,sum,first,last;
}P[maxn << 2];
int n,m;
int tol;
void build(int l,int r,int pos)
{
P[pos].l = P[pos].first = l;
P[pos].r = P[pos].last = r;
P[pos].add = -1;
P[pos].sum = 0;
if(l == r) return ;
int mid = (l + r) / 2;
build(l,mid,pos << 1);
build(mid + 1,r,pos << 1 | 1);
}
void pushup(int pos)
{
P[pos].sum = P[pos << 1].sum + P[pos << 1 | 1].sum;
if( P[pos].sum == (P[pos].r - P[pos].l + 1) )
{
P[pos].first = INF;
P[pos].last = -INF;
}
else
{
P[pos].first = min( P[pos << 1].first,P[pos << 1 | 1].first );
P[pos].last = max(P[pos << 1].last , P[pos << 1 | 1].last );
}
}
void pushdown(int pos)
{
if(P[pos].add != -1)
{
P[pos << 1].add = P[pos << 1 | 1].add = P[pos].add;
if(P[pos].add == 1)
{
P[pos << 1].sum = P[pos << 1].r - P[pos << 1].l + 1;
P[pos << 1].first = INF;
P[pos << 1].last = - INF;
P[pos << 1 | 1].sum = P[pos << 1 | 1].r - P[pos << 1 | 1].l + 1;
P[pos << 1 | 1].first = INF;
P[pos << 1 | 1].last = -INF;
}
else if(P[pos].add == 0)
{
P[pos << 1].sum = P[pos << 1 | 1].sum = 0;
P[pos << 1].first = P[pos << 1].l;
P[pos << 1].last = P[pos << 1].r;
P[pos << 1 | 1].first = P[pos << 1 | 1].l;
P[pos << 1 | 1].last = P[pos << 1 | 1].r;
}
P[pos].add = -1;
}
}
void update1(int L,int R,int pos,int &first,int &last)
{
if(tol <= 0) return;
if(P[pos].sum == (P[pos].r - P[pos].l + 1)) return;
int rest = (P[pos].r - P[pos].l + 1 ) - P[pos].sum;
if(L <= P[pos].l && P[pos].r <= R && rest <= tol)
{
first = min(first,P[pos].first);
last = max(last,P[pos].last);
tol -= rest;
P[pos].sum = P[pos].r - P[pos].l + 1;
P[pos].first = INF;
P[pos].last = -INF;
P[pos].add = 1;
return ;
}
pushdown(pos);
int mid = (P[pos].l + P[pos].r) / 2;
if(L <= mid && tol > 0) update1(L,R,pos << 1,first,last);
if(mid < R && tol > 0) update1(L,R,pos << 1 | 1,first,last);
pushup(pos);
}
int update2(int L,int R,int pos)
{
if(L <= P[pos].l && P[pos].r <= R)
{
int t = P[pos].sum;
P[pos].sum = 0;
P[pos].first = P[pos].l;
P[pos].last = P[pos].r;
P[pos].add = 0;
return t;
}
pushdown(pos);
int mid = ( P[pos]. l + P[pos].r ) / 2;
int ans = 0;
if(L <= mid) ans += update2(L,R,pos << 1);
if(mid < R) ans += update2(L,R,pos << 1 | 1);
pushup(pos);
return ans;
}
int main()
{
int kase;
scanf("%d",&kase);
while(kase--)
{
scanf("%d %d",&n,&m);
build(1,n,1);
while(m--)
{
int k,x,y;
scanf("%d %d %d",&k,&x,&y);
if(k == 1)
{
int first = INF,last = -INF;
tol = y;
x++;
update1(x,n,1,first,last);
if(first == INF) printf("Can not put any one.\n");
else printf("%d %d\n",first - 1,last - 1);
}
else
{
x++;
y++;
cout << update2(x,y,1) << endl;
}
}
puts("");
}
return 0;
}
