题意：给你一个数组，初始值为零，有四种操作 （1）“1 x y c”,代表 把区间 [x,y] 上的值全部加c （2）“2 x y c”,代表 把区间 [x,y] 上的值全部乘以c （3）“3 x y c” 代表 把区间 [x,y]上的值全部赋值为c （4）“4 x y p” 代表 求区间 [x,y] 上值的p次方和1<=p<=3
题解：线段树+成段更新+多种操作
wa了一天，实在找不到哪里有问题，1次方答案是对的，但往上就错了。 等刷完成段更新的其他题再看看吧。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; //成段更新 const int mod = 10007; const int MAXN = 1e5 + 5; int sum[MAXN << 2][4], add[MAXN << 2], mult[MAXN << 2], cover[MAXN << 2]; struct Node { int l, r; int mid() { return (l + r) >> 1; } } tree[MAXN << 2]; void fadd(int rt, int c, int m) { add[rt] = (add[rt] + c) % mod; sum[rt][3] = (sum[rt][3] + (3 * c * sum[rt][2]) % mod + (3 * ((c * c) % mod) * sum[rt][1]) % mod + (((((c * c) % mod) * c) % mod) * m) % mod) % mod; sum[rt][2] = (sum[rt][2] + (2 * c * sum[rt][1]) % mod + (((c * c) % mod) * m) % mod) % mod; sum[rt][1] = (sum[rt][1] + (c * m) % mod) % mod; //int sum1 = sum[rt][1], sum2 = sum[rt][2], sum3 = sum[rt][3]; //sum[rt][1] += (c * m) % mod; //sum[rt][1] %= mod; //int tmp2 = (c * c) % mod; //sum[rt][2] += (2 * sum1 * c) % mod + (tmp2 * m) % mod; //sum[rt][2] %= mod; //int tmp3 = (tmp2 * c) % mod; //sum[rt][3] += (3 * tmp2 * sum1) % mod + (3 * c * sum2) % mod + (tmp3 * m) % mod; //sum[rt][3] %= mod; } void fmult(int rt, int c, int m) { if (mult[rt]) mult[rt] = (mult[rt] * c) % mod; else mult[rt] = c; add[rt] = (add[rt] * c) % mod; sum[rt][1] = (c * sum[rt][1]) % mod; sum[rt][2] = (((c * c) % mod) * sum[rt][2]) % mod; sum[rt][3] = (((((c * c) % mod) * c) % mod) * sum[rt][3]) % mod; //add[rt] = (add[rt] * c) % mod; //int sum1 = sum[rt][1], sum2 = sum[rt][2], sum3 = sum[rt][3]; //sum[rt][1] = (sum1 * c) % mod; //int tmp2 = (c * c) % mod; //sum[rt][2] = (sum2 * tmp2) % mod; //int tmp3 = (tmp2 * c) % mod; //sum[rt][3] = (sum3 * tmp3) % mod; } void fcover(int rt, int c, int m) { cover[rt] = c; add[rt] = mult[rt] = 0; sum[rt][1] = (c * m) % mod; sum[rt][2] = (c * sum[rt][1]) % mod; sum[rt][3] = (c * sum[rt][2]) % mod; } void PushDown(int rt, int m) { if (cover[rt]) { fcover(rt << 1, cover[rt], m - (m >> 1)); fcover(rt << 1 | 1, cover[rt], m >> 1); cover[rt] = 0; } if (mult[rt]) { fmult(rt << 1, mult[rt], m - (m >> 1)); fmult(rt << 1 | 1, mult[rt], m >> 1); mult[rt] = 0; } if (add[rt]) { fadd(rt << 1, add[rt], m - (m >> 1)); fadd(rt << 1 | 1, add[rt], m >> 1); add[rt] = 0; } } void PushUp(int rt) { sum[rt][1] = (sum[rt << 1][1] + sum[rt << 1 | 1][1]) % mod; sum[rt][2] = (sum[rt << 1][2] + sum[rt << 1 | 1][2]) % mod; sum[rt][3] = (sum[rt << 1][3] + sum[rt << 1 | 1][3]) % mod; } void build(int l, int r, int rt) { tree[rt].l = l; tree[rt].r = r; sum[rt][1] = sum[rt][2] = sum[rt][3] = add[rt] = mult[rt] = cover[rt] = 0; if (l == r) { sum[rt][1] = sum[rt][2] = sum[rt][3] = 0; return; } int m = tree[rt].mid(); build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); //PushUp(rt); } void update(int c, int l, int r, int rt, int id) { if (tree[rt].l == l && r == tree[rt].r) { if (id == 1) fadd(rt, c, r - l + 1); else if (id == 2) fmult(rt, c, r - l + 1); else fcover(rt, c, r - l + 1); return; } if (tree[rt].l == tree[rt].r) return; PushDown(rt, tree[rt].r - tree[rt].l + 1); int m = tree[rt].mid(); if (r <= m) update(c, l, r, rt << 1, id); else if (l > m) update(c, l, r, rt << 1 | 1, id); else { update(c, l, m, rt << 1, id); update(c, m + 1, r, rt << 1 | 1, id); } PushUp(rt); } int query(int l, int r, int rt, int p) { if (l == tree[rt].l && r == tree[rt].r) { return sum[rt][p]; } PushDown(rt, tree[rt].r - tree[rt].l + 1); int m = tree[rt].mid(); int res = 0; if (r <= m) res += query(l, r, rt << 1, p), res %= mod; else if (l > m) res += query(l, r, rt << 1 | 1, p), res %= mod; else { res += query(l, m, rt << 1, p), res %= mod; res += query(m + 1, r, rt << 1 | 1, p), res %= mod; } return res; } int n, m, id, x, y, c; int main() { freopen("in.txt", "r", stdin); while (~scanf("%d%d", &n, &m) && n) { build(1, n, 1); for (int i = 1; i <= m; i++) { scanf("%d%d%d%d", &id, &x, &y, &c); if (id <= 3) update(c, x, y, 1, id); else printf("%d\n", query(x, y, 1, c)); } } return 0; }