CF1109F Sasha and Algorithm of Silence's Sounds

$\text{link}$

首先考虑计算每个左端点对应的合法右端点的个数，可以发现随着 $l$ 的增大，使得 $[l,r]$ 不存在环的最大的 $r$ 是单调递增的，然后我就不会了。。。

看了题解才想起来可以利用树“点数-边数=1”的性质计算，于是拿棵线段树顺便维护一下“点数-边数”的最小值以及最小值的个数就好了，因为 $[l,l]$ 显然满足 “点数-边数=1” 。

时间复杂度 $\mathrm{O(nm\log(nm))}$ 。

这种性质还是要想的起来啊。

线段树四倍空间 /fn/fn/fn

$\text{Code:}$

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 2e5 + 5;
int n, m, nm, a[maxn][maxn];
vector<int> G[maxm];
long long ans;
namespace LCT {
    struct Node {
        int ch[2], fa, tag;
        void clr() {ch[0] = ch[1] = fa = tag = 0;}
        void ladd() {tag ^= 1; swap(ch[0], ch[1]);}
    } t[maxm];
    bool nrt(int x) {return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x;}
    void rotate(int x) {
        int y = t[x].fa, z = t[y].fa;
        if (nrt(y)) t[z].ch[t[z].ch[1] == y] = x;
        t[t[y].fa = x].fa = z;
        int gx = t[y].ch[1] == x;
        t[y].ch[gx] = t[x].ch[gx ^ 1];
        t[t[x].ch[gx ^ 1]].fa = y;
        t[x].ch[gx ^ 1] = y;
    }
    void pd(int x) {
        if (t[x].tag) {
            t[t[x].ch[0]].ladd();
            t[t[x].ch[1]].ladd();
            t[x].tag = 0;
        }
    }
    int stk[maxm], top;
    void splay(int x) {
        int u = x;
        for (; nrt(u); u = t[u].fa) stk[++top] = u;
        pd(u); while (top) pd(stk[top--]);
        while (nrt(x)) {
            int y = t[x].fa, z = t[y].fa;
            if (nrt(y) && ((t[z].ch[0] == y) == (t[y].ch[0] == x))) rotate(y);
            rotate(x);
        }
    }
    void access(int x) {for (int y = 0; x; y = x, x = t[x].fa) splay(x), t[x].ch[1] = y;}
    void mrt(int x) {access(x); splay(x); t[x].ladd();}
    void split(int x, int y) {mrt(x); access(y); splay(y);}
    void cut(int x, int y) {split(x, y); t[x].fa = t[y].ch[0] = 0;}
    int frt(int x) {
        access(x); splay(x);
        while (t[x].ch[0]) pd(x), x = t[x].ch[0];
        splay(x); return x;
    }
    bool link(int x, int y) {
        mrt(x);
        if (frt(y) == x) return 0;
        t[x].fa = y; return 1;
    }
}
namespace _Smt {
    #define ls u << 1
    #define rs u << 1 | 1
    struct Node {
        int mn, sz, tag;
        void ladd(int x) {mn += x; tag += x;}
    } t[maxm << 2];
    Node merge(Node c, Node a, Node b) {
        if (a.mn < b.mn) c.mn = a.mn, c.sz = a.sz;
        if (a.mn > b.mn) c.mn = b.mn, c.sz = b.sz;
        if (a.mn == b.mn) c.mn = a.mn, c.sz = a.sz + b.sz;
        return c;
    }
    void pd(int u) {
        if (t[u].tag) {
            t[ls].ladd(t[u].tag);
            t[rs].ladd(t[u].tag);
            t[u].tag = 0;
        }
    }
    void mdf(int u, int l, int r, int x, int y) {
        if (l == r) {t[u] = (Node){y, 1, 0}; return;}
        pd(u);
        int mid = (l + r) >> 1;
        if (x <= mid) mdf(ls, l, mid, x, y);
            else mdf(rs, mid + 1, r, x, y);
        t[u] = merge(t[u], t[ls], t[rs]);
    }
    void mdf2(int u, int l, int r, int x, int y, int z) {
        if (x <= l && r <= y) {t[u].ladd(z); return;}
        pd(u);
        int mid = (l + r) >> 1;
        if (x <= mid) mdf2(ls, l, mid, x, y, z);
        if (y > mid) mdf2(rs, mid + 1, r, x, y, z);
        t[u] = merge(t[u], t[ls], t[rs]);
    }
    Node qry(int u, int l, int r, int x, int y) {
        if (x <= l && r <= y) return t[u];
        pd(u);
        int mid = (l + r) >> 1;
        if (x > mid) return qry(rs, mid + 1, r, x, y);
        if (y <= mid) return qry(ls, l, mid, x, y);
        return merge((Node){0, 0, 0}, qry(ls, l, mid, x, y), qry(rs, mid + 1, r, x, y));
    }
    #undef ls
    #undef rs
}
int lx;
bool lk(int l, int x) {
    for (int i = 0; i < G[x].size(); i++) {
        int v = G[x][i];
        if (v < l || v > x) continue;
        if (!LCT::link(x, v)) {
            for (int j = 0; j < i; j++) {
                if (G[x][j] < l || G[x][j] > x) continue;
                LCT::cut(x, G[x][j]);
            }
            return 0;
        }
        lx++;
    }
    return 1;
}
int dt;
void ct(int x, int r) {
    for (int v : G[x]) {
        if (v > r || v < x) continue;
        LCT::cut(x, v);
        // printf("? %d %d %d\n", x, v, r);
        _Smt::mdf2(1, 1, nm, v, r, 1);
    }
}
void solve() {
    int r = 2;
    _Smt::mdf(1, 1, nm, 1, 1);
    for (int l = 1; l < nm; l++) {
        // printf("! %d %d %d %d\n", l, r - 1, qry(1, 1, nm, l, r - 1).mn, qry(1, 1, nm, l, r - 1).sz);
        while (r <= nm) {
            lx = 0;
            if (!lk(l, r)) break;
            // printf("%d %d %d\n", r, qry2(1, 1, nm, r - 1), lx);
            _Smt::mdf(1, 1, nm, r, _Smt::qry(1, 1, nm, r - 1, r - 1).mn + 1 - lx);
            r++;
        }
        ans += _Smt::qry(1, 1, nm, l, r - 1).sz;
        // printf("%d %d %d %d\n", l, r - 1, _Smt::qry(1, 1, nm, l, r - 1).mn, _Smt::qry(1, 1, nm, l, r - 1).sz);
        // for (int i = l; i < r; i++) printf("    %d %d\n", i, _Smt::qry(1, 1, nm, i, i).mn);
        ct(l, r - 1); _Smt::mdf2(1, 1, nm, l + 1, r - 1, -1);
        // puts("?");
        // for (int i = l + 1; i < r; i++) printf("    %d %d\n", i, _Smt::qry(1, 1, nm, i, i).mn);
        // printf("! %d %d %d %d\n", l, r - 1, qry(1, 1, nm, l, r - 1).mn, qry(1, 1, nm, l, r - 1).sz);
    }
    ans++;
}
int main() {
    scanf("%d%d", &n, &m); nm = n * m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        if (i > 1) G[a[i][j]].pb(a[i - 1][j]);
        if (j > 1) G[a[i][j]].pb(a[i][j - 1]);
        if (i < n) G[a[i][j]].pb(a[i + 1][j]);
        if (j < m) G[a[i][j]].pb(a[i][j + 1]);
    }
    solve();
    printf("%lld", ans);
    return 0;
}