Hash表板子

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
ull rx=1e9+7;
ll rand(ll x,ll y){rx*=998244353;return rx%(y-x+1)+x;}
const int M=1e6+5,N=2e5+5;
ll rv[M],a[N],s[N];
int n,la[N],ed[M];
namespace fk{
	const int big=400,C=N/big+5,M=20007;
	int id[N],tot,l[C],r[C];
	ll v[N],lz[C];
	struct node{
		int head[M],d[big+5],d0;
		int nxt[big+5],cnt[big+5],num;
		ll h[big+5];
		void init(){
			for(int i=1;i<=num;i++)cnt[i]=0;
			for(int i=1;i<=d0;i++)head[d[i]]=0;
			num=d0=0;
		}
		int&operator[](ll n){
			int y=n%M;
			for(int p=head[y];p;p=nxt[p])
				if(h[p]==n)return cnt[p];
			if(head[y]==0)d[++d0]=y;
			nxt[++num]=head[y];head[y]=num;h[num]=n;
			return cnt[num];
		}
		int find(ll n){
			int y=n%M;
			for(int p=head[y];p;p=nxt[p])
				if(h[p]==n)return cnt[p];
			return 0;
		}
	}c[C];
	void make(int x){
		c[x].init();
		for(int i=l[x];i<=r[x];i++)c[x][v[i]]++;
	}
	void build(){
		for(int i=1;i<=n;i++){
			if(i%big==1)l[++tot]=i;
			id[i]=tot;r[tot]=i;
		}
		for(int i=1;i<=n;i++)v[i]=s[i-1];
		for(int i=1;i<=tot;i++)make(i);
	}
	void cha_b(int x,int y,ll z){
		for(int i=x;i<=y;i++)v[i]^=z;
		make(id[x]);
	}
	void change(int x,int y,ll z){
		if(id[x]==id[y])return cha_b(x,y,z);
		cha_b(x,r[id[x]],z);cha_b(l[id[y]],y,z);
		for(int i=id[x]+1;i<=id[y]-1;i++)lz[i]^=z;
	}
	int qry_b(int x,int y,ll z){
		z^=lz[id[x]];int s=0;
		for(int i=x;i<=y;i++)s+=(z==v[i]);
		return s;
	}
	int ask(int x,int y,ll z){
		if(id[x]==id[y])return qry_b(x,y,z);
		int s=qry_b(x,r[id[x]],z)+qry_b(l[id[y]],y,z);
		for(int i=id[x]+1;i<=id[y]-1;i++)s+=c[i].find(z^lz[i]);
		return s;
	}
}
int main(){
	freopen("odd.in","r",stdin);
	freopen("odd.out","w",stdout);
	for(int i=0;i<=1e6;i++)rv[i]=rand(1,1ll<<60);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		la[i]=ed[a[i]];ed[a[i]]=i;
		a[i]=rv[a[i]];s[i]=s[i-1]^a[i];
	}
	fk::build();
	ll ans=0;
	for(int i=1;i<=n;i++){
		fk::change(la[i]+1,i,a[i]);
		ans+=fk::ask(1,i,s[i]);
	}
	printf("%lld\n", ans);
}

/*
大致思路：
考场差点就会了，我好菜啊
考虑给每个点一个权值，然后我们统计一个前缀异或和
那么一个区间[l,r]满足条件当且仅当s[r]^s[l-1]=（在这个区间中出现的过的数的权值的异或和)
将后面那个东西设为p[i]
考虑移动右端点r，对于每个左端点维护s[l-1]^{p[l]，然后直接查询满足s[r]=s[l-1]}p[l]的l的个数即可
s[l-1]直接初始赋上，然后对于一个新的r
它会对pre[r]+1~r这段区间的p[i]造成一个a[r]的贡献，其中pre[i]是a[r]上一次出现的位置
这东西是个区间异或，考虑用分块维护
直接用map求出现次数会T，每个块都维护一个hash表
*/

原文地址：http://www.cnblogs.com/CHK666/p/16862718.html