香槟塔

题解：

难度：三星

考察点： 模拟，线段树，二分

解法一：模拟

这个题的测试数据可能比较水，没想到暴力也能卡过去。设置一个数组来记录每一层的香槟体积，对于每一次查询操作，直接输出即可；对于每一次修改操作，如果，则香槟会继续流入下一层，直到不能流为止，否则香槟在当前层终止，并修改当前层的体积。

#include "bits/stdc++.h"
using namespace std;
const int maxn=200000+10;
int a[maxn],b[maxn],n,m;
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--){
        int op,x,v;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            printf("%d\n",b[x]);
        }else{
            scanf("%d%d",&x,&v);
            while(x<=n&&v>0){
                int tmp=a[x]-b[x];
                if(tmp<v){
                    v-=tmp;
                    b[x]=a[x];
                    x++;
                }else{
                    b[x]+=v;
                    v=0;
                }
            }
        }
    }
    return 0;
}

解法二：二分+线段树

线段树是一种快速处理区间问题的数据结构，对于区间更新，区间求合等问题能在的时间复杂度内完成，具体可以参见Codeforces上这份教程

用线段树维护每一层的剩余容量，对于查询操作，直接总容量减去剩余容量即可；对于更新操作，因为从第层开始往下，剩余容量是单调递增的，因此具有可二分性，可以二分从层倒入能到达的层数，则第到层的剩余容量都区间修改为，第层容量修改为到的总剩余容量减去。因为有二分和线段树，所以复杂度为 .

#include "bits/stdc++.h"
using namespace std;
const int maxn=2e5+100;
typedef long long LL;
struct node{
    int left,right;
    LL sum,val;
}tree[maxn<<2];
int n,m;
LL a[maxn];
void pushup(int rt){
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdwon(int rt){
    tree[rt<<1].sum = (tree[rt<<1].right - tree[rt<<1].left + 1) * tree[rt].val;
    tree[rt<<1|1].sum = (tree[rt<<1|1].right - tree[rt<<1|1].left + 1) * tree[rt].val;
    tree[rt<<1].val = tree[rt<<1|1].val = tree[rt].val;
    tree[rt].val = -1;
}
void build(int l,int r,int rt){
    tree[rt].left=l,tree[rt].right=r;
    tree[rt].val=-1;
    if(l==r){
        tree[rt].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int c,int rt){
    int L=tree[rt].left,R=tree[rt].right;
    if(l==L&&r==R){
        tree[rt].val=(LL)c;
        tree[rt].sum=(LL)(R-L+1)*c;
        return;
    }
    if(tree[rt].val!=-1) pushdwon(rt);
    int mid=(L+R)/2;
    if(r<=mid) update(l,r,c,rt<<1);
    else if(l>mid) update(l,r,c,rt<<1|1);
    else{
        update(l,mid,c,rt<<1);
        update(mid+1,r,c,rt<<1|1);
    }
    pushup(rt);
}
LL query(int l,int r,int rt){
    int L=tree[rt].left,R=tree[rt].right;
    if(l==L&&r==R) return tree[rt].sum;
    if(tree[rt].val!=-1) pushdwon(rt);
    int mid=(L+R)/2;
    if(r<=mid) return query(l,r,rt<<1);
    if(l>mid) return query(l,r,rt<<1|1);
    return query(l,mid,rt<<1)+query(mid+1,r,rt<<1|1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,n,1);
    while(m--){
        int op,x;
        LL v;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            printf("%lld\n",a[x]-query(x,x,1));
        }else{
            scanf("%d%lld",&x,&v);
            int l=x,r=n,y=-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(query(x,mid,1)>=v){
                    y=mid;
                    r=mid-1;
                }else l=mid+1;
            }
            if(y==-1){
                update(x,n,0,1);
            }else if(x==y){
                int tmp=query(x,x,1);
                update(x,x,tmp-v,1);
            }else{
                int tmp=query(x,y,1);
                update(x,y-1,0,1);
                update(y,y,tmp-v,1);
            }
        }
    }
    return 0;
}