2019.8.5 NOIP模拟测试16 反思总结

#include<iostream>
#include<cstdio>
using namespace std;
int m,q,kk,vv;
struct node{
    int k,v;
}a[200010];
struct tree{
    int l,r,sum,pi,vi;
}b[800010];
int work(int p,int v){
    if(b[p*2+1].pi<v){
        return work(p*2,v-b[p*2+1].pi+b[p*2+1].vi);
    }
    else if(b[p*2+1].pi==v){
        return b[p].sum-b[p*2+1].sum;
    }
    else{
        return b[p].sum-b[p*2+1].sum+work(p*2+1,v);
    }
}
void update(int p){
    if(!b[p*2+1].vi){
        b[p].sum=b[p*2].sum+b[p*2+1].sum;
        b[p].vi=b[p*2+1].vi+b[p*2].vi;
        b[p].pi=b[p*2].pi+b[p*2+1].pi;
    }
    else if(b[p*2+1].vi>=b[p*2].pi){
        b[p].sum=b[p*2+1].sum;
        b[p].pi=b[p*2+1].pi;
        b[p].vi=b[p*2+1].vi-b[p*2].pi+b[p*2].vi;
    }
    else{
        b[p].sum=b[p*2+1].sum+work(p*2,b[p*2+1].vi);
        b[p].pi=b[p*2+1].pi+b[p*2].pi-b[p*2+1].vi;
        b[p].vi=b[p*2].vi;
    }
}
void build(int p,int l,int r){
    b[p].l=l,b[p].r=r;
    if(l==r){
        if(!a[l].k){
            b[p].sum=a[l].v;
            b[p].pi=1,b[p].vi=0;
        }
        else{
            b[p].sum=0;
            b[p].pi=0;
            b[p].vi=a[l].v;
        }
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    update(p);
}
void change(int p,int l,int r){
    if(l<=b[p].l&&b[p].r<=r){
        if(!kk){
            b[p].sum=vv;
            b[p].pi=1,b[p].vi=0;
        }
        else{
            b[p].sum=0;
            b[p].pi=0;
            b[p].vi=vv;
        }
        return;
    }
    int mid=(b[p].l+b[p].r)/2;
    if(l<=mid)change(p*2,l,r);
    if(r>mid)change(p*2+1,l,r);
    update(p);
}
int main()
{
//    freopen("3.in","r",stdin);
//    freopen("3.out","w",stdout);
    scanf("%d%d",&m,&q);
    for(int i=1,k,v;i<=m;i++){
        scanf("%d%d",&a[i].k,&a[i].v);
    }
    build(1,1,m);
    while(q--){
        int c;
        scanf("%d%d%d",&c,&kk,&vv);
        change(1,c,c);
        printf("%d\n",b[1].sum);
    }
    return 0;
}