题目链接：Glad You Came
题意：
给定一个长度为$n$的全$0$数组，有$m$次操作，每次操作会选定一个区间$[l, r]$，给定一个$v$，使得那个区间所有小于$v$的值全部都等于$v$，求$m$次操作完之后的数组。
$n\le 10^5, m\le 10^6, \sum m \le 6\times 10^7$
题解：
一开始想到的是时间倒流法，按照区间赋值从大到小排序，然后用并查集维护区间删除，$pre[i]$表示$i$右边第一个没有被删除的位置，这样是$O(mlogn + mlogm) = O(mlogm)$，成功爆炸了。
仔细分析发现瓶颈在于这个排序，那么区间就是不能排序的。。改用线段树变成$O(mlogn)$，还是爆炸了，但是看题解有用线段树过了的，可能是我写的常数太大了。
于是研究正经解法知道是ST表。
多次修改，一次查询的ST表的实现。
其实跟线段树差不多，但是不需要一直pushdown，最后一次pushdown一遍就行了。
因为是最值，可以重复，直接st表上修改就行，每次在一半长度位置修改，然后最后统一pushdown。
代码：
1 #include <bits/stdc++.h> 2 #define Mid ((l + r) / 2) 3 #define lson (rt << 1) 4 #define rson (rt << 1 | 1) 5 using namespace std; 6 const int N = 2e5 + 1009; 7 int n, m, st[30][N], Log[N]; 8 unsigned int X, Y, Z, W; 9 unsigned int RNG61() { 10 X = X ^ (X << 11); 11 X = X ^ (X >> 4); 12 X = X ^ (X << 5); 13 X = X ^ (X >> 14); 14 W = X ^ (Y ^ Z); 15 X = Y; 16 Y = Z; 17 Z = W; 18 return Z; 19 } 20 void work() { 21 cin >> n >> m >> X >> Y >> Z; 22 for(int i = 0; i <= Log[n]; i++) 23 for(int j = 1; j <= n; j++) 24 st[i][j] = 0; 25 for(int i = 1; i <= m; i++) { 26 int l, r, v; 27 unsigned int x, y, z; 28 x = RNG61(); y = RNG61(); 29 z = RNG61(); 30 l = min((x % n) + 1, (y % n) + 1); 31 r = max((x % n) + 1, (y % n) + 1); 32 v = z % (1ull << 30); 33 int k = Log[r - l + 1]; 34 st[k][l] = max(st[Log[r - l + 1]][l], v); 35 st[k][r - (1 << k) + 1] = max(st[k][r - (1 << k) + 1], v); 36 } 37 for(int i = Log[n]; i; i--) { 38 for(int j = 1; j <= n; j++) { 39 st[i - 1][j] = max(st[i - 1][j], st[i][j]); 40 st[i - 1][j + (1 << (i - 1))] = max(st[i - 1][j + (1 << (i - 1))], st[i][j]); 41 } 42 } 43 unsigned long long ans = 0; 44 for(int i = 1; i <= n; i++) 45 ans ^= 1ull * i * st[0][i]; 46 cout << ans << endl; 47 } 48 signed main() 49 { 50 ios :: sync_with_stdio(0); 51 cin.tie(0); 52 for(int i = 2; i <= 100009; i++) Log[i] = Log[i / 2] + 1; 53 int Case; 54 cin >> Case; 55 while(Case--) work(); 56 return 0; 57 }