传送门

文章目录

• 题意：
• 思路：

题意：

思路：

看到异或的话，很容易想到用01trie来贪心的搞，但是这个题涉及区间问题，直接搞的话需要将$[l,r]$的数都插入trie里面，这样的复杂度显然是不能接受的，但是我们可以借助01trie的思路来解决这个题。
01trie原理就是从高位到低位开始，每一位都走与$b$当前位相反的数，当前为$1$就走$0$，为$0$就走$1$，这是在trie树上的时候可以这样贪心，我们可以将其转换成值域上，定义$ans$初始值为$0$，让后从高到低看$b$的每一位，每次都看是否能找到与当前位相反的数存在，当然这是一个范围，比如当前$b$为$1$，那么就查询$[ans-x,ans-x+(1<<i)-1]$，否则就查询$[ans-x+(1<<i),ans-x+(1<<(i+1))-1]$，减$x$是因为原题加了$x$。
比如$b$为$0101$，当前位为$0$，那么我们应该让这一位尽可能为$1$，所以我们就查询$[1000,1111]$是否存在，如果存在的话就让$ans+=(1<<i)$，让后下一位是$1$，那么我们就查询$[ans+000,ans+011]$，让后这样继续查下去就行啦，当然要减去$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; } /**/

总结

以上是生活随笔为你收集整理的P3293 [SCOI2016]美味 主席树 + 伪01trie的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。