【题解】Luogu P2023 【[AHOI2009]维护序列】

背景

可能是我的写法太$DT$了,然后$int64$都溢出了,所以我就用了 __$int128$,当然$NOIP$不能用这玩意。

分析

就是线段树区间乘,区间加,查询区间和
关于怎样传标记他们说的很清楚。
其实我还是很好奇为啥我$int64$会溢出。

代码

$int128$需要手动写输入输出$I/O$,就是一个快读快输就好了。

#include<cstdio>

typedef __int128 int128;
const int128 MAXN = 1000000 + 6;
int128 MOD,A[MAXN];

inline int128 read(){
    int128 op = 1,ans = 0;char s = getchar();
    while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
    while(s >= '0' && s <= '9'){ans = ans * 10 + s - '0';s = getchar();}
    return ans *= op;
}
void print(int128 x){
    if(x < 0){putchar('-');x = -x;}
    if(x > 9){print(x / 10);}
    putchar(x % 10 + '0');
}
void println(int128 x){print(x);putchar('\n');}

class SegmentTree{
    public:int128 l,r;
    public:int128 sum,add,mul;
};SegmentTree t[MAXN * 4];

inline int128 L(int128 x){return x << 1;}
inline int128 R(int128 x){return x << 1 | 1;}
inline void maintain(int128 p){t[p].sum = (t[L(p)].sum + t[R(p)].sum) % MOD;}

void build(int128 p,int128 l,int128 r){
    t[p].l = l;t[p].r = r;
    t[p].add = 0;t[p].mul = 1;
    if(l == r){t[p].sum = A[l];return;}
    int128 mid = (l + r) >> 1;
    build(L(p),l,mid);
    build(R(p),mid + 1,r);
    maintain(p);
}

inline void spread(int128 p){
    int128 mid = (t[p].l + t[p].r) >> 1;
    t[L(p)].sum = (t[L(p)].sum * t[p].mul + t[p].add * (mid - t[p].l + 1)) % MOD;
    t[R(p)].sum = (t[R(p)].sum * t[p].mul + t[p].add * (t[p].r - mid)) % MOD;
    t[L(p)].mul = (t[L(p)].mul * t[p].mul) % MOD;
    t[R(p)].mul = (t[R(p)].mul * t[p].mul) % MOD;
    t[L(p)].add = (t[L(p)].add * t[p].mul + t[p].add) % MOD;
    t[R(p)].add = (t[R(p)].add * t[p].mul + t[p].add) % MOD;
    t[p].mul = 1;t[p].add = 0;
}

void change(int128 p,int128 l,int128 r,int128 d,bool op){
    if(op == true){//mul
        if(l <= t[p].l && r >= t[p].r){
            t[p].add = t[p].add * d;
            t[p].mul = t[p].mul * d;
            t[p].sum = t[p].sum * d;
            return;
        }
        spread(p);
        int128 mid = (t[p].l + t[p].r) >> 1;
        if(l <= mid) change(L(p),l,r,d,op);
        if(r > mid) change(R(p),l,r,d,op);
        maintain(p);
    }else{
        if(l <= t[p].l && r >= t[p].r){
            t[p].add = t[p].add + d;
            t[p].sum = (t[p].sum + d * (t[p].r - t[p].l + 1));
            return;
        }
        spread(p);
        int128 mid = (t[p].l + t[p].r) >> 1;
        if(l <= mid) change(L(p),l,r,d,op);
        if(r > mid) change(R(p),l,r,d,op);
        maintain(p);
    }
}

int128 ask(int128 p,int128 l,int128 r){
    if(l <= t[p].l && r >= t[p].r) return t[p].sum;
    spread(p);
    int128 ans = 0,mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) ans += ask(L(p),l,r);
    if(r > mid) ans += ask(R(p),l,r);
    return ans;
}

int main(){
    int128 n = read();MOD = read();
    for(int128 i = 1;i <= n;i++) A[i] = read();
    build(1,1,n);
    int128 m = read(),op,l,r;int128 d;
    while(m--){
        op = read(),l = read(),r = read();
        if(op == 1) d = read(),change(1,l,r,d,true);
        else if(op == 2) d = read(),change(1,l,r,d,false);
        else println(ask(1,l,r) % MOD);
    }

    return 0;
}