题解 P5283 【[十二省联考2019]异或粽子】

这里给出一个考场**玄学**做法。 首先我们~~可以看出这题可持久化01trie可做~~。 然后我们可以发现对于答案中的每个区间，~~它必然有一个右端点（废话）~~ 既然每个答案有一个右端点，那么我们只要能对所有可行的右端点，得到可行的最大区间异或和就行了。 把序列弄成前缀异或和，当trie树深度为d时，这可以O(nd)搞出来，O(nlogn)塞进堆里。 当我们弹出一个区间和时，对于这个右端点，它的答案需要更新成次大的区间异或和。 这很明显可以通过trie树节点上记录size，直接求第k大搞定。 ~~但是其实可以不这么做。~~ 当在trie树上找最大异或值时，其实就是贪心在搜索树上找到一条链的过程。 但是这里的贪心和一般的贪心不同，很明显，每层只有两个决策，并且在树深度较深处转向，比更浅处更优。 ~~这不就是dfs的回溯吗~~ 所以我们可以开一个n * d的二维数组作为堆栈。每在堆中取出一个区间异或和，我们就对对应的右端点回溯。 但是看这个数据：3 2 2 ... 它的异或前缀和是：3 1 3 ... 这个3，在异或前缀和里出现了不止一次，但对于trie树，它只出现了一次，如果对于某个右端点，3需要对答案提供不止一次的贡献，喜提Wa。（~~大样例都过不去但是可以80分）~~ ~~好办，维护计数器~~ ### MLE 为啥会mle呢，因为这个做法需要保留对于每个右端点，取答案时trie树上走的路径。算上堆栈，就相当于是开了1颗半可持久化trie。 而且还要记录路径上每个节点走过方向，又是一个2nd大小的bool数组。 如果给trie树维护计数器，那么内存又会增加4 * n * d/1024/1024≈123MB。加上之前那些乱七八糟的东西和系统栈，内存十分爆炸，~~1G刚好不够。~~ ~~凉凉？~~ ~~不，强行续命！~~ 我们可以发现这个做法并不需要维护节点的子树size，只需要对叶子结点维护计数器，而叶子节点没有左右儿子，这不是明显可以 一**var**多用。 如果是数组写的trie树，那么题已经做完了。 ~~指针只能凉凉？~~ ~~其实还能再续。~~ 虽然在c++（或者说oi版c++）中，变量是有类型的，但是我们还有强制类型转换！反正都是一段内存，而且指针保存的东西本质上就是个作为偏移量的整数，怎么不能当计数器？ (int)p->son[0]=1;//ce 貌似强制类型转换返回的是常量，不能做左值。~~所以还是凉凉？~~ 这个东西其实是可以绕过去的。 我们可以把它写成这样* (int*)(&p->son[0])=1; 这样(int*)(&p->son[0])是一个指向变量的常量指针，指向的变量是(p->son[0])（当做int处理），这不就可以做修改了吗。 然后就可以 ~~写出来ac代码~~ 强行续命80分代码了。 时间复杂度考虑trie树深度应该是O(nd+mlogn+(m-n)d),本题d=64. 跑的奇慢，交之前或许需要洗把脸。 ```cpp // luogu-judger-enable-o2 //01trie #include <cstdio> #include <queue> #include <algorithm> using namespace std; #define reg register typedef long long vt; const int kmaxn = 500000 + 5; const int kmaxd = 65;//64//<< 0-63 const int kmaxs = 62 * 500000; struct node { node* son[2]={nullptr,nullptr}; }; node mempool[kmaxs]; int mpt; node* root[kmaxn]; node* stk[kmaxn][kmaxd]; bool hsh[kmaxn][kmaxd][2]; short st[kmaxn]; int n, k; vt arr[kmaxn]; inline node* alloc_node() { return mpt<kmaxs ? &mempool[mpt++] : new node; } void insert(node* lp, node*& p, vt v, int pos = 62) { p = alloc_node(); if (lp)*p = *lp; if (pos<0) { *(int*)(&(p->son[0])) = *(int*)(&(p->son[0]))+1; //*(int*)(&p->son[0])=1; // cout<<(int)p->son[0]<<endl; return; } bool b = (v)&(((vt)1) << pos); insert((lp ? lp->son[b] : nullptr), p->son[b], v, pos - 1); } vt init(node* p, vt v, int num, int pos = 62) { stk[num][++st[num]] = p; if (pos<0)return 0; bool b = !((v)&(((vt)1) << pos)); if (p->son[b]) { hsh[num][pos][b] = true; return (((vt)1) << pos) + init(p->son[b], v, num, pos - 1); } else { hsh[num][pos][!b] = true; return init(p->son[!b], v, num, pos - 1); } } //priority_queue<pair<vt,int>> q; struct unit { vt v; int cnt, pos; unit(vt _v = 0, int c = 0, int p = 0) :v(_v), cnt(c), pos(p) { }; inline const bool operator<(const unit& u)const { return v<u.v; } }; /*class pq{ public: unit u[kmaxn]; int len=0; inline void push(const unit& v) { u[len++]=v; push_heap(u,u+len); } inline unit pop() { pop_heap(u,u+len); return u[--len]; } }q;*/ priority_queue<unit> q; int dfs(int pos, vt v, vt& ans) { short& tail = st[pos]; reg bool dir = false; reg bool b = false; reg int dp = 0; while (tail>1) { dir = (stk[pos][tail - 1]->son[1] == stk[pos][tail]); dp = 63 - (--tail); b = (v)&(((vt)1) << (dp)); if (b != dir) ans -= (((vt)1) << (dp)); dir = !dir; if (!hsh[pos][dp][dir] && stk[pos][tail]->son[dir])//find { break; } hsh[pos][dp][0] = hsh[pos][dp][1] = 0; } while (tail<64)//9223372032559812379 { dp = 63 - tail; dir = !((v)&(((vt)1) << dp)); if (stk[pos][tail]->son[dir] && !hsh[pos][dp][dir])//have and can turn { ans += (((vt)1) << (dp)); } else { dir = !dir; } hsh[pos][dp][dir] = true; stk[pos][tail + 1] = stk[pos][tail]->son[dir]; ++tail; } return *(int*)(&(stk[pos][tail]->son[0])); } inline void solve() { unsigned long long ans = 0; reg int pos = 0; reg int c = 0; vt t = -1; unit temp; while (k) { // printf("k %d\n", k); //temp=q.pop(); temp = q.top(); q.pop(); t = temp.v; c = min(temp.cnt, k); k -= c; pos = temp.pos; ans += t*c; c = dfs(pos, arr[pos], t); if (t >= 0) q.push(unit(t, c, pos)); t = -1; } printf("%lld\n", ans); } int main() { // freopen("xor19.in", "r", stdin); scanf("%d%d", &n, &k); // printf("%d %d\n", n, k); insert(nullptr, root[0], 0); vt t=0; for (reg int i = 1; i <= n; ++i) { //cin>>arr[i]; scanf("%lld", &arr[i]); arr[i] ^= arr[i - 1]; insert(root[i - 1], root[i], arr[i]); t = init(root[i], arr[i], i); // printf("%d cnt %d\n", i, *(int*)(void*)(&(stk[i][64]->son[0]))); q.push(unit(t, *(int*)(&(stk[i][64]->son[0])), i)); } solve(); // while (1); return 0; } ``` ~~幸好考场上死也没想出来需要维护计数器，否则MLE 80变60就很惨了（80变0更惨）~~