POJ 1733 Parity game(valset)

Description

给出N、M分别表示某个01串的长度、查询数量

接下来M行，L R S 表示[L, R]有奇数个1还是偶数个1

问哪一行出错了(与前面所述有矛盾)，输出这行的前一行标号

Analyze

带权并查集，跟HDU 3038 How many answers are wrong相似，但刚开始我不会做，在这里反思：

做题一定要有自己的充足的思考，先自己试着去解题，不行再看题解。

记住哪个点不行，自己尝试多种方法解决这个点。

看题解时思考题解是怎么实现自己所实现不了的功能，要学会这种思想。

现在我看以前的题解，发现要是在让我做那道题，我还是不会，真是讽刺。

我只知道那样做可行，而若抛却那种做法却不知如何去做。

就像只知道必要条件而不知道充分条件，只学到皮毛，没学到思想。只得到一条鱼而没学会怎么捕鱼。

升华

问：为什么计算机相关的数据结构在描述区间的时候都是[左闭，右开)？

一个未学过计算机的人相较而言会更喜欢[左闭， 右闭]这种描述

下面我们来探索一下

先给定区间[1, 9]，我们用某种方式将1~9连接

在分别给定区间[1, 3]， [4, 6]， [7, 9]，我们用同样的连接它们

但我们发现前后两者所表现的不一样：后者三个区间彼此没有组合在一起

但是两者其实所包含的区间完全一样

问题就在于：这种连接方式不够好

换成[左闭右开)或者(左开右闭]的方式连接就好了！

一般常用左开右闭，像“前缀和”就有这样的意思

但介于计算机从0开始，0的左为“-1”，不适合做下标，左闭右开更好些

以上都是我的思考以及猜测

另外这题数大，但数据量不大，正常思路应该用离散化解决一下，但我想用map偷懒，而且我第一反应觉得这题不用离散化(但实际上看来可以)，实测map可用。

map\ mp：无限大的数组(甚至下标可以为负值)

Code

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

bool flag;
char s[10];
int n, m, ans, L, R;
map<int, int> pre;
map<int, int> val;

int found(int x)
{
    if(pre[x] == 0)
        return x;

    int tem = found(pre[x]);
    val[x] += val[ pre[x] ];
    val[x] %= 2;
    return pre[x] = tem;
}

void unite(int L, int R, int num, int idx)
{
    int LL = found(L);
    int RR = found(R);
    if(LL != RR)
    {
        pre[LL] = RR;
        val[LL] = (-val[L] + val[R] + num + 2) % 2;
    }
    else
    {
        if((val[L] - val[R] + 2) % 2 != num)
            flag = 1, ans = idx - 1;
    }
}



int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        pre.clear();
        val.clear();
        flag = 0, ans = m;

        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d %s", &L, &R, s);
            if(flag)
                continue;
            if(s[0] == 'e')
                unite(L, R + 1, 0, i);
            else
                unite(L, R + 1, 1, i);
        }
        cout << ans << '\n';
    }
    return 0;
}