THUSCH 2017 大魔法师（分块）

题意

https://loj.ac/problem/2980

思路

分块是处理序列问题的一种比较无脑暴力的做法，相较线段树的优势在于不用考虑多层的 \(\text{push_up}\) 和 \(\text{push_down}\)，即不用考虑延迟标记下传下一层标记的问题（分块的延迟标记是只针对一个块的，一下传就没了），考虑问题较线段树而言更简单。

不难发现，若干次区间修改后，受到相同修改的区间，令修改后的 \(A_i\) 为 \(A_i'\) ，有 \(A_i'=aaA_i+baB_i+caC_i+da\)，其中 \(aa,ba,ca,da\) 是四个常数，分别表示 \(A\) 转给 \(A\) ，\(B\) 转给 \(A\) ，\(C\) 转给 \(A\) 贡献的系数及 \(A\) 需要加上的常数，\(B,C,D\) 同理，那么使用 \(12\) 个数组即可表示延迟标记。然后再用 \(sa,sb,sc\) 表示一个块内 \(A,B,C\) 的和。

\(7\) 种操作的块修改都可以直接对转移系数进行修改，并维护好 \(sa,sb,sc\) ，下传标记就把新的 \(A,B,C\) 算出来，替换旧的 \(A,B,C\) 即可。

代码

#include<bits/stdc++.h>
#define FOR(i,k,y) for(int i=(k),i##END=(y);i<=i##END;++i)
#define DOR(i,k,y) for(int i=(k),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &k,const _T y){return y<k?k=y,1:0;}
template<typename T,typename _T>inline bool chk_mak(T &k,const _T y){return k<y?k=y,1:0;}
typedef long long ll;
const int P=998244353;
const int N=(int)2.5e5+5;
const int alpha=350;
int aa[N],ba[N],ca[N],da[N];
int ab[N],bb[N],cb[N],db[N];
int ac[N],bc[N],cc[N],dc[N];
int sa[N],sb[N],sc[N];
int a[N],b[N],c[N];
int n,m;

void pls(int &a,int b){a+=b;if(a>=P)a-=P;}
void get_range(int k,int &l,int &r){l=std::max(1,k*alpha),r=std::min(n,(k+1)*alpha-1);}
void push_up(int k)
{
    int l,r;
    get_range(k,l,r);
    sa[k]=sb[k]=sc[k]=0;
    FOR(i,l,r)pls(sa[k],a[i]);
    FOR(i,l,r)pls(sb[k],b[i]);
    FOR(i,l,r)pls(sc[k],c[i]);
}
void push_down(int k)
{
    int l,r,len;
    get_range(k,l,r);
    FOR(i,l,r)
    {
        int A,B,C;
        A=((ll)aa[k]*a[i]+(ll)ba[k]*b[i]+(ll)ca[k]*c[i]+da[k])%P;
        B=((ll)ab[k]*a[i]+(ll)bb[k]*b[i]+(ll)cb[k]*c[i]+db[k])%P;
        C=((ll)ac[k]*a[i]+(ll)bc[k]*b[i]+(ll)cc[k]*c[i]+dc[k])%P;
        a[i]=A,b[i]=B,c[i]=C;
    }
    ab[k]=ac[k]=ba[k]=bc[k]=ca[k]=cb[k]=da[k]=db[k]=dc[k]=0;
    aa[k]=bb[k]=cc[k]=1;
}
void taged(int k,int op,int val)
{
    int l,r,len;
    get_range(k,l,r);
    len=r-l+1;
    if(op==1)
        pls(sa[k],sb[k]),pls(aa[k],ab[k]),pls(ba[k],bb[k]),pls(ca[k],cb[k]),pls(da[k],db[k]);
    else if(op==2)
        pls(sb[k],sc[k]),pls(ab[k],ac[k]),pls(bb[k],bc[k]),pls(cb[k],cc[k]),pls(db[k],dc[k]);
    else if(op==3)
        pls(sc[k],sa[k]),pls(ac[k],aa[k]),pls(bc[k],ba[k]),pls(cc[k],ca[k]),pls(dc[k],da[k]);
    else if(op==4)
        pls(sa[k],(ll)val*len%P),pls(da[k],val);
    else if(op==5)
        sb[k]=(ll)sb[k]*val%P,ab[k]=(ll)ab[k]*val%P,bb[k]=(ll)bb[k]*val%P,cb[k]=(ll)cb[k]*val%P,db[k]=(ll)db[k]*val%P;
    else if(op==6)
        sc[k]=(ll)val*len%P,ac[k]=bc[k]=cc[k]=0,dc[k]=val;
}

void upd(int l,int r,int op,int val)
{
    if(op==1)FOR(i,l,r)pls(a[i],b[i]);
    else if(op==2)FOR(i,l,r)pls(b[i],c[i]);
    else if(op==3)FOR(i,l,r)pls(c[i],a[i]);
    else if(op==4)FOR(i,l,r)pls(a[i],val);
    else if(op==5)FOR(i,l,r)b[i]=(ll)b[i]*val%P;
    else if(op==6)FOR(i,l,r)c[i]=val;
}

void update(int l,int r,int op,int val)
{
    int kx=l/alpha,ky=r/alpha;
    if(kx==ky)
    {
        push_down(kx);
        upd(l,r,op,val);
        push_up(kx);
        return;
    }
    FOR(i,kx+1,ky-1)taged(i,op,val);
    push_down(kx),push_down(ky);
    upd(l,(kx+1)*alpha-1,op,val);
    upd(ky*alpha,r,op,val);
    push_up(kx),push_up(ky);
}

void query(int l,int r)
{
    int kx=l/alpha,ky=r/alpha;
    int A=0,B=0,C=0;
    if(kx==ky)
    {
        push_down(kx);
        FOR(i,l,r)pls(A,a[i]),pls(B,b[i]),pls(C,c[i]);
        printf("%d %d %d\n",A,B,C);
        return;
    }
    FOR(i,kx+1,ky-1)pls(A,sa[i]),pls(B,sb[i]),pls(C,sc[i]);
    push_down(kx),push_down(ky);
    FOR(i,l,(kx+1)*alpha-1)pls(A,a[i]),pls(B,b[i]),pls(C,c[i]);
    FOR(i,ky*alpha,r)pls(A,a[i]),pls(B,b[i]),pls(C,c[i]);
    printf("%d %d %d\n",A,B,C);
}

int main()
{
    scanf("%d",&n);
    FOR(i,1,n)scanf("%d%d%d",&a[i],&b[i],&c[i]);
    FOR(i,1/alpha,n/alpha)
    {
        ab[i]=ac[i]=ba[i]=bc[i]=ca[i]=cb[i]=da[i]=db[i]=dc[i]=0;
        aa[i]=bb[i]=cc[i]=1;
        push_up(i);
    }
    scanf("%d",&m);
    while(m--)
    {
        int op,l,r,v;
        scanf("%d%d%d",&op,&l,&r);
        if(op>=4&&op<=6)scanf("%d",&v);
        if(op==7)query(l,r);
        else update(l,r,op,v);
    }
    return 0;
}

THUSCH 2017 大魔法师（分块）

原文：https://www.cnblogs.com/Paulliant/p/10570392.html