AcWing239. 奇偶游戏

思路

s i = a 1 + a 2 + ⋯ + a i s_{i} = a_{1} + a_{2} +\dots +a_{i} si=a1+a2++ai 前i个数中1的个数

s [ l − r ] s[l-r] s[lr]中有奇数个1

   ⟺    \iff s r − s l − 1 s_{r} - s_{l-1} srsl1为奇数

   ⟺    \iff s r s_{r} sr s l − 1 s_{l-1} sl1奇偶性不同

偶数个1    ⟺    \iff s r s_{r} sr s l − 1 s_{l - 1} sl1奇偶性相同


小A和小B在玩一个游戏。

首先,小A写了一个由0和1组成的序列S,长度为N。

然后,小B向小A提出了M个问题。

在每个问题中,小B指定两个数 l 和 r,小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如,小A曾经回答过 S[1~3] 中有奇数个1, S[4~6] 中有偶数个1,现在又回答 S[1~6] 中有偶数个1,显然这是自相矛盾的。

请你帮助小B检查这M个答案,并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k,使得01序列S满足第1 ~ k个回答,但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N,表示01序列长度。

第二行包含一个整数M,表示问题数量。

接下来M行,每行包含一组问答:两个整数l和r,以及回答“even”或“odd”,用以描述S[l~r] 中有偶数个1还是奇数个1。

输出格式

输出一个整数k,表示01序列满足第1k个回答,但不满足第1k+1个回答,如果01序列满足所有回答,则输出问题总数量。

数据范围

N ≤ 109 , M ≤ 10000 N≤109,M≤10000 N109,M10000

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 20050;

unordered_map<int, int>s;
int n, m;
int p[N], d[N];

int get(int x) {
   
	if (s.count(x) == 0)s[x] = ++n;
	return s[x];
}

int Find(int x) {
   
	if (x != p[x]) {
   
		int root = Find(p[x]);
		d[x] ^= d[p[x]];
		p[x] = root;
	}
	return p[x];
}
int main() {
   
	cin >> n >> m;
	n = 0;
	for (int i = 1;i < N;++i)p[i] = i;
	int res = m;

	for (int i = 1;i <= m;++i) {
   
		int a, b;
		string op;
		cin >> a >> b >> op;
		a = get(a - 1), b = get(b);

		int t = 0; //偶数
		if (op == "odd")t = 1; //奇数
		int pa = Find(a), pb = Find(b);

		if (pa == pb) {
   
			if ((d[a] ^ d[b]) != t) {
   
				res = i - 1;
				break;
			}
		}
		else {
   
			p[pa] = pb;
			d[pa] = d[a] ^ d[b] ^ t;
		}
	}
	cout << res << endl;
}