P5937 [CEOI 1999] Parity Game——前缀和与扩展域并查集
li_cat
·
·
个人记录
题意简述
给定m个要求，存在一个长度为n的序列满足从第1个到第R个要求，求最大的R
初步分析
首先n很大肯定要离散化
如果知道了[L,r]和[r+1,R]的奇偶性,就可以推出[L,R]的奇偶性
考虑区间dp，但是空间开不下
考虑使用map
挣扎了80pts
## 再次分析
### 以前缀和的角度思考
若$[l,r]$中1的个数为奇数
则$[1,r]$与$[1,l-1]$的奇偶性不同
偶数同理
这样，我们就**把二维的区间分散到了一维的点上**
### 用并查集维护奇偶性
**奇偶性相同与不同，可以使用扩展域并查集**
可以开一个正域和反域
反域中的元素的奇偶性与正域中是反过来的
也就是说反域中的元素和正域元素的关系都是反过来的
那么，**奇偶性不同的关系也可以由奇偶性相同来维护**了，直接用并查集
### AC Code:
```cpp
#include <bits/stdc++.h>
#define even 1
#define odd 2
using namespace std;
const int MAXN=5e3+5;
struct question{
int l,r,op;
}q[MAXN];
int n,m;
int lisan[MAXN<<1];
int erf(int x,int l,int r){
int mid;
while(l<r){
mid=(l+r+1)>>1;
if(lisan[mid]<=x) l=mid;
else r=mid-1;
}
return l;
}//
int nw;
void discretize(){
for(int i=1;i<=m;++i){
lisan[i] =q[i].l;
lisan[i+m] =q[i].r;;
}
sort(lisan+1,lisan+1+m*2);
nw=unique(lisan+1,lisan+1+m*2)-lisan-1;
for(int i=1;i<=m;++i){
q[i].l=erf(q[i].l,1,nw);
q[i].r=erf(q[i].r,1,nw);
}
}//
int fa[MAXN<<2];//扩展域并查集，正域和反域
//维护的关系是奇偶性相同
void init(){
for(int i=0;i<=m*4;++i){
fa[i]=i;
}
}//
int find(int x){
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}//
void merge(int x,int y){
x=find(x),y=find(y);
fa[x]=y;
}//
string s;
void work(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].l--;
cin>>s;
if(s=="odd") q[i].op=odd;
else q[i].op=even;
}
discretize();
init();
for(int i=1,l,r;i<=m;++i){
l=q[i].l;r=q[i].r;
if(q[i].op==even){//偶数的话奇偶性相同
if(find(l)==find(r+m*2)&&find(l+m*2)==find(r)){
printf("%d",i-1);
return ;
}
merge(l,r);
merge(l+m*2,r+m*2);
}else{
if(find(l)==find(r)&&find(l+m*2)==find(r+m*2)){
printf("%d",i-1);
return ;
}
merge(l,r+m*2);
merge(l+m*2,r);
}
}
printf("%d",m);
}//
int main(){
work();
return 0;
}
```