题解 |F题 随机异或哈希

F题

对于第个区间，将区间染上第种颜色。

对于能够创建的区间的左右端点，这两个端点混合之后的颜色一定完全相同。

考虑对每一个端点的染色方案进行哈希。

因为，可以使用随机异或哈希。对于所有需要染色的区间，用线段树维护一下即可。

时间复杂度：

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define int long long
#define Z 1LL << 10

using namespace std;
using i64 = long long;
using i128 = __int128;
using ld = long double;
using u64 = unsigned long long;

typedef pair<int, int> pii;

const int N = 2e5 + 5;
const int M = 4e6 + 5;
const int mod = 3;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
std::mt19937 rnd(time(0));
constexpr long double pi = static_cast<long double>(M_PI);
int dx[4] = { -1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int a[N];
struct segmenttree
{
    struct node
    {
        int l, r, maxx, tag;
    };
    vector<node>tree;

    segmenttree(): tree(1) {}
    segmenttree(int n): tree(n * 4 + 1) {}

    void pushup(int u)
    {
        auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
        root.maxx = max(left.maxx, right.maxx);
    }

    void pushdown(int u)
    {
        auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
        if (root.tag != 0)
        {
            left.tag ^= root.tag;
            right.tag ^= root.tag;
            left.maxx ^= root.tag;
            right.maxx ^= root.tag;
            root.tag = 0;
        }
    }

    void build(int u, int l, int r)
    {
        auto &root = tree[u];
        root = {l, r};
        if (l == r)
        {
            root.maxx = 0;
        }
        else
        {
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int u, int l, int r, int val)
    {
        auto &root = tree[u];
        if (root.l >= l && root.r <= r)
        {
            root.maxx ^= val;
            root.tag ^= val;
            return;
        }
        pushdown(u);
        int mid = root.l + root.r >> 1;
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        pushup(u);
    }

    int query(int u, int l, int r)
    {
        auto &root = tree[u];
        if (root.l >= l && root.r <= r)
        {
            return root.maxx;
        }
        pushdown(u);
        int mid = root.l + root.r >> 1;
        int res = 0;
        if (l <= mid) res = query(u << 1, l, r);
        if (r > mid) res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
};
int calc(int x)
{
    return x * (x + 1) / 2;
}
void solve()
{
    cin >> n >> m;
    segmenttree smt(m);
    smt.build(1, 1, m);
    for (int i = 1, l, r; i <= n; i++)
    {
        cin >> l >> r;
        if (l + 1 <= r - 1)
            smt.modify(1, l + 1, r - 1, rnd());

        a[l]++, a[r]++;
    }
    map<int, int>mp;
    for (int i = 1; i <= m; i++)
    {
        if (a[i]) continue;
        mp[smt.query(1, i, i)]++;
    }
    int ans = 0;
    for (auto mpp : mp)
    {
        int cnt = mpp.second;
        ans += calc(cnt);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}