[数据结构与算法]洛谷-美好的一天-(莫队+异或性质)

美好的一天

题意：
就是给你一个字符串和m查询，每次问你一段区间l到r中有多少个子区间的字符按一定顺序排列后是否可以组成一个回文串。

思考：
看到组成回文串，就和之前过的一样就是，出现次数为奇数的字母最多只有一个。可以直接维护26个字母出现的次数当然也可以维护一个26位的二进制，如果这一位是1那么就是这个字幕出现的次数位奇数。如果只是查询一段区间就好了，直接维护每个单词出现的次数，cnt全局变量维护就行了，当然也可以维护一个26位的全局变量也行。但是这里是每次查询一个区间的所有子区间的合法个数，其实仔细思考一下，如果先对字母维护前缀异或和，对于查询[l,r]的状态就是va[r]^va[l-1]。所以从[l-1,r]中选择两个位置是否可以满足va[b]异或va[a]等于0或者等于2的多少次方。等于0代表每一位出现都是偶数次，2的某次方就是某个单词出现的次数是奇数。所以分析到这里就很明显了，还有就是add函数怎么写，其实对于多了一个值x，那么对答案的贡献就是里面等于x的有多少个，或者x异或2的某次方有多少个。第二个的意思就是异或后比如位t,那么再异或一次x那么就变成了2的某次方是满足的。

代码：

struct Node{
	int l,r;
	int id;
}node[N];

int T,n,m,k;
int va[N];
int pos[N],cnt[(1ll<<26)+5],siz;
int anw[N],ans;

bool cmp(Node A,Node B)
{
	if(pos[A.l]!=pos[B.l]) return pos[A.l]<pos[B.l];
	return A.r<B.r;	
}

void add(int x)
{
	ans += cnt[va[x]]; //等于我的有多少个
	cnt[va[x]]++;
	for(int i=0;i<26;i++)
	{
		ans += cnt[va[x]^(1ll<<i)]; //这个值va[x]^(1ll<<i)再^一次va[x]，就变成了2的多少次方就是合法的。
	}
}

void sub(int x)
{
	cnt[va[x]]--; //先删去再减去贡献，因为不能算他自己.
	ans -= cnt[va[x]];
	for(int i=0;i<26;i++)
	{
		ans -= cnt[va[x]^(1ll<<i)];
	}
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		va[i] = (1ll<<(ch-'a'));
		va[i] ^= va[i-1];
	}
	siz = 3*sqrt(n); //有时候如果卡时间了，可以让siz变大一点
	for(int i=1;i<=n;i++) pos[i] = i/siz;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		node[i] = {a,b,i};
	}
	sort(node+1,node+1+m,cmp);
	int l = 1,r = 0;
	for(int i=1;i<=m;i++)
	{
		while(l<node[i].l-1) sub(l++);
		while(l>node[i].l-1) add(--l);
		while(r<node[i].r) add(++r);
		while(r>node[i].r) sub(r--);
		anw[node[i].id] = ans;
	}
	for(int i=1;i<=m;i++) cout<<anw[i]<<"\n";
	return 0;
}

总结：
多多思考。