算法提高课汇总

带权并查集

前缀和

题目涉及$l\sim r$区间个数, 定义前缀和$s(i) = S[1\sim i]$, 即前$i$个元素中
$1$的个数. 则区间数字$1$的奇偶可转化为:

• $S[l\sim r]$有偶数个$1$ --> $s(r) - s(l - 1)$为偶数 --> $s(r)$与$s(l-1)$奇偶性相同.

• $S[l\sim r]$有奇数个$1$ --> $s(r)$与$s(l-1)$奇偶性不同.

我们令$s(l-1)$与$s(r)$在同一并查集中表示两者的奇偶性关系已经给出;
若在同一类集合中表示两者奇偶性相同, 否则表示奇偶性不同. 问题转变
为维护多类集合的并查集问题, 解决思路参考AcWing 240. 食物链 :

• 判断$S[l\sim r]$奇偶性是否矛盾, 首先考虑$s(r)$与$s(l - 1)$是否处于同一并查集中,
  若属于同一并查集, 判断是否处于同一类集合; 若不属于同一并查集则二者的信息
  未给出, 将其奇偶性关系加入并查集中维护.

合理性

考虑序列$S$的构造方式: 令$s’(i) = 1$, 若$s(i)$为奇数; $s’(i) = 0$, 若$s(i)$为偶数.
原序列$S(i) = s’(i)$^$s’(i - 1)$. 其中^为异或运算, 即当$s(i)$与$s(i-1)$奇偶性
不同时, $S(i) = 1$,否则$S(i) = 0$. 可以用递推方式证明:

• 若$i = 1$, 由于$s(0) = 0$ --> $s’(0) = 0$. 若$s(1) = 1, S(1) = 1$,
  否则$s(1) = 0,S(1) = 0$. 两者情况均符合$s(1)$的奇偶性.

• 假设$i = k$时, $S(k) = s’(k)$^$s’(k - 1)$满足性质.
  当$i = k + 1$时, 若$s(k+1)$与$s(k)$奇偶性不同, $S(k + 1) = 1$, 满足性质;
  ($S(k + 1) = 1$ 保证了 $s(k + 1)$ 与 $s(k)$ 奇偶性不同)
  若$s(k + 1)$与$s(k)$奇偶性相同, $S(k + 1) = 0$, 满足性质.

所以我们通过维护$s’$ (s奇偶性关系) 的合理性就可以判断是否可以构造合理$S$序列.

具体实现

由于数值范围在$10^9$, 远大于输入个数$10^4$(有用数值范围), 需要做离散化处理.
问题由序列转换成判断奇偶性问题, 所以可以使用非保序离散化(对可以不保序个人还是
有点不能理解, 目前理解方式是在上述序列构造过程中, 只需要考虑奇偶性合理, 在
合理前提下不同顺序都能构造出一个合法序列).

代码实现

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 5000 * 2 + 10;

int n, m;
int p[N], d[N];
unordered_map<int, int> mp;

int get(int x)
{
    if ( mp.count(x) == 0 ) mp[x] = ++ n;
    return mp[x];
}

int find(int x)
{
    if ( p[x] != x )
    {
        int root = find(p[x]); //更新d[p[x]], 并得到当前根
        d[x] += d[ p[x] ];  //更新d[x]
        p[x] = root;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;

    n = 0;
    for ( int i = 1; i < N; i ++ )  p[i] = i;

    int res = m; 
    for ( int i = 1; i <= m; i ++ )
    {
        int l, r;
        string type;
        cin >> l >> r >> type;

        int a = get(l - 1), b = get(r);
        int t = 0;
        if ( type == "odd" )    t = 1;

        int pa = find(a), pb = find(b);
        if ( pa == pb )
        {//a, b关系已经给出
            if ( (d[a] - d[b] - t) % 2 )    
            {
                res = i - 1;
                break;
            }
        }
        else
        {//维护a, b关系
            p[pa] = pb;
            d[pa] = d[b] + t - d[a];
            //( d[a] + ? - d[b] )% 2 = t
            // ? = d[b] + t - d[a]
        }
    }
    cout << res << endl;

    return 0;
}

带扩展域并查集

实现维护多类集合并查集也可用带扩展域并查集实现, 其思想是枚举每个元素的所有条件.

以本题为例, 对于$s(i)$, 我们关注的是其与$s(j)$的相对关系, 而$s(i)$是奇或偶不需
考虑. 枚举两个条件: 若$s(i)$为偶数和若$s(i)$为奇数. 分别用下标$i$和$i + Bias$表示.
此时若已知$s(i)$与$s(j)$奇偶相同, 有:

• 若$s(i)$为偶数, $s(j)$也为偶数, 即$i$和$j$属于同于集合.

• 若$s(i)$为奇数, $s(j)$也为奇数, $i+Bias$与$j+Bias$属于同一集合.

若已知$s(i)$与$s(j)$奇偶性不同, 则:

• 若$s(i)$为偶数, 则$s(j)$为奇数, 即$i$和$j + Bias$属于同一集合.

• 若$s(i)$为奇数, 则$s(j)$为偶数, 即$i+Bias$和$j$属于同一集合.

即属于同一集合的条件相同(均为偶数或均为奇数).

实现代码

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 5000 * 2 + 10;

int n, m;
int p[2 * N]; //分别保存i和i + N
unordered_map<int, int> mp;

int get(int x)
{
    if ( mp.count(x) == 0 ) mp[x] = ++ n;
    return mp[x];
}

int find(int x)
{
    if ( p[x] != x )    p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    n = 0;
    for ( int i = 1; i < 2 * N; i ++ )  p[i] = i;

    int res = m; 
    for ( int i = 1; i <= m; i ++ )
    {
        int l, r;
        string type;
        cin >> l >> r >> type;

        int a = get(l - 1), b = get(r);
        if ( type == "even" )
        {
            if ( find(a) == find(b + N) )
            {//自相矛盾
                res = i - 1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + N)] = find(b + N);
        }
        else
        {
            if ( find(a) == find(b) )
            {
                res = i - 1;
                break;
            }
            p[find(a)] = find(b + N);
            p[find(a + N)] = find(b);
        }
    }
    cout << res << endl;

    return 0;
}