线段树双tag+差分数组——cf1208E

超、凢脫俗 2023-10-11 09:04 12阅读 0赞

写了一上午

/*
    对于每个数组a[],先排序然后从大到小把a[i]放进线段树更新
    设a[i]的位置是pos,那么其可更新的区间是[pos,w-(li-pos)]
    线段树结点保存
    tag=now表示当前区间已经被更新满了，无需再往下更新 
    flag=now表示当前区间被更新过
    flag=now-1表示当前区间从未被更新过，可以直接进行覆盖  
    */
    #include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define N 1000005
    #define ll long long 
    ll ans[N];
    ll n,w;
    struct Node{ll pos,a;};
    int cmp(Node a,Node b){
        return a.a>b.a;}
    vector<Node>v[N];
     
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    int tag[N<<2],flag[N<<2],now;
    void pushup(int rt){
        if(flag[rt<<1]==now || flag[rt<<1|1]==now)
            flag[rt]=now;
        if(tag[rt<<1]==now && tag[rt<<1|1]==now)
            tag[rt]=now;
    }
    void update(int L,int R,ll v,int l,int r,int rt){
        if(R<L)return;
        if(tag[rt]==now)return;//这个区间不用更新了0 
        if(L<=l && R>=r && flag[rt]!=now){
            ans[l]+=v;ans[r+1]-=v;
            flag[rt]=tag[rt]=now;
            return;
        }
        int m=l+r>>1;
        if(L<=m)update(L,R,v,lson);
        if(R>m)update(L,R,v,rson);
        pushup(rt);
    }
     
    int main(){
        cin>>n>>w;
        for(int i=1;i<=n;i++){
            int k;cin>>k;
            for(int j=1;j<=k;j++){
                Node t;
                scanf("%lld",&t.a);
                t.pos=j;
                v[i].push_back(t);
            }
        }
        
        for(int i=1;i<=n;i++){
            now=i;
            sort(v[i].begin(),v[i].end(),cmp);
            for(int j=0;j<v[i].size();j++){
                Node c=v[i][j];
                if(c.a<0){
        //开头结尾更新进0 
                    update(1,w-v[i].size(),0,1,w,1);
                    update(v[i].size()+1,w,0,1,w,1);
                }
                update(c.pos,w-v[i].size()+c.pos,c.a,1,w,1);
            }
        }    
        
        for(int i=1;i<=w;i++)ans[i]+=ans[i-1];
        for(int i=1;i<=w;i++)cout<<ans[i]<<" ";
    }

转载于:https://www.cnblogs.com/zsben991126/p/11511179.html