題目鏈接

雖然退役了，但因為Codewars想升個級所以寫了兩個題，xs

與這個一樣的題，感覺還是挺妙的。

\(Description\)
給定長為\(n\)的序列\(A_i\)，求有多少個區間，滿足區間中所有數的出現次數為奇數。
\(n\leq 2\times10^5,\ A_i\leq 10^5\)。

\(Solution\)
為每個數賦值一個隨機權值\(val_i\)。則區間所有數出現次數為奇數，等價于 區間所有權值的異或和 等于 區間出現過的權值的異或和。
設\(i\)為當前計算區間的右端點，\([j,i]\)所有權值異或和為\(f_j\)，\([j,i]\)出現過的權值異或和為\(g_j\)，以\(i\)為右端點的合法區間數為\(\sum_{j\leq i}[f_j=g_j]\)。記\(las_x\)為\(x\)上次出現過的位置。
那么每次枚舉前綴\([1,i]\)時，操作即為：對\(f_1, ..., f_i\)異或\(val_{A_i}\)，對\(g_{las_{A_i}+1}, ..., g_i\)異或\(val_{A_i}\)，求\(f_j=g_j\)即\(f_j\ \mathbb{xor}\ g_j=0\)的個數。
令\(h_j=f_j\ \mathbb{xor}\ g_j\)，則操作即為：對\(h_1, ..., h_{las_{A_i}}\)異或\(val_{A_i}\)，求\(h_j=0\)的個數。

所以就是：區間異或一個值，求區間等于0的數的個數。可以分塊。
記\(cnt[b][k]\)表示塊\(b\)中數\(k\)的出現次數，則每次修改，對整塊更新\(tag[b]\)，對零散部分將改變的值從\(cnt[b]\)里刪掉并更新；每次詢問，對整塊查\(cnt[b][tag[b]]\)，對零散部分暴力查值為\(tag[b]\)的個數。

\(cnt[b]\)可以用map，也可以哈希（如果用哈希，在更新\(cnt[b]\)時不妨直接將整個\(cnt[b]\)哈希表清空。哈希表不太好刪除）。
復雜度\(O(n\sqrt n\log n)\)或\(O(n\sqrt n)\)。

#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}

typedef long long LL;
typedef unsigned long long ull;
const int N=2e5+5,M=1e5+5,B=450,B_size=450;
const int mod=2099;

int las[M],bel[N],L[B],R[B];
ull val[M],seq[N],tag[B];
std::mt19937_64 Rand(19511016);

struct Hash
{
	int Enum,Time,time[mod+2],H[mod+2],nxt[B_size+2],cnt[B_size+2];
	ull to[B_size+2];

	inline void AE(int u,ull v,int t)
	{
		to[++Enum]=v, nxt[Enum]=H[u], cnt[Enum]=t, H[u]=Enum;
	}
	void Clear()
	{
		++Time, Enum=0;
//		memset(H,0,sizeof H);
	}
	void Init(int v)
	{
		Clear();
		Get_head(0), AE(0, 0, v);//注意在插入0前，更新0的表頭！其實應該用Insert(0)去插入。
	}
	int Get_head(int x)
	{
		return time[x]==Time?H[x]:(time[x]=Time,H[x]=0);
	}
	int Query(ull v)
	{
		for(int i=Get_head(v%mod); i; i=nxt[i])
			if(to[i]==v) return cnt[i];
		return 0;
	}
	void Insert(ull v)
	{
		for(int i=Get_head(v%mod); i; i=nxt[i])
			if(to[i]==v) return void(++cnt[i]);
		AE(v%mod, v, 1);
	}
}cnt[B];

void Update(int p,ull v)
{
	if(!p) return;
	int b=bel[p];
	for(int i=1; i<b; ++i) tag[i]^=v;
	
	cnt[b].Clear();
	for(int i=L[b]; i<=p; ++i) cnt[b].Insert(seq[i]^=v);
	for(int i=R[b]; i>p; --i) cnt[b].Insert(seq[i]);
}
int Query(int p)
{
	int b=bel[p], ans=0; ull v=tag[b];
	for(int i=1; i<b; ++i) ans+=cnt[i].Query(tag[i]);
	for(int i=L[b]; i<=p; ++i) ans+=(seq[i]==v);
	return ans;
}
template<std::size_t S>
LL solve(std::array<int,S> A)//注意A下標從0開始！
{
	int n=A.size();
	for(int i=1; i<=n; ++i) seq[i]=0, las[A[i-1]]=0;
	for(int i=1; i<=n; ++i) if(!val[A[i-1]]) val[A[i-1]]=Rand();

	for(int i=1; i<=n; ++i) bel[i]=(i-1)/B_size+1;
	int tot=bel[n];
	for(int i=1; i<=tot; ++i) L[i]=(i-1)*B_size+1, R[i]=i*B_size;
	R[tot]=std::min(R[tot], n);

	for(int i=1; i<=tot; ++i) tag[i]=0, cnt[i].Init(R[i]-L[i]+1);

	LL ans=0;
	for(int i=1; i<=n; ++i)
		Update(las[A[i-1]],val[A[i-1]]), ans+=Query(i), las[A[i-1]]=i;
	return ans;
}

int main()
{
	std::array<int, 27> A2 = {6,1,7,4,6,7,1,4,7,1,4,6,6,7,4,1,6,4,7,1,4,5,3,2,1,6,9};
	printf("%lld\n",solve(A2));//114
	std::array<int, 15> A = {2, 5, 2, 3, 6, 7, 8, 23, 23, 13, 65, 31, 3, 4, 3};
	printf("%lld\n",solve(A));//53
	

	return 0;
}