USACO22OPEN-Silver C

前言（Front talk)

$\qquad$比较简单。（甚至想把这个题的前言删掉）

网址（Website）

$\qquad$洛谷： USACO22OPEN COW Operations S

$\qquad$SPOJ：题目详情 - COW Operations - Super

$\qquad$SPOJ：题解 - COW Operations - Super

题目（Problem）

$Bessie$ 找到了一个长度不超过 $2 \cdot 10^5$ 且仅包含字符 ‘C’，’O’ 和 ‘W’ 的字符串 $s$。她想知道是否可以使用以下操作将该字符串变为单个字母 ‘C’（她最喜欢的字母）：

选择两个相邻相等的字母并将其删除。
选择一个字母，将其替换为另外两个字母的任一排列。

求出这个字符串本身的答案对 $Bessie$ 而言并不足够，所以她想要知道 $s$ 的 $Q$（$1\le Q\le 2\cdot 10^5$）个子串的答案。

输入格式（Input）

输入的第一行包含 $s$。

第二行包含 $Q$。

以下 $Q$ 行每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le |s|$，其中 $|s|$ 表示 $s$ 的长度）。

输出格式（Output）

输出一个长为 $Q$ 的字符串，如果第 $i$ 个子串可以被转变则第 $i$ 个字符为 ‘Y’，否则为 ‘N’。

样例（Example）

样例输入

样例输出

YNNNYN

提示（Notice）

【样例解释】

第一个询问的答案是「是」，因为 s 的第一个字符已经等于 ‘C’。

第五个询问的答案是「是」，因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 ‘C’：

   OW
-> CWW
-> C

这个样例字符串 COW 的其他子串均不能被转变为 ‘C’。

【测试点性质】

测试点 $2-4$ 满足 $|s|\le 5000$ 以及 $Q\le 5000$。
测试点 $5-11$ 没有额外限制。

题解（Solution）

容易得到几个性质：

任两个字母可以交换
任两个不同字母可以合成一个字母
任两个相等字母可以抵消

然后直接记录三个字母的前缀数量，到时候直接差分求字母数，$mod\ 2$ 后判断剩下的能不能组成字母 $C$ 即可。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
inline int input(){int x;return cin>>x,x;}
const int N = 201234;
char a[N];
int n,q;

int c[N],o[N],w[N];

inline bool check(int l,int r){
	int C=(c[r]-c[l-1])%2;
	int O=(o[r]-o[l-1])%2;
	int W=(w[r]-w[l-1])%2;
	if(C==1 && O==0 && W==0) return true;
	if(C==0 && O==1 && W==1) return true;
	return false;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("cowoper");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>(a+1)>>q;
	n=strlen(a+1);
	For(i,1,n){
		c[i]=c[i-1],o[i]=o[i-1],w[i]=w[i-1];
		if(a[i]=='C') c[i]++;
		if(a[i]=='O') o[i]++;
		if(a[i]=='W') w[i]++;
	}
	while(q--){
		int l=input(),r=input();
		cout<<(check(l,r)?'Y':'N');
	}return 0;
}