洛谷 P3373 线段树2——致卑微的我

洛谷 P3373 线段树2——致卑微的我

谨以此片博客记录一上午的debug

#include <iostream>
#include <algorithm>
#include <cstdio>#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1using namespace std;const int MAXN = 1e5 + 5;struct Node{long long v, mul, add;
}node[MAXN << 4];int p;
long long a[MAXN];void pushUp(int rt){node[rt].v = (node[rt << 1].v + node[rt << 1 | 1].v) % p;
}void pushDown(int l, int r, int rt){int m = (l + r) >> 1;node[rt << 1].v = (node[rt << 1].v * node[rt].mul + node[rt].add * (m - l + 1)) % p;node[rt << 1 | 1].v = (node[rt << 1 | 1].v * node[rt].mul + node[rt].add * (r - m)) % p;node[rt << 1].mul = (node[rt << 1].mul * node[rt].mul) % p;node[rt << 1 | 1].mul = (node[rt << 1 | 1].mul * node[rt].mul) % p;node[rt << 1].add = (node[rt << 1].add * node[rt].mul + node[rt].add) % p;node[rt << 1 | 1].add = (node[rt << 1 | 1].add * node[rt].mul + node[rt].add) % p;node[rt].mul = 1;node[rt].add = 0;return;
}void Build(int l, int r, int rt){node[rt].mul = 1;node[rt].add = 0;if(l == r){node[rt].v = a[l] % p;return;}int m = (l + r) >> 1;Build(lson);Build(rson);pushUp(rt);
}void updateMul(int L, int R, int k, int l, int r, int rt){
//    if(r < L || R < l){
//        return;
//    }if(L <= l && r <= R){node[rt].v = (node[rt].v * k) % p;node[rt].mul = (node[rt].mul * k) % p;node[rt].add = (node[rt].add * k) % p;return;}pushDown(l, r, rt);int m = (l + r) >> 1;//pushDown(l, r, rt);if(L <= m){updateMul(L, R, k, lson);}if(R > m){updateMul(L, R, k, rson);}pushUp(rt);
}void updateAdd(int L, int R, int k, int l, int r, int rt){
//    if(r < L || R < l){
//        return ;
//    }if(L <= l && r <= R){node[rt].add = (node[rt].add + k) % p;node[rt].v = (node[rt].v + k * (r - l + 1)) % p;return;}pushDown(l, r, rt);int m = (l + r) >> 1;if(L <= m){updateAdd(L, R, k, lson);}if(R > m){updateAdd(L, R, k, rson);}pushUp(rt);
}int query(int L, int R, int l, int r, int rt){if(r < L || R < l){return 0;}if(L <= l && r <= R){return node[rt].v;}pushDown(l, r, rt);int m = (l + r) >> 1;int ans = 0;if(L <= m){ans += query(L, R, lson) % p;}if(R > m){ans += query(L, R, rson) % p;}return ans % p;
}int main()
{int n, m;scanf("%d %d %d", &n, &m, &p);for(int i = 1; i <= n; ++i){scanf("%lld", &a[i]);}Build(1, n, 1);while(m--){int op;int x, y;long long k;scanf("%d", &op);if(op == 1){scanf("%d %d %lld", &x, &y, &k);updateMul(x, y, k, 1, n, 1);continue;}if(op == 2){scanf("%d %d %lld", &x, &y, &k);updateAdd(x, y, k, 1, n, 1);continue;}else{scanf("%d %d", &x, &y);printf("%dn", query(x, y, 1, n, 1));continue;}}return 0;
}