菜啊，不会 100 pts，但是 zhq 讲得真好
先看另一道题：luogu P1631 序列合并
简述题意：两个长度为 n 的单调不下降序列 A, B，在 A, B 中各取一个数相加，共有 $n^2$ 种可能，求最小的 n 个
数据范围：$n\leq 10^5$
将所有可能是答案的数放进一个小根堆中，贪心地想，如果一对数 $A_i, B_j$ 被还不是当前堆最小的一对数，那么 $A_{i+1}, B_j$ 或 $A_i, B_{j + 1}$ 也不可能是答案（因为序列单调不下降），而当 $A_i, B_j$ 被当作第 k 个答案取出的时候，则 $A_{i+1}, B_{j}$ 和 $A_i, B_{j+1}$ 也就有可能作为第 k+1 个答案，所以将这两个加入堆中
以这样的思路完成：
1 // P1631 序列合并 2 3 #include <ctime> 4 #include <cmath> 5 #include <cstdio> 6 #include <cstring> 7 #include <cstdlib> 8 #include <iostream> 9 #include <algorithm> 10 #include <vector> 11 #include <queue> 12 #define inf 100010 13 #define INF 0x7fffffff 14 #define ll long long 15 16 namespace chiaro{ 17 18 template <class I> 19 inline void read(I &num){ 20 num = 0; char c = getchar(), up = c; 21 while(c < ‘0‘ || c > ‘9‘) up = c, c = getchar(); 22 while(c >= ‘0‘ && c <= ‘9‘) num = (num << 1) + (num << 3) + (c ^ ‘0‘), c = getchar(); 23 up == ‘-‘ ? num = -num : 0; return; 24 } 25 template <class I> 26 inline void read(I &a, I &b) {read(a); read(b);} 27 template <class I> 28 inline void read(I &a, I &b, I &c) {read(a); read(b); read(c);} 29 30 struct Node { 31 int i, j; 32 int dis; 33 inline bool operator < (const Node& other) const { 34 return dis > other.dis; 35 } 36 Node() {i = j = dis = 0;} 37 Node(int a, int b, int c) {i = a, j = b, dis = c;} 38 }; 39 40 int n; 41 int a[inf], b[inf]; 42 std::priority_queue <Node, std::vector <Node> > P; 43 44 inline int main(){ 45 read(n); 46 for(int i = 1; i <= n; i++) read(a[i]); 47 for(int i = 1; i <= n; i++) read(b[i]); 48 P.push((Node){1, 1, a[1] + b[1]}); 49 for(int i = 1; i <= n; i++) { 50 Node x = P.top(); P.pop(); 51 printf("%d ", x.dis); 52 P.push((Node){x.i, x.j + 1, a[x.i] + b[x.j + 1]}); 53 if(x.j == 1) P.push((Node){x.i + 1, x.j, a[x.i + 1] + b[x.j]}); 54 } 55 return 0; 56 } 57 58 } 59 60 signed main(){ return chiaro::main();}
再看另一道题：【NOI2010】超级钢琴
简述题意：给定一个长度为 n 的序列，要求从中找去 k 个不同区间（区间大小不小于 L, 不大于 R），将 k 个区间全部求和，要求和最大
数据范围：$n,k\leq 5\times 10^5$
显然需要维护一个前缀和 sum[] ，做法与上题相似
我们现在钦定一个点 x 作为左端点，那么右端点就大致在 $[x + L - 1, x + R - 1]$ 中，那么我们其实就是要在这个区间内找一个 sum 最大的点
区间 RMQ 问题，没有修改，上 ST 表
当我们找到了一个答案后 $(x, y)$，那么有哪些可能使下一个答案？
还是让左端点 x 固定，则答案存在的区间被 y 点割成了两个部分，即 $[x + L - 1, y - 1]$ 与 $[y + 1, x + R - 1]$
就将这两个区间 ST 求完最大值后加入堆
1 // P2048 [NOI2010]超级钢琴 2 3 #include <ctime> 4 #include <cmath> 5 #include <cstdio> 6 #include <cstring> 7 #include <cstdlib> 8 #include <iostream> 9 #include <algorithm> 10 #include <vector> 11 #include <queue> 12 #define inf 500010 13 #define INF 0x7fffffff 14 #define ll long long 15 16 namespace chiaro{ 17 18 template <class I> 19 inline void read(I &num){ 20 num = 0; char c = getchar(), up = c; 21 while(c < ‘0‘ || c > ‘9‘) up = c, c = getchar(); 22 while(c >= ‘0‘ && c <= ‘9‘) num = (num << 1) + (num << 3) + (c ^ ‘0‘), c = getchar(); 23 up == ‘-‘ ? num = -num : 0; return; 24 } 25 template <class I> 26 inline void read(I &a, I &b) {read(a); read(b);} 27 template <class I> 28 inline void read(I &a, I &b, I &c) {read(a); read(b); read(c);} 29 30 struct Node { 31 int x; 32 int l, r; 33 int p; 34 Node() {x = l = r = p = 0;} 35 Node(int a, int b, int c, int d) {x = a, l = b, r = c, p = d;} 36 }; 37 38 int n, k; 39 int L, R; 40 int a[inf]; 41 ll sum[inf]; 42 43 ll table[24][inf]; 44 int log[inf]; 45 46 std::priority_queue <Node, std::vector <Node> > P; 47 48 inline bool operator < (const Node& now, const Node& other) { 49 return (sum[now.p] - sum[now.x - 1]) < (sum[other.p] - sum[other.x - 1]); 50 } 51 52 #define max(a, b) (sum[(a)] > sum[(b)] ? (a) : (b)) 53 54 inline void build(int n) { 55 for(int i = 2; i <= n; i++) log[i] = log[i >> 1] + 1; 56 for(int i = 1; i <= n; i++) table[0][i] = i; 57 for(int j = 1; (1 << j) <= n; j++) { 58 for(int i = 1; i + (1 << j) - 1 <= n; i++) { 59 int x = table[j - 1][i]; 60 int y = table[j - 1][i + (1 << (j - 1))]; 61 table[j][i] = max(x, y); 62 } 63 } 64 } 65 66 inline int query(int l, int r) { 67 int k = log[r - l + 1]; 68 int x = table[k][l]; 69 int y = table[k][r - (1 << k) + 1]; 70 return max(x, y); 71 } 72 73 inline int main(){ 74 read(n, k); read(L, R); 75 for(int i = 1; i <= n; i++) read(a[i]); 76 for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; 77 build(n); 78 for(int i = 1; i <= n; i++) { 79 if(i + L - 1 > n) break; 80 int l = i + L - 1; 81 int r = std::min (n, i + R - 1); 82 P.push((Node){i, l, r, query(l, r)}); 83 } 84 ll ans = 0; 85 while(k--) { 86 Node x = P.top(); P.pop(); 87 ans += sum[x.p] - sum[x.x - 1]; 88 if(x.p != x.l) P.push((Node){x.x, x.l, x.p - 1, query(x.l, x.p - 1)}); 89 if(x.p != x.r) P.push((Node){x.x, x.p + 1, x.r, query(x.p + 1, x.r)}); 90 } 91 printf("%lld\n", ans); 92 return 0; 93 } 94 95 } 96 97 signed main(){ return chiaro::main();}
做完上述两题后就来看这道题：【十二省联考2019】异或粽子
简述题意：给定长度为 n 的数列，要求找 k 个不同的区间，将区间内的数全部亦或，然后将 k 区间的答案求和，要求和最大
数据范围：$n\leq 5\times 10^5, k \leq 2\times 10^5$
zhq：看到亦或和最大就应该想到 Trie
我做题少不要欺负我
与上题相似的维护前缀亦或 sum[]
与上题相似，不过为了下文方便我们固定右端点 x，然后在 $[0, x - 1]$ 中找一个点 y，使得 $sum[x]\ xor\ sum[y]$ 最大可用 Trie 轻易维护
但是我们要固定找的范围（即 $[0, x - 1]$），所以需要用可持久化 Trie
可是我不会可持久化 Trie
那就不固定范围，可以发现对于一对答案点 $(x,y)$， 当 x 被固定的时候会最先找到 y 点， 当 y 被固定的时候 x 最先被找到，所以一对点一定且只会被找到两次
又因为 $sum[x]\ xor\ sum[y] = sum[y]\ xor\ sum[x]$，那么我们不妨找 2k 个答案，然后将最后答案除以二
那当我们固定一个点 x 找到了第 k 大的区间，那么以 x 点为固定点也就有可能成为第 k+1 大的区间，所以再找第 k+1 大的点并加入堆
代码：
1 #include <ctime> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <iostream> 7 #include <algorithm> 8 #include <vector> 9 #include <queue> 10 #define inf 500010 11 #define INF 0x7fffffff 12 #define ll long long 13 #define int unsigned int 14 15 namespace chiaro{ 16 17 template <class I> 18 inline void read(I &num){ 19 num = 0; char c = getchar(), up = c; 20 while(c < ‘0‘ || c > ‘9‘) up = c, c = getchar(); 21 while(c >= ‘0‘ && c <= ‘9‘) num = (num << 1) + (num << 3) + (c ^ ‘0‘), c = getchar(); 22 up == ‘-‘ ? num = -num : 0; return; 23 } 24 template <class I> 25 inline void read(I &a, I &b) {read(a); read(b);} 26 template <class I> 27 inline void read(I &a, I &b, I &c) {read(a); read(b); read(c);} 28 29 struct Node { 30 int id; 31 int rk; 32 int dis; 33 Node(int a, int b, int c) {id = a, rk = b, dis = c;} 34 35 inline bool operator < (const Node& other) const { 36 return dis < other.dis; 37 } 38 }; 39 40 struct Trie { 41 int ch[2]; 42 int size; 43 }; 44 45 int n, k; 46 ll ans; 47 int a[inf]; 48 int sum[inf]; 49 Trie t[inf * 32]; 50 std::priority_queue <Node, std::vector <Node> > P; 51 52 #define next (t[now].ch[bit]) 53 #define xnext (t[now].ch[bit ^ 1]) 54 55 inline void insert(int x) { 56 static int index = 0; 57 int now = 0; 58 for(int i = 31; i < 32; i--) { 59 int bit = (x >> i) & 1; 60 ++t[now].size; 61 if(next == 0) next = ++index; 62 now = next; 63 } 64 ++t[now].size; 65 return; 66 } 67 68 inline int query(int x, int rk) { 69 int ans = 0; 70 int now = 0; 71 for(int i = 31; i < 32; i--) { 72 int bit = (x >> i) & 1; 73 if(xnext == 0) now = next; 74 else if(rk <= t[xnext].size) now = xnext, ans |= (1u << i); 75 else rk -= t[xnext].size, now = next; 76 } 77 return ans; 78 } 79 80 inline int main(){ 81 read(n, k); k <<= 1; 82 for(int i = 1; i <= n; i++) read(a[i]); 83 for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i]; 84 for(int i = 0; i <= n; i++) insert(sum[i]); 85 for(int i = 0; i <= n; i++) P.push((Node){i, 1, query(sum[i], 1)}); 86 for(int i = 1; i <= k; i++) { 87 Node x = P.top(); P.pop(); 88 ans += x.dis; 89 if(x.rk >= n) continue; 90 P.push((Node){x.id, x.rk + 1, query(sum[x.id], x.rk + 1)}); 91 } 92 printf("%lld\n", ans >> 1); 93 return 0; 94 } 95 96 } 97 98 signed main(){ return chiaro::main();}
zhq 讲的真好，学到许多
原文：https://www.cnblogs.com/Chiaro/p/problem-yihuozongzi.html
