题解 CF703D 【Mishka and Interesting sum】

Accoty_AM · 2019-10-15 21:11:53 · 题解

发现题解没有在线算法，那我就来写一篇
首先，答案是区间不重复的数的异或和xor区间出现次数为奇数的数的异或和
我们将每个数升到二维，第一位是位置，第二维记录一个pre，表示这个数上一次出现的位置，a[i]很大我们可以把它放到哈希表里，记录它的位置。这样对于每个询问l,r每次只要统计，第一维在l-r中，第二维在0-l-1的数即可，发现没有修改，这个操作可以用主席树实现。
区间为奇数的数的异或和用一个异或前缀和就行，因为出现偶数次数的数都相互抵消掉了

代码

#include<bits/stdc++.h>
using namespace std;
namespace OI{
    #define rg register
    template <typename T>
    inline void read(T &x){
        x=0;
        static char ch;ch=getchar();
        static int f; f=0;
        while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=f?-x:x;
    }
    const int N=300005;
    int sum[N];
    int a[N],n,m;
    int xorsum[N<<5];
    int rt[N],son[N<<5][2],cnt;
    #define ls son[p][0]
    #define rs son[p][1]
    #define pls son[pre][0]
    #define prs son[pre][1]
    int head[1000004],mod=1000003,tot,nxt[N],edge[N],pre[N],second[N];
    inline void add(int x,int st){
        for(int i=head[x%mod];i;i=nxt[i]){
            if(edge[i]==x) return (void) (pre[i]=st);
        }
        nxt[++tot]=head[x%mod];
        head[x%mod]=tot;
        edge[tot]=x;
        pre[tot]=st;
    }
    inline int find(int x){
        for(int i=head[x%mod];i;i=nxt[i]){
            if(edge[i]==x) return pre[i];
        }
        return false;
    }
    inline bool check(int p){
        int len=sqrt(p);
        for(int i=2;i<=len;++i) if(!(p%i)) return false;
        return true;
    }
    int insert(int l,int r,int to,int d,int pre){
        int p=++cnt;
        ls=pls;rs=prs;
        xorsum[p]=xorsum[pre]^d;
        if(l==r) return p;
        int mid=(l+r)>>1;
        if(to<=mid) ls=insert(l,mid,to,d,pls);
        else rs=insert(mid+1,r,to,d,prs);
        return p;
    }
    int ask(int l,int r,int L,int R,int pre,int p){
        if(l==L&&r==R) return xorsum[p]^xorsum[pre];
        int mid=(l+r)>>1;
        if(L>mid) return ask(mid+1,r,L,R,prs,rs);
        if(R<=mid) return ask(l,mid,L,R,pls,ls);
        return ask(l,mid,L,mid,pls,ls)^ask(mid+1,r,mid+1,R,prs,rs);
    }
    inline void main(){
//      freopen("xor.in","r",stdin);
//      freopen("xor.out","w",stdout);
        read(n);
        for(int i=1;i<=n;++i){
            read(a[i]);
            second[i]=find(a[i]);
            add(a[i],i);
            rt[i]=insert(0,n,second[i],a[i],rt[i-1]);
            sum[i]=sum[i-1]^a[i];
        }
        read(m);
        int l,r;
        for(int i=1;i<=m;++i){
            read(l),read(r);
            printf("%d\n",ask(0,n,0,l-1,rt[l-1],rt[r])^sum[l-1]^sum[r]);
        }
    }
}
signed main(){ OI::main(); return 0;}