cf371D Vessels

不知道哪错了,待改。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
typedef long long ll;
const int maxn=2e5+10;
ll a[4*maxn],sum[4*maxn];
bool lazy[4*maxn];
int n,m;
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];return;
}
void pushdown(int id)
{
    if(!lazy[id]) return;
    sum[lson]=0;lazy[lson]=1;
    sum[rson]=0;lazy[rson]=1;
    lazy[id]=0;
    return;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        scanf("%I64d",&a[id]);
        sum[id]=a[id];
        return;
    }
    int m=(l+r)/2;
    build(lson,l,m);
    build(rson,m+1,r);
    pushup(id);
    return;
}
void update(int id,int l,int r,int L,int R)
{
    if(L>R) return;
    if(L<=l && r<=R)
    {
        sum[id]=0;lazy[id]=1;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(L<=m) update(lson,l,m,L,R);
    if(R>m) update(rson,m+1,r,L,R);
    pushup(id);
    return;
}
void update2(int id,int l,int r,int pos,ll v)
{
    if(l==r)
    {
        sum[id]-=v;
        if(sum[id]<0) sum[id]=0;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) update2(lson,l,m,pos,v);
    else update2(rson,m+1,r,pos,v);
    pushup(id);
    return;
}
ll query_sum(int id,int l,int r,int L,int R)
{
    if(L>R) return 0;
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    pushdown(id);
    int ret=0,m=(l+r)/2;
    if(L<=m) ret+=query_sum(lson,l,m,L,R);
    if(R>m) ret+=query_sum(rson,m+1,r,L,R);
    return ret;
}
ll query(int id,int l,int r,int pos)
{
    if(l==r)
    {
        return a[id]-sum[id];
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) return query(lson,l,m,pos);
    else return query(rson,m+1,r,pos);
}
int bsearch(int pos,int l,int r,ll v)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(query_sum(1,1,n,pos,mid)<v) l=mid+1;
        else r=mid-1;
    }
    return l;
}
void debug(int id,int l,int r)
{
    if(l==r)
    {
        printf("%d ",sum[id]);
        return;
    }
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        memset(lazy,0,sizeof(lazy));
        int com,p;
        ll x;
        build(1,1,n);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&com);
            if(com==1)
            {
                scanf("%d%I64d",&p,&x);
                int ret=bsearch(p,p,n,x);
                ll tmp=query_sum(1,1,n,p,ret-1);
                update(1,1,n,p,ret-1);
                update2(1,1,n,ret,x-tmp);
                //debug(1,1,n);puts("");
            }
            else
            {
                scanf("%d",&p);
                printf("%I64d\n",query(1,1,n,p));
                //debug(1,1,n);puts("");
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>