## [$T125847$ 【模板】动态开点线段树](https://www.luogu.com.cn/problem/T125847) ### 题目背景 **注意：请注意时间限制是800ms 请使用较快的输入输出** **注意：空间限制是128MB 请不要开long long** **时限在std的2.5倍以上** ### 题目描述 有一个有$1000000000$个数的初始值全为$0$的区间，你要进行两种操作： 将某区间每一个数加上 $x$ 求出某区间每一个数的和 #### 输入格式 第一行包含一个正整数$x,p$，表示操作个数和模数 接下来$m$行，每行包含3或4个整数，`1 x y z`表示将$[x,y]$内每个数加$z$，`2 x y`表示求$[x,y]$内每个数的和对$p$取模的结果 #### 输出格式 输出包含若干行，为操作$2$的结果 #### 样例输入 #1 ``` 5 1000000 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4 ``` #### 样例输出 #1 ``` 0 2 8 ``` #### 样例输入 #2 ``` 10 19260817 1 374820971 712098346 1098272 1 162434628 326475424 152364 1 273453274 501278493 2029843 2 109087934 309864534 2 45934570 707590802 1 928572468 937453858 7572566 1 284984549 305943757 4828364 1 429483545 988734685 20060802 2 450934587 584905959 2 857346545 932847348 ``` #### 样例输出 #2 ``` 884893 3287340 9797062 5474275 ``` #### 提示 $1≤m≤100000$ $1≤x≤y≤1000000000$，$1≤z≤10^{8}$，$1≤p≤10^{8}$ ### $Code$ ```cpp {.line-numbers} #include using namespace std; const int N = 1e7 + 10; typedef long long LL; int m, p; // m个输入，p是模的值 // 动态开点线段树 #define ls tr[u].l #define rs tr[u].r #define mid ((l + r) >> 1) struct Node { int l, r; int sum, add; } tr[N << 1]; int root, idx; // 根节点编号，初始值是0，通过modify创建，第1个，也就是根root=1 // idx:节点号游标 // 汇总统计信息 void pushup(int u) { tr[u].sum = (LL(tr[ls].sum) + LL(tr[rs].sum)) % p; } void pushdown(int &u, int l, int r) { if (tr[u].add == 0) return; // 如果没有累加懒标记，返回 if (ls == 0) ls = ++idx; // 左儿子创建 if (rs == 0) rs = ++idx; // 右儿子创建 // 懒标记下传 tr[ls].sum = (LL(tr[ls].sum) + LL(tr[u].add) * (mid - l + 1) % p) % p; // 区间和增加=懒标记 乘以 区间长度 tr[rs].sum = (LL(tr[rs].sum) + LL(tr[u].add) * (r - mid) % p) % p; tr[ls].add = (LL(tr[ls].add) + LL(tr[u].add)) % p; // 加法的懒标记可以叠加 tr[rs].add = (LL(tr[rs].add) + LL(tr[u].add)) % p; // 清除懒标记 tr[u].add = 0; } // 区间修改 void modify(int &u, int l, int r, int L, int R, int v) { if (u == 0) u = ++idx; // 动态开点 if (l >= L && r <= R) { // 如果区间被完整覆盖 tr[u].add = (LL(tr[u].add) + v) % p; // 加法的懒标记可以叠加 tr[u].sum = (LL(tr[u].sum) % p + LL(v) * (r - l + 1) % p) % p; // 区间和增加=懒标记 乘以 区间长度 // cout << tr[u].add << " " << tr[u].sum << endl; return; } if (l > R || r < L) return; // 如果没有交集 // 下传懒标记 pushdown(u, l, r); // 分裂 modify(ls, l, mid, L, R, v), modify(rs, mid + 1, r, L, R, v); // 汇总 pushup(u); } // 区间查询 LL query(int u, int l, int r, int L, int R) { if (l >= L && r <= R) return tr[u].sum % p; // 如果完整命中，返回我的全部 if (l > R || r < L) return 0; // 如果与我无关,返回0 pushdown(u, l, r); return (query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R)) % p; } int main() { #ifndef ONLINE_JUDGE freopen("T125847.in", "r", stdin); #endif // 加快读入 ios::sync_with_stdio(false), cin.tie(0); cin >> m >> p; while (m--) { int op, x, y, k; cin >> op >> x >> y; if (op == 1) { cin >> k; modify(root, 1, 1000000000, x, y, k); } else cout << query(root, 1, 1000000000, x, y) % p << endl; } return 0; } ``` ### 总结 - 空间限制是$128MB$ 请不要开`long long`,但是，在两个大的整数进行加法或乘法计算时，一定要使用`LL`进行强制转换，然后再取模，否则溢出出现负数会让你调试的怀疑人生，不要问我是怎么知道的，我才不告诉你调了一个小时也没检查出错误来~ ```cpp {.line-numbers} if (l >= L && r <= R) { // 如果区间被完整覆盖 tr[u].add = (LL(tr[u].add) + v) % p; // 加法的懒标记可以叠加 tr[u].sum = (LL(tr[u].sum) % p + LL(v) * (r - l + 1) % p) % p; // 区间和增加=懒标记 乘以 区间长度 // cout << tr[u].add << " " << tr[u].sum << endl; return; } ``` - 在实在没有办法的情况下，采用`count`输出一个每个变量的值是一个非常好的调试办法，不要用$IDE$的调试功能，远不如这个来的直接！当我突然发现`tr[u].sum`出现负数时，我才意识到是我的转`LL`+取模的代码出现了溢出，原来的代码是这样写的： ```cpp {.line-numbers} if (l >= L && r <= R) { // 如果区间被完整覆盖 tr[u].add = (LL(tr[u].add) + v) % p; // 加法的懒标记可以叠加 tr[u].sum = (LL(tr[u].sum) % p + LL(v * (r - l + 1) % p)) % p; // 区间和增加=懒标记 乘以 区间长度 return; } ``` 结果$WA$的我怀疑人生~,看到错误了没：`v`没在转换成`LL`前就和另一个数字进行乘法操作，导致直接溢出，再来转化为`LL`也是与事无补 ~ - 动态开点的线段树，一般的上限是个数，比如本题的个数是$1000000000$,就可以直接写上这个，不怕数组装不下，因为操作数一共就$1e5$个，其实也可以使用离散化解决，但我太懒了，就不管了~