HDU - 4614（线段树+区间更新）

HDU - 4614（线段树+区间更新）

参考博客：点我
每次查询某个区间【X, N】这个区间是否能放一朵花，若能放就返回最后一朵花的位置。若不能放则返回-1。 每次线段树向下递归的时候，判断一下左边空花瓶的数量是否>=f， 若大于代表左边区间的花瓶就可以放完，那么直接递归左边区间，反之则将花的数量-左边区间空花瓶的数量，然后递归右区间。类似主席树求第K大的思想。最后到根节点再判断一下该节点是否能够放花，若不能那么只能又去找另一区间。比如递归了右区间，但是发现右边区间已经无法放了，那么只能去左边区间找最后一朵花的位置。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn  50005
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;

int sum[maxn<<2],lazy[maxn<<2];

void build(int node,int l,int r){
    if(l==r){
        sum[node]=1;
        lazy[node]=-1;
        return ;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    lazy[node]=-1;
    sum[node]=sum[node<<1]+sum[node<<1|1];
}


void pushdown(int node,int l,int r){
    if(lazy[node]==-1) return ;
    if(lazy[node]==0){
        lazy[node<<1]=lazy[node<<1|1]=0;
        sum[node<<1]=sum[node<<1|1]=0;
    }
    else if(lazy[node]==1){
        int mid=(l+r)>>1;
        sum[node<<1]=mid-l+1;
        sum[node<<1|1]=r-mid;
        lazy[node<<1]=lazy[node<<1|1]=1;
    }
    lazy[node]=-1;
}

void update(int node,int start,int ends,int l,int r,int val){
    if(start>=l&&ends<=r){
        if(val==1) sum[node]=ends-start+1;
        else sum[node]=0;
        lazy[node]=val;
        return ;
    }
    int mid=(start+ends)>>1;
    pushdown(node,start,ends);
    if(l<=mid) update(node<<1,start,mid,l,r,val);
    if(mid<r) update(node<<1|1,mid+1,ends,l,r,val);
    sum[node]=sum[node<<1]+sum[node<<1|1];
}
int query(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r) return sum[node];
    int mid=(start+ends)>>1;
    pushdown(node,start,ends);
    int ans=0;
    if(l<=mid) ans+=query(node<<1,start,mid,l,r);
    if(r>mid) ans+=query(node<<1|1,mid+1,ends,l,r);
    return ans;
}

int solve(int node,int start,int ends,int l,int r,int k){
    if(start==ends){
        if(sum[node]==0) return -1;
        if(sum[node]==1) return start;
    }
    pushdown(node,start,ends);
    int ln=0,ans=-1;
    int mid=(start+ends)>>1;
    if(l<=mid) ln=query(node<<1,start,mid,l,mid);
    if(k>ln)   ans=solve(node<<1|1,mid+1,ends,l,r,k-ln);
    else ans=solve(node<<1,start,mid,l,r,k);
    if(ans==-1){
        if(ln==0) return -1;
        ans=solve(node<<1,start,mid,l,r,k);
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        build(1,1,n);
        for(int i=0;i<m;i++){
            int x,y,k;
            scanf("%d%d%d",&k,&x,&y);
            if(k==1){
                x++;
                int ends=solve(1,1,n,x,n,y);
                if(ends==-1) printf("Can not put any one.\n");
                else{
                    int start=solve(1,1,n,x,n,1);
                    printf("%d %d\n",start-1,ends-1);
                    update(1,1,n,start,ends,0);
                }
            }
            else{
                x++,y++;
                int t=query(1,1,n,x,y);
                update(1,1,n,x,y,1);
                printf("%d\n",y-x-t+1);
            }
        }
        printf("\n");
    }
    return 0;
}