異或序列（莫隊）

題目原址

使用莫隊算法即可

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm> 
using namespace std;
#define maxn 1000010
#define ll long long int
typedef struct nodee{
    int l,r;
    int indx;
}node;
node maze[maxn];
ll n,m,k,summ;
ll sum[maxn],num[maxn];
ll a[maxn],vis[maxn];
bool cmp(node u,node v)
{
    if(vis[u.l]==vis[v.l])
        return u.r<v.r;
    return vis[u.l]<vis[v.l];
}
void pls(ll x)
{
    summ+=num[x^k];
    num[x]++;
}
 
void min(ll x)
{
    num[x]--;
    summ-=num[x^k];
}
int main()
{	
	int i,l,r;
    scanf("%lld %lld %lld",&n,&m,&k);
    
    memset(num,0,sizeof(num));
    num[0]=1;
    memset(vis,0,sizeof(vis));
    memset(sum,0,sizeof(sum));
    
    int temp=(int)sqrt((double)n);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]=a[i]^a[i-1];
        vis[i]=i/temp;
    }
    for(i=1; i<=m; i++){
        scanf("%lld %lld",&maze[i].l,&maze[i].r);
        maze[i].indx=i;
    }
  
    sort(maze+1,maze+1+m,cmp);
    
	l=1;  r=0;  summ=0;
    for(i=1; i<=m; i++){
    	while(r<maze[i].r){
    		r++;
    		pls(a[r]);
		} 
		while(r>maze[i].r){
			min(a[r]);
			r--;
		}
		while(l<maze[i].l){
			min(a[l-1]);
			l++;
		}
		while(l>maze[i].l){
			l--;
			pls(a[l-1]);
		}
		
        sum[maze[i].indx]=summ;
    }
    
    for(i=1; i<=m; i++)
        printf("%lld\n",sum[i]);
 
    return 0;
}