首页 > 代码库 > bzoj4103异或运算 可持久化trie树
bzoj4103异或运算 可持久化trie树
要去清华冬令营了,没找到2016年的题,就先坐一坐15年的。
因为n很小,就按照b串建可持久化trie树,a串暴力枚举。
其他的直接看代码。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read() { int x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘){f=-1;}ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int data[20000005],ch[20000005][2],cnt; inline int newnode(){return ++cnt;} inline void insert(int x,int id) { int i,c,k; for(i=30;i>=0;i--) { c=(id>>i)&1; k=ch[x][c]; ch[x][c]=newnode(); data[ch[x][c]]=data[k]; ch[ch[x][c]][0]=ch[k][0]; ch[ch[x][c]][1]=ch[k][1]; data[x]++;x=ch[x][c]; } data[x]++; } int n,m,q; int a[1005],b[300005]; int x1,x2,y1,y2,k; int p[1005][2]; inline int query(int k) { int i,j,sum,c,res=0; for(i=30;i>=0;i--) { sum=0; for(j=x1;j<=x2;j++) { c=(a[j]>>i)&1;c^=1; sum+=data[ch[p[j][1]][c]]-data[ch[p[j][0]][c]]; } if(sum>=k) { for(j=x1;j<=x2;j++) { c=(a[j]>>i)&1;c^=1; p[j][1]=ch[p[j][1]][c]; p[j][0]=ch[p[j][0]][c]; } res+=1<<i; } else { for(j=x1;j<=x2;j++) { c=(a[j]>>i)&1; p[j][1]=ch[p[j][1]][c]; p[j][0]=ch[p[j][0]][c]; } k-=sum; } } return res; } int root[300005]; int main() { n=read(),m=read(); int i,j; for(i=1;i<=n;i++) a[i]=read(); for(i=1;i<=m;i++) b[i]=read(); for(i=1;i<=m;i++) { root[i]=newnode(); data[root[i]]=data[root[i-1]]; ch[root[i]][0]=ch[root[i-1]][0]; ch[root[i]][1]=ch[root[i-1]][1]; insert(root[i],b[i]); } q=read(); for(i=1;i<=q;i++) { x1=read(),x2=read(),y1=read(),y2=read();k=read(); for(j=x1;j<=x2;j++) { p[j][0]=root[y1-1];p[j][1]=root[y2]; } printf("%d\n",query(k)); } return 0; }
bzoj4103异或运算 可持久化trie树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。