【数据结构/分块/可持久化 Trie】AcWing 269. Fotile模拟赛L
2022/6/27 23:24:43
本文主要是介绍【数据结构/分块/可持久化 Trie】AcWing 269. Fotile模拟赛L,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
块乐
分析
因为这题查询的是指定区间 \([l, r]\) 的最大异或子段,我们很难不想到使用可持久化 \(\texttt{trie}\) 来搞。
然而,对于每次查询,如果单纯地使用可持久化 \(\texttt{trie}\),那么必须要枚举右端点进行查询,那么每次查询的复杂度是 \(O(n{\rm {log}} V)\)(\(V\) 为值域大小),承受不住。
在查询上可以直接优化吗?似乎做不到呢。。你会发现没有什么可用的数据结构可以对此进行优化。
那么考虑使用优雅的暴力——分块来进行操作:
- 将区间划分为 \(tot\) 块。
- 假设查询的区间为 \([l,r]\),我们对中间的整块 \([L,R]\)(这里 \([L,R]\) 为块的标号)在查询前进行了预处理,已经知道了这一部分的贡献(也就是最大异或值)是 \(f(L, R)\)。
- 那么我们只需要枚举一遍左边的非整块部分,使用上面说的可持久化 \(\texttt{trie}\) 来求最大异或值,记为 \(A\),同理右边非整块部分也这么干,结果记为 \(B\)。(这两部分的查询分别用 \(pre,suf\) 两棵树来完成即可,见代码)
- 那么答案就是 \(\max\{A, B, f(L, R)\}\)。
- 上面的操作复杂度显然是 \(O(\frac{n}{tot}\cdot {\rm log} V)\)
最后说说怎么预处理:
-
首先枚举整块,然后枚举整块内的左右端点来求这个整块的最大异或值,复杂度为 \(O(tot \cdot (\frac{n}{tot}) ^ 2)\)
这样我们就得到了 \(f(i, i)\)。
-
接下来利用递推得到 \(f(i, j)\)(其中 \(i<j\)):我们只需要枚举第 \(j\) 块的端点,然后使用可持久化 \(\texttt{trie}\) 求它和第 \(i\) 块的左端点的最大异或值即可,记贡献为 \(A\),那么递推方程就是 \(f(i, j) = \max(f(i, j-1), A)\),这一步的复杂度为 \(O(tot^2 \frac{n}{tot}{\rm log }V)\)
综上,复杂度为:\(O(\frac{n}{tot}\cdot {\rm log} V + tot \cdot (\frac{n}{tot}) ^ 2 + tot^2 \frac{n}{tot}{\rm log}V)\),如果简单地将 \({\rm log} V\) 看成是一个常数(最多 \(31\)),那么可以发现块长选取为 \(\sqrt n\) 最合适,整个算法复杂度为 \(O(n\sqrt n {\rm log} V)\)
实现
感觉我的码风应该可以被看懂
// Problem: Fotile模拟赛L // Contest: AcWing // URL: https://www.acwing.com/problem/content/description/271/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << ": " << (x) << endl #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define dwn(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back #define all(x) (x).begin(), (x).end() #define x first #define y second using pii = pair<int, int>; using ll = long long; #define int long long inline void read(int &x){ int s=0; x=1; char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();} while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); x*=s; } const int N=2e4+50, M=31, BLK=sqrt(N+1); int n, Q; int w[N]; struct LTrie{ int tr[N*M][2]; int root[N]; int s[N], mxid[N*M]; int idx; int sum(int l, int r){ return s[r]^s[l-1]; } void insert(int i, int k, int p, int q){ if(k==-1) return mxid[q]=i, void(); int val=s[i]>>k&1; if(p) tr[q][val^1]=tr[p][val^1]; tr[q][val]=++idx; insert(i, k-1, tr[p][val], tr[q][val]); mxid[q]=max(mxid[tr[q][0]], mxid[tr[q][1]]); } void build(){ mxid[0]=-1; root[0]=idx=1; insert(0, M, 0, root[0]); rep(i,1,n) s[i]^=s[i-1]; rep(i,1,n){ root[i]=++idx; insert(i, M, root[i-1], root[i]); } } int query(int u, int c, int lim){ dwn(i,M,0){ int val=c>>i&1; if(mxid[tr[u][val^1]]>=lim) u=tr[u][val^1]; else u=tr[u][val]; } return s[mxid[u]]^c; } int query(int l, int r){ // fix r and query limit >= l-1 return query(root[r], s[r], l-1); } }pre, suf; int Len; int tot; int L[BLK], R[BLK]; int id[N]; // the block id of index int f[BLK][BLK]; void init(){ tot=n/Len; rep(i,1,tot) L[i]=(i-1)*Len+1, R[i]=i*Len; if(R[tot]<n) ++tot, L[tot]=R[tot-1]+1, R[tot]=n; rep(i,1,tot) rep(j,L[i],R[i]) id[j]=i; // dp rep(i,1,tot){ int l=L[i], r=R[i]; rep(j,l,r) rep(k,j,r) f[i][i]=max(f[i][i], pre.sum(j, k)); } rep(len,2,tot){ rep(l,1,tot-len+1){ // l, r is block id int r=l+len-1; int lx=L[r], rx=R[r]; rep(i,lx,rx) f[l][r]=max(f[l][r], pre.query(L[l], i)); f[l][r]=max(f[l][r], f[l][r-1]); } } } int query(int l, int r){ int res=0; int lid=id[l], rid=id[r]; if(lid==rid){ rep(i,l,r) res=max(res, pre.query(l, i)); return res; } if(lid+1<rid) res=f[lid+1][rid-1]; rep(i,l,L[lid+1]-1) res=max(res, suf.query(n-r+1, n-i+1)); rep(i,R[rid-1]+1,r) res=max(res, pre.query(l, i)); return res; } signed main(){ cin>>n>>Q; rep(i,1,n) read(w[i]); rep(i,1,n){ pre.s[i]=w[i]; suf.s[i]=w[n+1-i]; } pre.build(), suf.build(); Len=sqrt(n+1); init(); int res=0; while(Q--){ int l, r; read(l), read(r); l=(l+res)%n+1; r=(r+res)%n+1; if(l>r) swap(l, r); cout<<(res=query(l, r))<<endl; } return 0; }
这篇关于【数据结构/分块/可持久化 Trie】AcWing 269. Fotile模拟赛L的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享