题解 P6707 【[COCI2010-2011#7] UPIT】终极数据结构

Rosyclouds · 2020-09-28 22:22:40 · 题解

对楼上分块算法的代码补充

另提一下，之所以不会T,是因为我们当块大小>2S时才会重构，那么最多重构\sqrt(n)次,复杂度是\sqrt(n)n

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ls p<<1
#define rs p<<1|1
const int M=2e5+5;
int n,tot,Q,S,sz[450];//sz：块的大小 
LL lazy[3][450],sum[450],num[450][900],tmp[M];//lazy:延迟更新标记 
void Down(int p){ 
    if(lazy[0][p]){
        for(int i=1;i<=sz[p];++i)num[p][i]=lazy[0][p];
        lazy[0][p]=0;
    }
    if(lazy[1][p]){
        LL &x=lazy[1][p],&y=lazy[2][p];
        for(int i=1;i<=sz[p];++i)
            num[p][i]+=x,x+=y;
        x=y=0;
    }
}
LL Query(int l,int r){
    LL res=0;
    int k=1,id=0,t=1;
    while(k+sz[id]<=l)k+=sz[id++];
    Down(id);
    while(k<l)++k,++t;
    while(t<=sz[id]&&k<=r)res+=num[id][t++],++k;
    ++id;
    while(k+sz[id]<=r)k+=sz[id],res+=sum[id++];
    t=1;Down(id);
    while(k<=r)res+=num[id][t++],++k;
    return res;
}
void Change(int l,int r,int x){
    int k=1,id=0,t=1;
    while(k+sz[id]<=l)k+=sz[id++];
    Down(id);
    while(k<l)++k,++t;
    while(t<=sz[id]&&k<=r)
        sum[id]+=x-num[id][t],num[id][t++]=x,++k;
    ++id;
    while(k+sz[id]<=r){
        k+=sz[id];
        sum[id]=1ll*sz[id]*x;
        lazy[0][id]=x;lazy[1][id]=lazy[2][id]=0;
        id++;
    }
    t=1;Down(id);
    while(k<=r){
        sum[id]+=x-num[id][t],num[id][t++]=x,++k;
    }
    return ;
}
void Update(int l,int r,int x){
    int k=1,id=0,t=1;
    LL v=x;
    while(k+sz[id]<=l)k+=sz[id++];
    Down(id);
    while(k<l)++k,++t;
    while(t<=sz[id]&&k<=r)
        sum[id]+=v,num[id][t++]+=v,++k,v+=x;
    ++id;
    while(k+sz[id]<=r){
        k+=sz[id];
        sum[id]+=(v+v+(1ll*sz[id]-1)*x)*sz[id]/2;
        lazy[1][id]+=v;lazy[2][id]+=x;
        v+=1ll*sz[id]*x;id++;
    }
    t=1;Down(id);
    while(k<=r){
        sum[id]+=v,num[id][t++]+=v,++k,v+=x;
    }
    return ;
}
void Rebuild(){//块重构 
    tot=0;
    for(int i=0;sz[i];++i){
        Down(i);
        for(int j=1;j<=sz[i];++j)
        tmp[++tot]=num[i][j];
        sz[i]=sum[i]=0;
    }
    S=max(2,(int)sqrt(tot));
    for(int i=1;i<=tot;++i){
        int id=i/S;
        sum[id]+=tmp[i];
        num[id][++sz[id]]=tmp[i];
    }
}
void Insert(int x,int y){
    int k=1,id=0,t=1;
    while(sz[id]&&k+sz[id]<=x)k+=sz[id++];
    Down(id);
    while(k<x)++k,++t;
    for(int i=sz[id];i>=t;--i)num[id][i+1]=num[id][i];
    num[id][t]=y,sum[id]+=y,++sz[id];
    if(sz[id]>2*S)Rebuild(); //当块的大小超出2S的时候将所有块重构 
}
int main(){
    int x,y,z,kind;
    scanf("%d%d",&n,&Q);
    int S=max(2,(int)sqrt(n));
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        int id=i/S;
        num[id][++sz[id]]=x;
        sum[id]+=x;
    }
    while(Q--){
        scanf("%d%d%d",&kind,&x,&y);
        if(kind==1){
            scanf("%d",&z);
            Change(x,y,z);
        }
        else if(kind==2){
            scanf("%d",&z);
            Update(x,y,z);
        }   
        else if(kind==3)
            Insert(x,y);

        else
            printf("%lld\n",Query(x,y));    
    }
    return 0;
}