【HDU 4614】Vases and Flowers（线段树区间更新懒惰标记）

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50001
using namespace std;
int tree[N<<2],lz[N<<2];
void PushUp(int node)
{
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
void PushDown(int node,int v)
{
    if(lz[node]==2)tree[node<<1]=tree[node<<1|1]=0;//清空区间
    else if(lz[node]==1)//填满区间
    {
        tree[node<<1]=v-(v>>1);//左儿子的区间长度
        tree[node<<1|1]=v>>1;
    }
    lz[node<<1]=lz[node<<1|1]=lz[node];//将懒惰标记下移
    lz[node]=0;
}
void build(int l,int r,int node)
{
    lz[node]=tree[node]=0;
    if(l==r)return;
    int m=l+r>>1;
    build(l,m,node<<1);
    build(m+1,r,node<<1|1);
}
//查询[ll,rr]有多少花。节点node对应区间[l,r]
int query(int l,int r,int node,int ll,int rr)
{
    if(r<ll||l>rr)return 0;//[l,r]不在[ll,rr]范围内
    if(ll<=l&&r<=rr)return tree[node];//[l,r]完全在[ll,rr]范围内
    if(lz[node])PushDown(node,r-l+1);//将懒惰标记下移
    int m=l+r>>1;
    return query(l,m,node<<1,ll,rr)+query(m+1,r,node<<1|1,ll,rr);
}
void update(int l,int r,int node,int ll,int rr)
{
    if(r<ll||l>rr)return;
    if(ll<=l&&r<=rr)
    {
        tree[node]=r-l+1;//区间填满
        lz[node]=1;//标记为需要填满子区间，直接覆盖原来的懒惰标记
    }
    else
    {
        if(lz[node])PushDown(node,r-l+1);//先将原有的标记下移
        int m=l+r>>1;
        update(l,m,node<<1,ll,rr);
        update(m+1,r,node<<1|1,ll,rr);
        PushUp(node);
    }
}
//找出第v个空瓶子的下标
int solve(int l,int r,int node,int v)
{
    if(l==r) return l;
    if(lz[node])PushDown(node,r-l+1);
    int m=l+r>>1;
    int ans=m-l+1-tree[node<<1];//左儿子区间有多少空瓶子
    if(ans<v) return solve(m+1,r,node<<1|1,v-ans);
    return solve(l,m,node<<1,v);
}
int dele(int l,int r,int node,int ll,int rr)
{
    if(r<ll||l>rr)return 0;
    int ans=0;
    if(ll<=l&&r<=rr)
    {
        ans=tree[node];//要清除的花
        tree[node]=0;
        lz[node]=2;
    }
    else
    {
        if(lz[node])PushDown(node,r-l+1);
        int m=l+r>>1;
        ans=dele(l,m,node<<1,ll,rr)+dele(m+1,r,node<<1|1,ll,rr);
        PushUp(node);
    }
    return ans;
}
int main()
{
    int t,n,m,k,a,b,ansl,ansr;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        build(0,n-1,1);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&k,&a,&b);
            if(k==1)
            {
                int sum=query(0,n-1,1,a,n-1);//求a到n-1有多少花
                if(sum==n-a) printf("Can not put any one.\n");//如果满了就不能插了
                else
                {
                    int num=a-query(0,n-1,1,0,a-1);//0到a-1有多少空瓶子
                    ansl=solve(0,n-1,1,num+1);//第num+1个空瓶子的下标
                    ansr=solve(0,n-1,1,min(num+b,num+n-a-sum));//第num+b个空瓶子的下标
                    printf("%d %d\n",ansl,ansr);
                    update(0,n-1,1,ansl,ansr);
                }
            }
            else printf("%d\n", dele(0,n-1,1,a,b));
        }
        printf("\n");
    }
}