急训 Day 1 （2）

Mushroom的区间
【题目描述】
Mushroom有一行数，初始时全部是0。现在Mushroom有m个区间[L,R]，他希望用以下操作得到新的序列。
从m个给定区间中选择一个区间[s,t]，把区间中的数对应元素全部翻转。（0变1,1变0）
请告诉Mushroom他能得到多少区间。（模10^9+7）
【输入格式】
第一行包含两个整数n，m。表示n个数和m个区间。
接下来m行是所表示的区间。
【输出格式】
一个整数，表示能得到的区间数。
【样例输入】
3 3
1 1
2 2
3 3
【样例输出】
8
【数据范围】
对于30%的数据，n,m<=20
对于60%的数据，n,m<=100
对于100%的数据，n,m<=100000

【样例解释】
每个位置都可以单个修改，所以有8种可能。

神奇的解法，思路：去掉一些可以用其他区间覆盖掉他的区间（该区间则视为无效）最后有效区间数则为幂，ans=2^（边数）

如何维护区间是否被覆盖，这里有一个很神奇的并查集做法，因为L可以等于R 所以考虑平移左区间一位（答案不改变）
每次读入判断两端点的father 如果father一样则说明这个区间是可以被之前出现过的区间所覆盖的（一定等效）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<map>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int MAX=;

const int MOD=+;

int n,m,ans=;

int fa[MAX];

int findfa(int k)

{

    if (fa[k]!=k) return fa[k]=findfa(fa[k]);

    return fa[k];

}

int main()

{

    cin>>n>>m;

    for (int i=;i<=n;i++)

     fa[i]=i;

    for (int i=;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        int f1=findfa(x-);

        int f2=findfa(y);

        if (f1!=f2)

        {

            fa[f1]=f2;

            ans=ans*%MOD;

        }

    }

    cout<<ans;

}