codeforces703D Mishka and Interesting sum（区间偶数异或）-白红宇

codeforces703D Mishka and Interesting sum（区间偶数异或）

阅读量：6269 次

发布时间：2019-06-22

本文共 1505 字，大约阅读时间需要 5 分钟。

题意：

给你一个序列，q个询问l,r

要求出l到r区间内出现偶数次的数的异或值

思路：

预处理异或前缀sum

将询问按r放入vector，存的pair<l,i>

树状数组部分有点同于求区间数的种数。

last记录每个数前一次出现的位置。

走到i时，如果a[i]出现过，那么把他上次出现的位置异或掉，再在i位置上异或上a[i]。

然后对所有以i结尾的讯问区间进行操作，这里就是异或计算了。

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate
                 
                  inline void rd(T &x){ char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-'0';c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=1e6+10;int a[N],sum[N],c[N],ans[N],n,q,l,r;vector
                  
                   
                     >eg[N];map
                    
                     last;int lowbit(int x){ return x&(-x);}int add(int i,int val){ for(;i<=n;i+=lowbit(i)) c[i]^=val;}int summ(int i){ int ret=0; for(;i>0;i-=lowbit(i)) ret^=c[i]; return ret;}int main(){ rd(n); rep(i,1,n) rd(a[i]),sum[i]=sum[i-1]^a[i]; rd(q); rep(i,1,q) { rd(l),rd(r); eg[r].pb(mkp(l,i)); } int cnt=0; rep(i,1,n) { if(last.count(a[i])) add(last[a[i]],a[i]); add(i,a[i]); last[a[i]]=i; for(int j=0;j