题意：有一个01串S，长度为n，一个人说出k个关于01串的回答，描述S[l~r] 中有奇数个1还是偶数个1。依次看，判断他到第几个问题都是可靠的回答。
思路：首先n很大要离散化，然后因为很容易想到如果S[l,r]为奇数，则S[1,r]为偶数,S[1,l-1]为奇数,或者S[1,r]为奇数,S[1,l-1]为偶数。如果S[l,r]为偶数，则
那两个区间奇偶性相同。所以可以用扩展域，扩展每个[1,x]的奇数和偶数两种情况，然后并查集。
#include<cstring> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<cmath> #define ll long long using namespace std; struct point { int l; int r; int ans; }query[10010]; int a[20010],fa[20010],n,m,t; void read_discrete() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { char str[5]; scanf("%d%d%s",&query[i].l,&query[i].r,str); query[i].ans=(str[0]=='o'?1:0); a[++t]=query[i].l-1; a[++t]=query[i].r; } sort(a+1,a+t+1); n=unique(a+1,a+t+1)-a-1; } int get(int k) { return fa[k]==k?k:fa[k]=get(fa[k]); } int main() { read_discrete(); for(int i=1;i<=2*n;i++) { fa[i]=i; } for(int i=1;i<=m;i++) { int x=lower_bound(a+1,a+n+1,query[i].l-1)-a; int y=lower_bound(a+1,a+n+1,query[i].r)-a; //printf("x:%d y:%d ",x,y); int x_odd=x,x_even=x+n; int y_odd=y,y_even=y+n; if(query[i].ans==0) { if(get(x_odd)==get(y_even)) { printf("%d ",i-1); return 0; } fa[get(x_odd)]=get(y_odd); fa[get(x_even)]=get(y_even); } else { if(get(x_odd)==get(y_odd)) { printf("%d ",i-1); return 0; } fa[get(x_odd)]=get(y_even); fa[get(x_even)]=get(y_odd); } } printf("%d ",m); }