傳送門(mén)

文章目錄

• 題意：
• 思路：

題意：

思路：

看到異或的話，很容易想到用01trie來(lái)貪心的搞，但是這個(gè)題涉及區(qū)間問(wèn)題，直接搞的話需要將$[l,r]$的數(shù)都插入trie里面，這樣的復(fù)雜度顯然是不能接受的，但是我們可以借助01trie的思路來(lái)解決這個(gè)題。
01trie原理就是從高位到低位開(kāi)始，每一位都走與$b$當(dāng)前位相反的數(shù)，當(dāng)前為$1$就走$0$，為$0$就走$1$，這是在trie樹(shù)上的時(shí)候可以這樣貪心，我們可以將其轉(zhuǎn)換成值域上，定義$ans$初始值為$0$，讓后從高到低看$b$的每一位，每次都看是否能找到與當(dāng)前位相反的數(shù)存在，當(dāng)然這是一個(gè)范圍，比如當(dāng)前$b$為$1$，那么就查詢$[ans?x,ans?x+(1<<i)?1]$，否則就查詢$[ans?x+(1<<i),ans?x+(1<<(i+1))?1]$，減$x$是因?yàn)樵}加了$x$。
比如$b$為$0101$，當(dāng)前位為$0$，那么我們應(yīng)該讓這一位盡可能為$1$，所以我們就查詢$[1000,1111]$是否存在，如果存在的話就讓$ans+=(1<<i)$，讓后下一位是$1$，那么我們就查詢$[ans+000,ans+011]$，讓后這樣繼續(xù)查下去就行啦，當(dāng)然要減去$x$，最后別忘記$an{s}^b$就行啦。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=200010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int a[N*2],root[N*2],tot; struct Node {int l,r;int cnt; }tr[N*40];void insert(int p,int &q,int l,int r,int pos,int x) {q=++tot; tr[q]=tr[p];tr[q].cnt+=x;if(l==r) return;int mid=l+r>>1;if(pos<=mid) insert(tr[p].l,tr[q].l,l,mid,pos,x);else insert(tr[p].r,tr[q].r,mid+1,r,pos,x); }int query(int p,int q,int l,int r,int ql,int qr) {int num=tr[q].cnt-tr[p].cnt;if(!num) return 0;if(l>=ql&&r<=qr) return num;int mid=l+r>>1,ans=0;if(ql<=mid) ans+=query(tr[p].l,tr[q].l,l,mid,ql,qr);if(qr>mid) ans+=query(tr[p].r,tr[q].r,mid+1,r,ql,qr);return ans; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),insert(root[i-1],root[i],0,100000,a[i],1);while(m--){int b,x,l,r; scanf("%d%d%d%d",&b,&x,&l,&r);int ans=0;for(int i=17;i>=0;i--){if(b>>i&1) { if(query(root[l-1],root[r],0,100000,ans-x,ans-x+(1<<i)-1)==0) ans+=(1<<i); }else { if(query(root[l-1],root[r],0,100000,ans-x+(1<<i),ans-x+(1<<(i+1))-1)>0) ans+=(1<<i); }}printf("%d\n",ans^b);}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的P3293 [SCOI2016]美味 主席树 + 伪01trie的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。