.netcore网站开发,确定网站主题,十大ps培训机构,网站建设题目正题
题目链接:https://www.luogu.com.cn/problem/P4735 题目大意 nnn个数字#xff0c;有操作
在末尾加入一个数字xxx询问[l,r][l,r][l,r]范围内的一个ppp使得ap⊕ap1⊕ap2...⊕an⊕xa_p\oplus a_{p1}\oplus a_{p2}...\oplus a_{n}\oplus xap⊕ap1⊕ap2...⊕an⊕x的…正题
题目链接:https://www.luogu.com.cn/problem/P4735 题目大意
nnn个数字有操作
在末尾加入一个数字xxx询问[l,r][l,r][l,r]范围内的一个ppp使得ap⊕ap1⊕ap2...⊕an⊕xa_p\oplus a_{p1}\oplus a_{p2}...\oplus a_{n}\oplus xap⊕ap1⊕ap2...⊕an⊕x的值最大。 解题思路
定义sis_isi表示前缀异或和那么其实答案就是求一个在[l−1,r−1][l-1,r-1][l−1,r−1]中的一个sps_psp使得sn⊕x⊕sps_n\oplus x\oplus s_psn⊕x⊕sp最大。 后面两个是固定的考虑如何求sps_psp我们知道我们可以用TrieTrieTrie求静态的异或和最大就是按照反方向路径行走。所以这里我们用类似于主席树的方法建立一颗可持久化TrieTrieTrie。
不同的是我们对于每个节点要维护一个最大的上限lastlastlast也就是这个节点的子树中包含的最后的插入的节点这样询问时我们从rtrrt_rrtr出发避开lastllastllastl的节点就好了。
时间复杂度O(28n)O(28n)O(28n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5e510,W28;
int n,m,cnt,a[N],rt[N];
int ch[N*40][2],last[N*40];
int Insert(int x,int k,int val,int id){int ycnt;if(k0){last[y]id;return y;}int c(valk)1;ch[y][c^1]ch[x][c^1];ch[y][c]Insert(ch[x][c],k-1,val,id);last[y]max(last[ch[y][0]],last[ch[y][1]]);return y;
}
int Ask(int x,int k,int val,int lim){if(k0)return last[x];int c((valk)1)^1;if(last[ch[x][c]]lim)return Ask(ch[x][c],k-1,val,lim);return Ask(ch[x][c^1],k-1,val,lim);
}
int main()
{scanf(%d%d,n,m);memset(last,-1,sizeof(last));rt[0]Insert(0,W,0,0);for(int i1;in;i){scanf(%d,a[i]);a[i]^a[i-1];rt[i]Insert(rt[i-1],W,a[i],i);}while(m--){char op[4];int l,r,x;scanf(%s,op);if(op[0]Q){scanf(%d%d%d,l,r,x);l--;r--;int ansAsk(rt[r],W,a[n]^x,l);printf(%d\n,a[n]^x^a[ans]);}else{scanf(%d,a[n]);a[n]^a[n-1];rt[n]Insert(rt[n-1],W,a[n],n);}}return 0;
}
