題目大意：給你一個長方形矩陣，位置$i,j$上的數是$a_{i}\;xor\;b_{j}$，求某個子矩陣內第$K$大的值

最先想的是二分答案然后驗證，然而是$O(qnlogmloga_{i})$，不出意外會被卡..看完題解才恍然大悟

$01Trie$是具有二分性質的！因為每個節點最多有2個兒子！

先對$b$序列建可持久化$01Trie$，記錄一個$sum$表示當前節點的子樹內有多少個數

對于每次詢問，因為$n$很小，暴力枚舉$a$進行統計，記錄每個a當前在01Trie的位置

接下來就是在$01Trie$上二分了

按位從高到低枚舉，統計一共有多少個數這一位是1，即每個a所在$01Trie$位置 和這一位異或值為1 的子樹內，記為$tot$

如果$tot>k$，說明這一位不是1，每個$a$分別向異或值是0的地方走，然后$K-=tot$，去掉這一位填1的貢獻

反之每個$a$往異或值為1的地方走

最后輸出答案即可

#include <set> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #define N1 301000 #define N2 10201000 #define MM 100 #define ll long long #define dd double #define uint unsigned int #define mod 1000000007 #define idx(X) (X-'a') #define it multiset<node>::iterator using namespace std;int gint() {int ret=0,fh=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}return ret*fh; }uint bin[35]; int n,m; uint a[N1],b[N1],pa[N1]; int px[N1],py[N1];struct Trie{ int ch[N2][2],num[N2],root[N1],tot; int sum[N2],stk[N2],tp; void init() {root[0]=tot=1;int x=1;for(int i=30;i>=0;i--){ch[x][0]=++tot;x=ch[x][0],num[x]=1;} } void insert(int s,int rt1,int rt2,int w) {int x,y,p;y=root[rt1];x=root[rt2]=++tot;for(int i=31;i>=0;i--){p=(s&bin[i])?1:0;ch[x][p]=++tot;ch[x][p^1]=ch[y][p^1];num[ch[x][p]]=num[ch[y][p]]+w;sum[ch[x][p]]=sum[ch[y][p]];x=ch[x][p],y=ch[y][p];stk[++tp]=x;}sum[x]++,stk[tp--]=0;while(tp){x=stk[tp--];sum[x]=sum[ch[x][0]]+sum[ch[x][1]];} } uint query(int L,int R,int l,int r,int K) {int x,y,p;uint ans=0;y=l<0?0:root[l],x=root[r];int s[2],tot;for(int j=L;j<=R;j++)px[j]=x,py[j]=y;for(int i=31;i>=0;i--){s[0]=0,s[1]=0,tot=0;for(int j=L;j<=R;j++){p=(a[j]&bin[i])?1:0,s[p]++;tot+=sum[ch[px[j]][p^1]]-sum[ch[py[j]][p^1]];}if(K>tot){K-=tot;for(int j=L;j<=R;j++){p=(a[j]&bin[i])?1:0;if(num[ch[px[j]][p]]-num[ch[py[j]][p]]>0)px[j]=ch[px[j]][p],py[j]=ch[py[j]][p];else px[j]=py[j]=0;}}else{for(int j=L;j<=R;j++){p=(a[j]&bin[i])?1:0;if(num[ch[px[j]][p^1]]-num[ch[py[j]][p^1]]>0)px[j]=ch[px[j]][p^1],py[j]=ch[py[j]][p^1];else px[j]=py[j]=0;}ans|=bin[i];}}return ans; } }T;int main() {//freopen("t1.in","r",stdin);scanf("%d%d",&n,&m);for(int i=31;i>=0;i--)bin[i]=(1<<i);for(int i=1;i<=n;i++)a[i]=gint();T.init();for(int i=1;i<=m;i++)b[i]=gint(),T.insert(b[i],i-1,i,1);int Q,u,d,l,r,K;scanf("%d",&Q);for(int q=1;q<=Q;q++){u=gint(),d=gint(),l=gint(),r=gint(),K=gint();printf("%d\n",T.query(u,d,l-1,r,K));}return 0; }

?

轉載于:https://www.cnblogs.com/guapisolo/p/10031560.html

總結

以上是生活随笔為你收集整理的BZOJ 4103 [Thusc 2015]异或运算 (可持久化01Trie+二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。