MnZn求助线段树
查看原帖
MnZn求助线段树
420129
Nt_Tsumiki楼主2024/7/3 09:24

没 T,WA 了

#include <iostream>
#include <cstring>
#include <cstdio>

#define LL long long
#define MOD 998244353
#define N 250001

using namespace std;
int n,m;

struct Matrix {
    LL a[4][4];

    Matrix(int op=0) { memset(a,0,sizeof a); if (op==1) a[0][0]=a[1][1]=a[2][2]=a[3][3]=1; }
    LL* operator[](int x) { return a[x]; }
    
    Matrix operator*(Matrix B) {
        Matrix C=Matrix();
        for (int i=0;i<4;i++)
            for (int j=0;j<4;j++)
                for (int k=0;k<4;k++) (C[i][j]+=a[i][k]*B[k][j]%MOD)%=MOD;
        return C;
    }
    
    Matrix operator+(Matrix B) {
        Matrix C=Matrix();
        for (int i=0;i<4;i++)
            for (int j=0;j<4;j++) C[i][j]=(a[i][j]+B[i][j])%MOD;
        return C;
    }
}A[N];

struct Tree { Matrix sum,tag; }t[N<<2];

void build(int x,int l,int r) {
    t[x].tag=Matrix(1);
    if (l==r) return t[x].sum=A[l],void();
    int mid=(l+r>>1);
    build(x<<1,l,mid); build(x<<1|1,mid+1,r);
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}

void pushdown(int x) {
    t[x<<1].sum=t[x<<1].sum*t[x].tag,t[x<<1].tag=t[x<<1].tag*t[x].tag;
    t[x<<1|1].sum=t[x<<1|1].sum*t[x].tag,t[x<<1|1].tag=t[x<<1|1].tag*t[x].tag;
    t[x].tag=Matrix(1);
}

void upd(int x,int l,int r,int L,int R,Matrix op) {
    if (L<=l and r<=R) return t[x].sum=t[x].sum*op,t[x].tag=t[x].tag*op,void();
    int mid=(l+r>>1); pushdown(x);
    if (L<=mid) return upd(x<<1,l,mid,L,R,op);
    if (R>mid) return upd(x<<1|1,mid+1,r,L,R,op);
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}

Matrix ask(int x,int l,int r,int L,int R) {
    if (L<=l and r<=R) return t[x].sum;
    int mid=(l+r>>1); pushdown(x);
    if (R<=mid) return ask(x<<1,l,mid,L,R);
    else if (L>mid) return ask(x<<1|1,mid+1,r,L,R);
    else return ask(x<<1,l,mid,L,R)+ask(x<<1|1,mid+1,r,L,R);
}

int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld%lld%lld",&A[i][0][0],&A[i][0][1],&A[i][0][2]),A[i][0][3]=1;
    build(1,1,n);
    scanf("%d",&m);
    for (int i=1,op,l,r,v;i<=m;i++) {
        scanf("%d",&op); Matrix tmp=Matrix(1);
        if (op==1) {
            scanf("%d%d",&l,&r);
            tmp[1][0]=1;
            upd(1,1,n,l,r,tmp);
        } else if (op==2) {
            scanf("%d%d",&l,&r);
            tmp[2][1]=1;
            upd(1,1,n,l,r,tmp);
        } else if (op==3) {
            scanf("%d%d",&l,&r);
            tmp[0][2]=1;
            upd(1,1,n,l,r,tmp);
        } else if (op==4) {
            scanf("%d%d%d",&l,&r,&v);
            tmp[3][0]=v;
            upd(1,1,n,l,r,tmp);
        } else if (op==5) {
            scanf("%d%d%d",&l,&r,&v);
            tmp[1][1]=v;
            upd(1,1,n,l,r,tmp);
        } else if (op==6) {
            scanf("%d%d%d",&l,&r,&v);
            tmp[2][2]=0,tmp[3][2]=v;
            upd(1,1,n,l,r,tmp);
        } else {
            scanf("%d%d",&l,&r);
            tmp=ask(1,1,n,l,r);
            printf("%lld %lld %lld\n",tmp[0][0],tmp[0][1],tmp[0][2]);
        }
    }
    return 0;
}
2024/7/3 09:24
加载中...