题意：

首先小A写了一个长度为n的01字符串，然后由小B提问小A M个问题，小B指定一个区间[l, r]然后小A回答区间内1的个数为奇数还是偶数，这个过程中小A可能会撒谎，然后题目要求你回答出找到最小的一个k使得1~k都是没有撒谎的，换句话说就是从第一个开始如果小A一旦撒谎输出前面问题的个数。

思路：

最开始拿到这道题没有啥办法，然后看了《算法进阶指南》的解法，才明白，首先我们处理的是一个区间问题，如果直接处理这个区间我们是很难写这道题的，但是题目问的与奇偶性相关所以我们能马上反应过来采用异或运算，其实异或运算的性质很类似与前缀和的，异或又称为不进位加法。

我们用s代表前这个序列的缀和。
s[l, r] 如果有偶数个1，它等价于s[l-1]与s[r]奇偶性相同。
s[]l, r[如果有奇数个1，它等价于s[l-1]与s[r]奇偶性不同。
且上述关系具有传递性，例如x和y奇偶性不同，y和z的奇偶性不同那么x和z的奇偶性相同。
而为了处理本题这种多种传递关系，我们采用“带权并查集”的方法。
设置数组d，d[x]代表的是他与fa[x]的奇偶性，如果为1表示x与fa[x]奇偶性不同，反之相同。在路径压缩时我们对x到树根上的所有边权做异或运算，就可以得到x与树根的奇偶关系。
由于本题的数据范围过大要采用离散化。

代码：

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long 
#define endl "\\n"
#define xx first
#define yy secondusing namespace std;typedef pair<int, int> PII;const int N = 2e5 + 10;int n, m, k, _;
int d[N], fa[N]; 
vector<int> arr;struct node
{int l , r, ans;
}e[N];int get(int x)
{if(x == fa[x]) return x;int root = get(fa[x]);d[x] ^= d[fa[x]];return fa[x] = root;
}signed main()
{IOS;cin >> n >> m;for(int i = 1; i <= m; i ++){string op;cin >> e[i].l >> e[i].r >> op;if(op[0] == 'o') e[i].ans = 1;else e[i].ans = 0;arr.push_back(e[i].l-1);arr.push_back(e[i].r);}arr.push_back(-1e9);sort(arr.begin(), arr.end());arr.erase(unique(arr.begin() , arr.end()) , arr.end());n = arr.size();for(int i = 0; i <= n; i ++) fa[i] = i;for(int i = 1; i <= m; i ++){int x = lower_bound(arr.begin(), arr.end(), e[i].l-1) - arr.begin();int y = lower_bound(arr.begin(), arr.end(), e[i].r) - arr.begin();int p = get(x), q = get(y);if(p != q){fa[p] = q;d[p] = d[x] ^ d[y] ^ e[i].ans;}else{if(d[x] ^ d[y] != e[i].ans){cout << i-1 << endl;return 0;}}}cout << m << endl;return 0;
}