D - Parity game离散化+带权并查集

废话之我是**

带权并查集，和那个how many answer are wrong差不多，冲啊！
嗯？怎么写了一发后mle了？？？？
哦哦，原来还要离散化！
嗯？怎么离散化后还是wa?
哦哦，原来我的ans没有初始值为k（每一个询问都是正确的情况）
呜呜呜我好傻

题意

就是给你一个n（0<n<1e9）,n是一个由0、1组成的串的长度，给你k次询问，每次询问l, r, ch，ch==“even”/“odd”， 意思就是l–r这个区间的和为偶数或者奇数。问每次询问是否是正确的（与前面的询问发生冲突的就是错误的），如果是错误的且是第一次错误，就输出上次一询问是第几次询问…

带权并查集啊，只不过n太大了，存不下，得先离散化

总结

离散化，将数存到数组里，排序 -> 去重 -> 二分查找
排序就sort就行，去重有个 unique函数，二分查找就lower_bound
然后就老带权并查集了，区间的左端要开区间（类似前缀似的 喵喵喵？？）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define pq priority_queue
#define eps 1e-10
#define PI acos(-1.0)
int n, k;
int ok, ans;
int cnt;
const int maxn = 20005;
char s[maxn][10];
int L[maxn];
int a[maxn], b[maxn], fa[maxn], d[maxn];


int find(int x){
    
	if(x == fa[x])
		return x;
	int tp = find(fa[x]);
	d[x] ^= d[fa[x]];
	return fa[x] = tp;
}

void init(){
    
	for(int i = 0; i <= cnt; i++){
    
		fa[i] = i;
		d[i] = 0;
	}
}

void Union(int x, int y, int val){
    
	int fx = find(x);
	int fy = find(y);
	if(fx != fy){
    
		fa[fy] = fx;
		d[fy] ^= d[x] ^ d[y] ^ val;
	}
	else{
    
		if(d[y] ^ d[x] != val && !ok){
    
// cout << x << " " << y << " " << val <<endl;
			ok = 1;
		}
	}
}

int main(){
    
	scanf("%d", &n);
	scanf("%d", &k);
	for(int i = 1; i <= k; i++){
    
		scanf("%d %d", &a[i], &b[i]);
		L[cnt++] = a[i] - 1;
		L[cnt++] = b[i];
		scanf(" %s", s[i]);
	}
	sort(L, L + cnt);
	init();
	cnt = unique(L, L + cnt) - L;
	ans = k;
	for(int i = 1; i <= k; i++){
    
		int l = lower_bound(L, L +  cnt, a[i] - 1) - L;
		int r = lower_bound(L, L + cnt, b[i]) - L;
		if(s[i][0] == 'e'){
    
			Union(l, r, 0);
			if(ok){
    
				ans = i - 1;
				break;
			}
		}
		else{
    
			Union(l, r, 1);
			if(ok){
    
				ans = i - 1;
				break;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}