POJ1733-离散化+带权并查集

Description

Input

Output

Sample Input

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Sample Output

3

题目大意： 给你一串长度为n的01串，给你m个操作，每次操作为判断子串[x,y]内1的个数为奇数还是偶数，求x表示前x个操作没有矛                    

                   盾，第x+1个操作与前面的相矛盾（除了全部都没有矛盾）

题目思路：一开始看到这个题没看懂题目意思，还是英语太渣了，后面看了其他大佬们的博客才真正知道题意，然后想了会并没有                     

                    想到用并查集怎么做，然后又去看别人的博客 写到一个模型才恍然大悟，[x,y]区间的1的个数其实可以表示为                    

                    sum(y)-sum(x-1)，是不是很像树状数组啊？，其实是并查集，这样就可以联系并查集了，

                   区间x,y 就可以换成 x-1,y 了 ，比如 1 2 e  3 4 o 5 6 e 1 6 e 去过不转换的话 1 6 与 3 4 就没有联系了，转换后的话就是                     

                   0 2 e 2 4 o 4 6 e 0 6 e这样就可以用带权并查集做了，至于数据范围离散化下就ok了

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

const int maxn = 10050;
int pre[maxn],a[maxn],rk[maxn];
struct st{
    int l,r;
    char q[10];
}s[maxn];
int n,m;

int get(int x){
    if(x!=pre[x]){
        int tmp = pre[x];
        pre[x] = get(pre[x]);
        rk[x]=(rk[x]+rk[tmp])%2;
    }
    return pre[x];
}

int main()
{
       while(~scanf("%d%d",&n,&m)){
          int cnt = 0;
          for(int i=0;i<m;i++){
             scanf("%d%d%s",&s[i].l,&s[i].r,s[i].q);
             s[i].l--;
             a[cnt++]=s[i].l,a[cnt++]=s[i].r;
          }
          // 离散化
          sort(a,a+cnt);
          map<int,int>mp;
          cnt = unique(a,a+cnt)-a;
          for(int i=0;i<cnt;i++){
                pre[i]=i,rk[i]=0;
                mp[a[i]]=i;
          }
          int ans = 0;
          for(int i=0;i<m;i++){
             int x = mp[s[i].l],y = mp[s[i].r];
             int xx = get(x);
             int yy = get(y);
             if(xx!=yy){
                pre[xx]=yy;
                if(s[i].q[0]=='e')          //偶数边的权值为0
                rk[xx]=(rk[x]+rk[y])%2;
                else rk[xx]=(rk[x]+rk[y]+1)%2;    //奇数边的权值为1
                ans++;
             }
             else {
                if(rk[x]==rk[y]&&s[i].q[0]=='o')break;    
                if(rk[x]!=rk[y]&&s[i].q[0]=='e')break;
                ans++;
             }
          }
          printf("%d\n",ans);

       }

    return 0;
}