【BZOJ3689】异或之 堆+可持久化Trie树
持久 异或 Trie
2023-09-11 14:15:27 时间
【BZOJ3689】异或之
Description
给定n个非负整数A[1], A[2], ……, A[n]。
对于每对(i, j)满足1 <= i < j <= n,得到一个新的数A[i] xor A[j],这样共有n*(n-1)/2个新的数。求这些数(不包含A[i])中前k小的数。
注:xor对应于pascal中的“xor”,C++中的“^”。
Input
第一行2个正整数 n,k,如题所述。
以下n行,每行一个非负整数表示A[i]。
Output
共一行k个数,表示前k小的数。
Sample Input
4 5
1
1
3
4
1
1
3
4
Sample Output
0 2 2 5 5
HINT
【样例解释】
1 xor 1 = 0 (A[1] xor A[2])
1 xor 3 = 2 (A[1] xor A[3])
1 xor 4 = 5 (A[1] xor A[4])
1 xor 3 = 2 (A[2] xor A[3])
1 xor 4 = 5 (A[2] xor A[4])
3 xor 4 = 7 (A[3] xor A[4])
前5小的数:0 2 2 5 5
【数据范围】
对于100%的数据,2 <= n <= 100000; 1 <= k <= min{250000, n*(n-1)/2};
0 <= A[i] < 2^31
题解:这不就是BZOJ2006超级钢琴吗?没做过的先去做那道题。
然后这题把超级钢琴中的ST表换成可持久化Trie树就行了。
#include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <utility> #define mp(A,B,C,D) make_pair(make_pair(A,B),make_pair(C,D)) using namespace std; typedef pair<int,int> pii; priority_queue<pair<pii,pii> > pq; const int maxn=100010; int n,m,tot; int ch[maxn*35][2],rt[maxn],siz[maxn*32],org[maxn*32],v[maxn]; void insert(int x,int y,int num) { int i,d,u; u=rt[y]=++tot; for(i=1<<30;i;i>>=1) { d=(num&i)>0; ch[u][d]=++tot,ch[u][d^1]=ch[x][d^1],u=ch[u][d],x=ch[x][d],siz[u]=siz[x]+1; } org[u]=y; } int query(int x,int y,int num) { int ret=0,i,d; for(i=1<<30;i;i>>=1) { d=(num&i)>0; if(siz[ch[y][d]]==siz[ch[x][d]]) d^=1; x=ch[x][d],y=ch[y][d]; } return org[y]; } int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } int main() { n=rd(),m=rd(); int i,a,b,c,x,y; for(i=1;i<=n;i++) v[i]=rd(),insert(rt[i-1],i,v[i]); for(i=2;i<=n;i++) pq.push(mp(-(v[i]^v[query(0,rt[i-1],v[i])]),i,1,i-1)); pii t1,t2; for(i=1;i<=m;i++) { if(i!=1) printf(" "); t1=pq.top().first,t2=pq.top().second,pq.pop(); printf("%d",-t1.first),x=t1.second,a=t2.first,b=t2.second; y=query(rt[a-1],rt[b],v[x]); if(y>a) pq.push(mp(-(v[x]^v[query(rt[a-1],rt[y-1],v[x])]),x,a,y-1)); if(y<b) pq.push(mp(-(v[x]^v[query(rt[y],rt[b],v[x])]),x,y+1,b)); } return 0; }
相关文章
- 技术分享 | 数据持久化技术(Java)
- 5 -- Hibernate的基本用法 --5 2 持久化对象的状态
- 5 -- Hibernate的基本用法 --5 1 持久化类的要求
- BZOJ 3439 Kpm的MCpassword Trie树+可持久化线段树
- redis持久化的几种方式
- ActiveMQ消息持久化存储策略
- 使用Spring Data JPA持久化数据
- SwiftUI 数据持久化之 数据coredata与文件存储的区别和优势
- 如何在 SwiftUI 中使用核心数据作为 macOS Ventura 应用程序的持久存储
- pinia持久化存储插件pinia-plugin-persist
- nuxt如何处理用户登录状态持久化:nuxtServerInit 页面渲染前的store处理
- Sentinel 规则持久化到 apollo 配置中心
- 【Redis入门笔记 07】数据库持久化
- 【功能与技巧】promethues通过记录规则持久化查询,存储rules表达式查询结果为采集指标
- Redis持久存储-AOF&RDB