题目链接 1295 XOR key
可持久化tire树模版题
数组一定要开够 不然数组不够的话就容易tle 吃了两次亏
#include<bits/stdc++.h> using namespace std; #define maxn 500000 #define LL long long struct ac{ LL sum,nex[]; void init(){ sum=; memset(nex,,sizeof(nex)); } }tre[maxn*]; LL tot,root[maxn]; void init(){ memset(tre,,sizeof(tre)); tot=; memset(root,,sizeof(root)); } void add(LL x,LL y,LL &z){ z=++tot; tre[z].init(); tre[z].sum=tre[y].sum+; LL k=z; ;j>=;j--){ <<j)&x); tre[k].nex[fa^]=tre[y].nex[fa^]; tre[k].nex[fa]=++tot; k=tot; y=tre[y].nex[fa]; tre[k].sum=tre[y].sum+; } } LL query(LL l,LL r,LL x){ LL ans=; ;j>=;j--){ <<j)&x); LL ll=tre[l].nex[fa^]; LL rr=tre[r].nex[fa^]; LL z=tre[rr].sum-tre[ll].sum; if(z){ ans+=1LL*<<j; l=ll,r=rr; }else{ l=tre[l].nex[fa]; r=tre[r].nex[fa]; } } return ans; } int main(){ LL n,m; cin>>n>>m; init(); ;j<=n;j++){ long long x; scanf("%lld",&x); add(x,root[j-],root[j]); } ;j<=m;j++){ LL l,r,x; scanf("%lld%lld%lld",&x,&l,&r); printf(],x)); } }