F题解 | Witcher Genshin Impact

既然大家都是线段树我就来个分块吧

#include <bits/stdc++.h>
 
using LL = long long;
using PII = std::pair<LL, LL>;

const int N = 1e5 + 10;
const int M = 330;
const int MOD = 1145141;

LL n, m, total, length, v[N], belong[N], sum[M], l[M], r[M], rnum[M]; 

void build() {
    length = sqrt(n);
    total = (n - 1)/length + 1;
    for(int i = 1; i <= total; i++) {
        l[i] = r[i - 1] + 1, r[i] = i*length;
    }
    r[total] = n;

    for(int i = 1; i <= n; i++) belong[i] = (i - 1)/length + 1;
    
    //处理每个块的和
    for(int i = 1; i <= total; i++) {
        LL all = 1;
        for(int j = l[i]; j <= r[i]; j++) {
            sum[i] = (sum[i] + v[j]*all)%MOD;
            all = (all*v[j])%MOD;
            if(j == r[i]) rnum[i] = all;
        }
    }
}

void modify(int pos, int val) {
    v[pos] = val;
    int now = belong[pos];
    sum[now] = 0;

    LL all = 1;
    for(int i = l[now]; i <= r[now]; i++) {
        sum[now] = (sum[now] + v[i]*all)%MOD;
        all = (all*v[i])%MOD;
    }
    rnum[now] = all;
}

LL query(int L, int R) {
    if(belong[L] == belong[R]) {
        LL res = 0, all = 1;
        for(int i = L; i <= R; i++) {
            res = (res + all*v[i])%MOD;
            all = (all*v[i])%MOD;
        }
        return res;
    }
    
    LL res = 0, tempr = 1;
    for(int i = L; i <= r[belong[L]]; i++) {
        res = (res + tempr*v[i])%MOD;
        tempr = (tempr*v[i])%MOD;
    }
    
    for(int i = belong[L] + 1; i <= belong[R] - 1; i++) {
        res = (res + tempr*sum[i])%MOD;
        tempr = (tempr*rnum[i])%MOD;
    }

    for(int i = l[belong[R]]; i <= R; i++) {
        res = (res + tempr*v[i])%MOD;
        tempr = (tempr*v[i])%MOD;
    }
    
    return res;
}

void solve() {
    std::cin >> n >> m;
    for(int i = 1; i <= n; i++) std::cin >> v[i];
    build();

    while(m--) {
        int op, a, b;
        std::cin >> op >> a >> b;
        if(op == 1) std::cout << query(a, b) << '\n';
        else modify(a, b);
    }
}
  
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
     
    int T = 1;;
    //std::cin >> T;
    while (T--) solve();
    return 0;
}