HDU

https://cn.vjudge.net/problem/HDU-4614

题意

n个花瓶，m个操作，花瓶里面有的有花，有的是空的。1操作是从a开始往右放b朵花，花瓶有了的不放，跳过，直到a右边都放满了花，多余的扔了。输出本次放花的起始位置，如果一朵不能放，输出一句话。

分析

1~N 的区间，用1表示空的，0表示放了花的。维护一个sum,就是和。对于操作二就是求区间和。

操作一用二分找第一个符合位置的数。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int maxm = 200000 + 10;
const int mod = 10007;

struct ND{
    int l,r;
    int sum,lazy;
}tree[maxn<<2];
int n,m;
void build(int rt,int l,int r){
    tree[rt].lazy=-1;
    tree[rt].sum=0;
    tree[rt].l=l,tree[rt].r=r;
    if(l==r) return;
    int mid = (l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
void pushup(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdown(int rt){
    tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt].lazy;
    if(tree[rt].lazy){
        int len=tree[rt].r-tree[rt].l+1;
        tree[rt<<1].sum=len-(len>>1);
        tree[rt<<1|1].sum=(len>>1);
    }else{
        tree[rt<<1].sum=tree[rt<<1|1].sum=0;
    }
    tree[rt].lazy=-1;
}
void update(int rt,int l,int r,int val){
    if(l==tree[rt].l&&tree[rt].r==r){
        tree[rt].lazy=val;
        if(val) tree[rt].sum=tree[rt].r-tree[rt].l+1;
        else tree[rt].sum=0;
        return;
    }
    if(tree[rt].lazy!=-1) pushdown(rt);
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(r<=mid) update(rt<<1,l,r,val);
    else if(l>mid) update(rt<<1|1,l,r,val);
    else{
        update(rt<<1,l,mid,val);
        update(rt<<1|1,mid+1,r,val);
    }
    pushup(rt);
}
int query(int rt,int l,int r){
    if(tree[rt].l==l&&tree[rt].r==r) return tree[rt].sum;
    if(tree[rt].lazy!=-1) pushdown(rt);
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(r<=mid) return query(rt<<1,l,r);
    else if(l>mid) return query(rt<<1|1,l,r);
    else return query(rt<<1,l,mid)+query(rt<<1|1,mid+1,r);
}
int bin(int s,int ra){//二分找第一个可以插ra朵花的位置
    int l=s,r=n;
    int ans=-1;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        int tmp=query(1,s,mid);
        if(tmp+ra==mid-s+1){
            ans=mid;
            r=mid-1;
        }else{
            if(tmp+ra<mid-s+1) r=mid-1;
            else l=mid+1;
        }
    }
    return ans;
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    int t,cas=1;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        build(1,1,n);
//        printf("Case #%d:
",cas++);
        int x,y,c;
        while(m--){
            scanf("%d%d%d",&c,&x,&y);
            if(c==1){
                int st,ed;
                x++;
                st=bin(x,1);
                if(st==-1){
                    puts("Can not put any one.");
                }else{
                    int tmp=query(1,st,n);
                    tmp=n-st+1-tmp; //最多能插几朵花
                    if(tmp<=y) y=tmp;
                    ed=bin(x,y);
                    printf("%d %d
",st-1,ed-1);
                    update(1,st,ed,1);
                }
            }else{
                x++,y++;
                printf("%d
",query(1,x,y));
                update(1,x,y,0);
            }
        }
        puts("");
    }
    return 0;
}