【题意】给了一个序列&＃xff0c;询问[L,R]区间里面出现次数为偶数次的数的异或和。
【解题方法】仔细想了一下&＃xff0c;就是区间所有的数的异或和再异或上L,R区间里面不同的数的异或和&＃xff08;这个东西用离线线段树轻松搞定&＃xff09;。
【AC代码】
#include #include #include #include #include using namespace std;#define ll long longconst int maxn&＃61;1000010;int n,m,a[maxn],b[maxn];mapvis;struct Q{int l,r,id;bool operator<(const Q &rhs)const{return r}q[maxn];ll ans[maxn];struct node{int l,r;ll sum;}Tree[maxn<<2];void pushup(int rt){Tree[rt].sum&＃61;Tree[rt*2].sum^Tree[rt*2&＃43;1].sum;}void Build(int l,int r,int rt){Tree[rt].l&＃61;l,Tree[rt].r&＃61;r;if(l&＃61;&＃61;r){Tree[rt].sum&＃61;a[l];return ;}int mid&＃61;(Tree[rt].l&＃43;Tree[rt].r)/2;Build(l,mid,rt*2);Build(mid&＃43;1,r,rt*2&＃43;1);pushup(rt);}void update(int pos,int val,int rt){if(Tree[rt].l&＃61;&＃61;Tree[rt].r){Tree[rt].sum^&＃61;(ll)val;return ;}int mid&＃61;(Tree[rt].l&＃43;Tree[rt].r)/2;if(pos<&＃61;mid) update(pos,val,rt*2);else update(pos,val,rt*2&＃43;1);pushup(rt);}ll queryans(int L,int R,int rt){if(L&＃61;&＃61;Tree[rt].l&&Tree[rt].r&＃61;&＃61;R){return Tree[rt].sum;}int mid&＃61;(Tree[rt].l&＃43;Tree[rt].r)/2;// ll ret&＃61;0;// if(L<&＃61;mid) ret&＃43;&＃61;queryans(L,mid,rt*2);// if(mid// return ret;if(R<&＃61;mid) return queryans(L,R,rt*2);else if(L>mid) return queryans(L,R,rt*2&＃43;1);else{return queryans(L,mid,rt*2)^queryans(mid&＃43;1,R,rt*2&＃43;1);}}int main(){scanf("%d",&n);vis.clear();Build(1,n,1);memset(ans,0,sizeof(ans));memset(b,0,sizeof(b));for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) scanf("%d",&a[i]);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){b[i]&＃61;a[i];b[i]^&＃61;b[i-1];}scanf("%d",&m);for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){scanf("%d%d",&q[i].l,&q[i].r);q[i].id&＃61;i;}sort(q&＃43;1,q&＃43;m&＃43;1);//puts("success");int now&＃61;1;for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){for(;now<&＃61;q[i].r;now&＃43;&＃43;){if(vis[a[now]]) update(vis[a[now]],a[now],1);update(now,a[now],1);vis[a[now]]&＃61;now;}//cout<<(b[q[i].r]^b[q[i].l-1])<}
京公网安备 11010802041100号