首页 > 代码库 > HDU 4578 线段树区间更新(确定区间操作的优先级)
HDU 4578 线段树区间更新(确定区间操作的优先级)
HDU 4578
线段树区间更新
操作有:
区间所有数add(c)
区间所有数mul(c)
区间所有数set(c)
查询有:
区间所有数的p次方和(p>= 1 && p <= 3)
关键是区间更新的三种操作的优先级的确定清楚set>mul>add
关键是:down和update中对区间的更新操作是一回事,可以写成函数方便编程
//#pragma warning (disable: 4786) //#pragma comment (linker, "/STACK:16777216") //HEAD #include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int maxn = 100010; const int MOD = 10007; #define ll rt << 1 #define rr rt << 1 | 1 int q[3][maxn << 2]; int setval[maxn << 2], add[maxn << 2], mul[maxn << 2]; void up(int rt) { for (int i = 0; i < 3; i++) q[i][rt] = (q[i][ll] + q[i][rr]) % MOD; } void down_setval(int rt, int c, int len) { int a[4]; a[1] = c; for (int i = 2; i <= 3; i++) a[i] = a[i - 1] * a[1] % MOD; for (int i = 0; i < 3; i++) q[i][rt] = a[i + 1] * len % MOD; setval[rt] = c; add[rt] = 0;/// mul[rt] = 1;/// } void down_addval(int rt, int c, int len) { int a[4]; a[1] = c; for (int i = 2; i <= 3; i++) a[i] = a[i - 1] * a[1] % MOD; q[2][rt] = q[2][rt] % MOD + a[3] * len % MOD + 3 * a[2] % MOD * q[0][rt] % MOD + 3 * a[1] % MOD * q[1][rt] % MOD; q[1][rt] = q[1][rt] % MOD + a[2] * len % MOD + 2 * a[1] % MOD * q[0][rt] % MOD; q[0][rt] = q[0][rt] + a[1] * len % MOD; for (int i = 0; i < 3; i++) q[i][rt] %= MOD; add[rt] = (add[rt] + c) % MOD; } void down_mulval(int rt, int c, int len) { int a[4]; a[1] = c; for (int i = 2; i <= 3; i++) a[i] = a[i - 1] * a[1] % MOD; for (int i = 0; i < 3; i++) q[i][rt] = (q[i][rt] * a[i + 1]) % MOD; mul[rt] = (mul[rt] * c) % MOD; add[rt] = (add[rt] * c) % MOD; } void down(int rt, int l, int r) { int m = (l + r) >> 1; if (setval[rt] != -1)///!!! { down_setval(ll, setval[rt], m - l + 1); down_setval(rr, setval[rt], r - m); setval[rt] = -1;///!!! // return ; } if (mul[rt] != 1) { down_mulval(ll, mul[rt], m - l + 1); down_mulval(rr, mul[rt], r - m); mul[rt] = 1; } if (add[rt] != 0) { down_addval(ll, add[rt], m - l + 1); down_addval(rr, add[rt], r - m); add[rt] = 0; } } void update(int L, int R, int qx, int c, int l, int r, int rt) { if (L <= l && r <= R) { if (qx == 3) down_setval(rt, c, r - l + 1); else if (qx == 1) down_addval(rt, c, r - l + 1); else down_mulval(rt, c, r - l + 1); return ; } int m = (l + r) >> 1; down(rt, l, r); if (L <= m) update(L, R, qx, c, l, m, ll); if (m < R) update(L, R, qx, c, m +1, r, rr); up(rt); } int query(int L, int R, int c,int l, int r, int rt) { if (L <= l && r <= R) return q[c - 1][rt]; int m = (l + r) >> 1; down(rt, l, r); int ret = 0; if (L <= m) ret = (ret + query(L, R, c, l, m, ll)) % MOD; if (m < R) ret = (ret + query(L, R, c, m + 1, r, rr)) % MOD; return ret; } int main () { int n, m; while (scanf("%d%d", &n, &m) == 2) { if (n + m == 0) break; CLR(q, 0); CLR(setval, -1);///!!! CLR(add, 0); for (int i = 0; i < maxn * 4; i++) mul[i] = 1; // while (m--) { int qx, x, y, c; RI(qx); RIII(x, y, c); if (qx <= 3) update(x, y, qx, c, 1, n, 1); else printf("%d\n", query(x, y, c, 1, n, 1)); } } return 0; }
另一种:
//#pragma warning (disable: 4786) //#pragma comment (linker, "/STACK:16777216") //HEAD #include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) typedef long long LL; const int INF = 1000000007; const double eps = 1e-10; const int maxn = 100010; const int MOD = 10007; #define ll rt << 1 #define rr rt << 1 | 1 int q[3][maxn << 2]; int setval[maxn << 2], add[maxn << 2], mul[maxn << 2]; void up(int rt) { for (int i = 0; i < 3; i++) q[i][rt] = (q[i][ll] + q[i][rr]) % MOD; } void down_setval(int rt, int c, int len) { int a[4]; a[1] = c; for (int i = 2; i <= 3; i++) a[i] = a[i - 1] * a[1] % MOD; for (int i = 0; i < 3; i++) q[i][rt] = a[i + 1] * len % MOD; setval[rt] = c; add[rt] = 0;/// mul[rt] = 1;/// } void down_nosetval(int rt, int a, int b, int len) { int ta[4], tb[4]; ta[1] = a, tb[1] = b; for (int i = 2; i <= 3; i++) ta[i] = ta[i - 1] * ta[1] % MOD, tb[i] = tb[i - 1] * tb[1] % MOD; q[2][rt] = ta[3] * q[2][rt] % MOD + tb[3] * len % MOD + 3 * ta[2] % MOD * tb[1] % MOD * q[1][rt] % MOD + 3 * ta[1] % MOD * tb[2] % MOD * q[0][rt] % MOD; q[2][rt] %= MOD; q[1][rt] = ta[2] * q[1][rt] % MOD + tb[2] * len % MOD + 2 * ta[1] % MOD * tb[1] % MOD * q[0][rt] % MOD; q[1][rt] %= MOD; q[0][rt] = ta[1] * q[0][rt] % MOD + tb[1] * len % MOD; q[0][rt] %= MOD; if (setval[rt] != -1)///!!! { setval[rt] = setval[rt] * a + b; setval[rt] %= MOD; } else { mul[rt] = mul[rt] * a; add[rt] = add[rt] * a + b; mul[rt] %= MOD; add[rt] %= MOD; } } void down(int rt, int l, int r) { int m = (l + r) >> 1; if (setval[rt] != -1)///!!! { down_setval(ll, setval[rt], m - l + 1); down_setval(rr, setval[rt], r - m); setval[rt] = -1;///!!! add[rt] = 0; mul[rt] = 1; } else { int a = mul[rt], b = add[rt]; down_nosetval(ll, a, b, m - l + 1); down_nosetval(rr, a, b, r - m); add[rt] = 0; mul[rt] = 1; } } void update(int L, int R, int qx, int c, int l, int r, int rt) { if (L <= l && r <= R) { if (qx == 3) down_setval(rt, c, r - l + 1); else { int a = 1, b = 0; if (qx == 1) b = c; else a = c; down_nosetval(rt, a, b, r - l + 1); } return ; } int m = (l + r) >> 1; down(rt, l, r); if (L <= m) update(L, R, qx, c, l, m, ll); if (m < R) update(L, R, qx, c, m +1, r, rr); up(rt); } int query(int L, int R, int c,int l, int r, int rt) { if (L <= l && r <= R) return q[c - 1][rt]; int m = (l + r) >> 1; down(rt, l, r); int ret = 0; if (L <= m) ret = (ret + query(L, R, c, l, m, ll)) % MOD; if (m < R) ret = (ret + query(L, R, c, m + 1, r, rr)) % MOD; return ret; } int main () { int n, m; while (cin >> n >> m) { if (n + m == 0) break; CLR(q, 0); CLR(setval, -1);///!!! CLR(add, 0); REP(i, maxn << 2) mul[i] = 1; // while (m--) { int qx, x, y, c; RI(qx); RIII(x, y, c); if (qx <= 3) update(x, y, qx, c, 1, n, 1); else cout << query(x, y, c, 1, n, 1) % MOD << endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。