题目链接： 传送门
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N = 20010; int p[N], d[N], n, m; //dis数组用于存储需要离散化的数据 vector<int>dis; struct node{ int l, r, num; }op[N]; //初始化父结点 void init() { for(int i = 1; i <= n; i++) p[i] = i; } //找到根结点 int find(int x) { if(x == p[x]) return x; int tmp = find(p[x]); d[x] ^= d[p[x]]; return p[x] = tmp; } //离散化操作 void discretize() { sort(dis.begin(), dis.end()); dis.erase(unique(dis.begin(), dis.end()), dis.end()); n = dis.size(); } //二分映射，返回对应值的下标 int map(int x) { return lower_bound(dis.begin(), dis.end(), x) - dis.begin() + 1; } int main() { cin >> n >> m; //输入数据 for(int i = 1; i <= m; i++) { char str[5]; scanf("%d%d%s", &op[i].l, &op[i].r, str); op[i].num = (str[0] == 'o' ? 1 : 0); //把下标存入dis中 dis.push_back(op[i].l - 1); dis.push_back(op[i].r); } //离散化 discretize(); //初始化 init(); //枚举操作 for(int i = 1; i <= m; i++) { //通过映射找到对应值下标 int x = map(op[i].l - 1), y = map(op[i].r); //找到根节点 int px = find(x), py = find(y); //判断两个点是否已连接 if(px == py) { //判断两点奇偶性是否符合要求（后面具体讲） if((d[x] ^ d[y]) != op[i].num) { cout << i - 1 <<endl; return 0; } //未连接则连接 } else { p[px] = py; d[px] = d[x] ^ d[y] ^ op[i].num; } } //输出结果 cout << m << endl; }这道题我的主要做法是用“边带权”并查集+散列化来做 首先讲讲散列化因为这道题数据很多(n<=10^9)，而查询不多(q <= 5000)。所以我们可以考虑把数据散列化来做。散列化的基础：看大佬博客 然后讲讲这道题目的主要思路（我用的“边带权”并查集，也可以用拓展域做），首先见到这种区间查询的题我们通常会想到前缀和。而前缀和又怎么查询主要分两种情况： 1.sum[l~r]有偶数个1：此时sum[l - 1]与sum[r]的奇偶性应该是相同的。 2.sum[l~r]有奇数个1：此时sum[l - 1]与sum[r]的奇偶性应该是不同的。 而判断奇偶性是否相同最好的方法就是把两个前缀和异或，同奇偶则为0，反之则为1。 利用这些性质我们就可以开始做题了，首先我们把这个前缀和转化为边权，即边权就是当前点的前缀和，然后把奇数操作看作1（因为此时两点边权奇偶性不同），偶数操作看作1（因为此时两点边权奇偶性相同）。接下来通过px==py判断两点是否已连通，不连通则把两点连通。连通则判断(d[x] ^ d[y]) != op[i].num，即两点边权奇偶性异或的结果与所给操作是否相符。不相符则输出最小的不满足条件的编号-1。都相符最后输出查询数。
