{"id":129,"date":"2022-06-03T18:56:26","date_gmt":"2022-06-03T10:56:26","guid":{"rendered":"https:\/\/vite66.cn\/?p=129"},"modified":"2025-01-11T16:57:55","modified_gmt":"2025-01-11T08:57:55","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%b8%b8%e7%94%a8%e7%ae%97%e6%b3%95%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/vite66.cn\/?p=129","title":{"rendered":"\u6570\u636e\u7ed3\u6784 – \u5e38\u7528\u7b97\u6cd5\u6a21\u677f"},"content":{"rendered":"

\u57fa\u672c\u6570\u636e\u7ed3\u6784<\/h2>\n

\u5355\u94fe\u8868<\/h3>\n
\/\/ head\u5b58\u50a8\u94fe\u8868\u5934\uff0ce[]\u5b58\u50a8\u8282\u70b9\u7684\u503c\uff0cne[]\u5b58\u50a8\u8282\u70b9\u7684next\u6307\u9488\uff0cidx\u8868\u793a\u5f53\u524d\u7528\u5230\u4e86\u54ea\u4e2a\u8282\u70b9\nint head, e[N], ne[N], idx;\n\n\/\/ \u521d\u59cb\u5316\nvoid init()\n{\n    head = -1;\n    idx = 0;\n}\n\n\/\/ \u5728\u94fe\u8868\u5934\u63d2\u5165\u4e00\u4e2a\u6570a\nvoid insert(int a)\n{\n    e[idx] = a, ne[idx] = head, head = idx ++ ;\n}\n\n\/\/ \u5c06\u5934\u7ed3\u70b9\u5220\u9664\uff0c\u9700\u8981\u4fdd\u8bc1\u5934\u7ed3\u70b9\u5b58\u5728\nvoid remove()\n{\n    head = ne[head];\n}<\/code><\/pre>\n
\u53cc\u94fe\u8868<\/h3>\n
\/\/ e[]\u8868\u793a\u8282\u70b9\u7684\u503c\uff0cl[]\u8868\u793a\u8282\u70b9\u7684\u5de6\u6307\u9488\uff0cr[]\u8868\u793a\u8282\u70b9\u7684\u53f3\u6307\u9488\uff0cidx\u8868\u793a\u5f53\u524d\u7528\u5230\u4e86\u54ea\u4e2a\u8282\u70b9\nint e[N], l[N], r[N], idx;\n\n\/\/ \u521d\u59cb\u5316\nvoid init()\n{\n    \/\/0\u662f\u5de6\u7aef\u70b9\uff0c1\u662f\u53f3\u7aef\u70b9\n    r[0] = 1, l[1] = 0;\n    idx = 2;\n}\n\n\/\/ \u5728\u8282\u70b9a\u7684\u53f3\u8fb9\u63d2\u5165\u4e00\u4e2a\u6570x\nvoid insert(int a, int x)\n{\n    e[idx] = x;\n    l[idx] = a, r[idx] = r[a];\n    l[r[a]] = idx, r[a] = idx ++ ;\n}\n\n\/\/ \u5220\u9664\u8282\u70b9a\nvoid remove(int a)\n{\n    l[r[a]] = l[a];\n    r[l[a]] = r[a];\n}\n<\/code><\/pre>\n
\u6808<\/h3>\n
\/\/ tt\u8868\u793a\u6808\u9876\nint stk[N], tt = 0;\n\n\/\/ \u5411\u6808\u9876\u63d2\u5165\u4e00\u4e2a\u6570\nstk[ ++ tt] = x;\n\n\/\/ \u4ece\u6808\u9876\u5f39\u51fa\u4e00\u4e2a\u6570\ntt -- ;\n\n\/\/ \u6808\u9876\u7684\u503c\nstk[tt];\n\n\/\/ \u5224\u65ad\u6808\u662f\u5426\u4e3a\u7a7a\nif (tt > 0)\n{\n\n}<\/code><\/pre>\n
\u961f\u5217<\/h3>\n
\u666e\u901a\u961f\u5217<\/h4>\n
\/\/ hh \u8868\u793a\u961f\u5934\uff0ctt\u8868\u793a\u961f\u5c3e\nint q[N], hh = 0, tt = -1;\n\n\/\/ \u5411\u961f\u5c3e\u63d2\u5165\u4e00\u4e2a\u6570\nq[ ++ tt] = x;\n\n\/\/ \u4ece\u961f\u5934\u5f39\u51fa\u4e00\u4e2a\u6570\nhh ++ ;\n\n\/\/ \u961f\u5934\u7684\u503c\nq[hh];\n\n\/\/ \u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\nif (hh <= tt)\n{\n\n}<\/code><\/pre>\n
\u5faa\u73af\u961f\u5217<\/h4>\n
\/\/ hh \u8868\u793a\u961f\u5934\uff0ctt\u8868\u793a\u961f\u5c3e\u7684\u540e\u4e00\u4e2a\u4f4d\u7f6e\nint q[N], hh = 0, tt = 0;\n\n\/\/ \u5411\u961f\u5c3e\u63d2\u5165\u4e00\u4e2a\u6570\nq[tt ++ ] = x;\nif (tt == N) tt = 0;\n\n\/\/ \u4ece\u961f\u5934\u5f39\u51fa\u4e00\u4e2a\u6570\nhh ++ ;\nif (hh == N) hh = 0;\n\n\/\/ \u961f\u5934\u7684\u503c\nq[hh];\n\n\/\/ \u5224\u65ad\u961f\u5217\u662f\u5426\u4e3a\u7a7a\nif (hh != tt)\n{\n\n}<\/code><\/pre>\n
KMP \u7b97\u6cd5<\/h3>\n
\/\/ s[]\u662f\u957f\u6587\u672c\uff0cp[]\u662f\u6a21\u5f0f\u4e32\uff0cn\u662fs\u7684\u957f\u5ea6\uff0cm\u662fp\u7684\u957f\u5ea6\n\u6c42\u6a21\u5f0f\u4e32\u7684Next\u6570\u7ec4\uff1a\nfor (int i = 2, j = 0; i <= m; i ++ )\n{\n    while (j && p[i] != p[j + 1]) j = ne[j];\n    if (p[i] == p[j + 1]) j ++ ;\n    ne[i] = j;\n}\n\n\/\/ \u5339\u914d\nfor (int i = 1, j = 0; i <= n; i ++ )\n{\n    while (j && s[i] != p[j + 1]) j = ne[j];\n    if (s[i] == p[j + 1]) j ++ ;\n    if (j == m)\n    {\n        j = ne[j];\n        \/\/ \u5339\u914d\u6210\u529f\u540e\u7684\u903b\u8f91\n    }\n}\n<\/code><\/pre>\n
Trie \u6811<\/h3>\n
int son[N][26], cnt[N], idx;\n\/\/ 0\u53f7\u70b9\u65e2\u662f\u6839\u8282\u70b9\uff0c\u53c8\u662f\u7a7a\u8282\u70b9\n\/\/ son[][]\u5b58\u50a8\u6811\u4e2d\u6bcf\u4e2a\u8282\u70b9\u7684\u5b50\u8282\u70b9\n\/\/ cnt[]\u5b58\u50a8\u4ee5\u6bcf\u4e2a\u8282\u70b9\u7ed3\u5c3e\u7684\u5355\u8bcd\u6570\u91cf\n\n\/\/ \u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\u4e32\nvoid insert(char *str)\n{\n    int p = 0;\n    for (int i = 0; str[i]; i ++ )\n    {\n        int u = str[i] - 'a';\n        if (!son[p][u]) son[p][u] = ++ idx;\n        p = son[p][u];\n    }\n    cnt[p] ++ ;\n}\n\n\/\/ \u67e5\u8be2\u5b57\u7b26\u4e32\u51fa\u73b0\u7684\u6b21\u6570\nint query(char *str)\n{\n    int p = 0;\n    for (int i = 0; str[i]; i ++ )\n    {\n        int u = str[i] - 'a';\n        if (!son[p][u]) return 0;\n        p = son[p][u];\n    }\n    return cnt[p];\n}\n\n\/\/ \u7ed3\u6784\u4f53\u5199\u6cd5\n struct node{\n        node* son[26];\n        int cnt = 0;\n    };\n    node* head = new node();\n    void insert(string s) {\n        node* p = head;\n        for (int i = 0; i < s.size(); ++ i) {\n            int u = s[i] - 'a';\n            if (p->son[u] == NULL) {\n                p->son[u] = new node();\n            }\n            p = p->son[u];\n        }\n        p->cnt ++;\n    }\n    bool query(string& s, int idx, int f) {\n        node* p = head;\n        for (int i = 0; i < s.size(); ++ i) {\n            int u = s[i] - 'a';\n            if (p->son[u] == NULL) return false;\n            p = p->son[u];\n        }\n        return p->cnt > 0;\n    }\n<\/code><\/pre>\n
\u5e76\u67e5\u96c6<\/h3>\n
(1)\u6734\u7d20\u5e76\u67e5\u96c6\uff1a\n\n    int p[N]; \/\/\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x) p[x] = find(p[x]);\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i <= n; i ++ ) p[i] = i;\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    p[find(a)] = find(b);\n\n(2)\u7ef4\u62a4size\u7684\u5e76\u67e5\u96c6\uff1a\n\n    int p[N], size[N];\n    \/\/p[]\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9, size[]\u53ea\u6709\u7956\u5b97\u8282\u70b9\u7684\u6709\u610f\u4e49\uff0c\u8868\u793a\u7956\u5b97\u8282\u70b9\u6240\u5728\u96c6\u5408\u4e2d\u7684\u70b9\u7684\u6570\u91cf\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x) p[x] = find(p[x]);\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i <= n; i ++ )\n    {\n        p[i] = i;\n        size[i] = 1;\n    }\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    size[find(b)] += size[find(a)];\n    p[find(a)] = find(b);\n\n(3)\u7ef4\u62a4\u5230\u7956\u5b97\u8282\u70b9\u8ddd\u79bb\u7684\u5e76\u67e5\u96c6\uff1a\n\n    int p[N], d[N];\n    \/\/p[]\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9, d[x]\u5b58\u50a8x\u5230p[x]\u7684\u8ddd\u79bb\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x)\n        {\n            int u = find(p[x]);\n            d[x] += d[p[x]];\n            p[x] = u;\n        }\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i <= n; i ++ )\n    {\n        p[i] = i;\n        d[i] = 0;\n    }\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    p[find(a)] = find(b);\n    d[find(a)] = distance; \/\/ \u6839\u636e\u5177\u4f53\u95ee\u9898\uff0c\u521d\u59cb\u5316find(a)\u7684\u504f\u79fb\u91cf\n\n    \u677f\u5b50\n\nstruct DSU{\n    vector<int> p;\n    DSU(int n) : p(n + 1){\n        iota(p.begin(), p.end(), 0);\n    }\n\n    int find(int x){\n        return p[x] == x ? x : p[x] = find(p[x]);\n    }\n\n    bool same(int x, int y) { \n        return find(x) == find(y); \n    }\n\n    bool merge(int x, int y){\n        x = find(x), y = find(y);\n        if (x == y) return false;\n        p[y] = x;\n        return true;\n    }\n};\n<\/code><\/pre>\n
\u5806<\/h3>\n
\/\/ h[N]\u5b58\u50a8\u5806\u4e2d\u7684\u503c, h[1]\u662f\u5806\u9876\uff0cx\u7684\u5de6\u513f\u5b50\u662f2x, \u53f3\u513f\u5b50\u662f2x + 1\n\/\/ ph[k]\u5b58\u50a8\u7b2ck\u4e2a\u63d2\u5165\u7684\u70b9\u5728\u5806\u4e2d\u7684\u4f4d\u7f6e\n\/\/ hp[k]\u5b58\u50a8\u5806\u4e2d\u4e0b\u6807\u662fk\u7684\u70b9\u662f\u7b2c\u51e0\u4e2a\u63d2\u5165\u7684\nint h[N], ph[N], hp[N], size;\n\n\/\/ \u4ea4\u6362\u4e24\u4e2a\u70b9\uff0c\u53ca\u5176\u6620\u5c04\u5173\u7cfb\nvoid heap_swap(int a, int b)\n{\n    swap(ph[hp[a]],ph[hp[b]]);\n    swap(hp[a], hp[b]);\n    swap(h[a], h[b]);\n}\n\nvoid down(int u)\n{\n    int t = u;\n    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;\n    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;\n    if (u != t)\n    {\n        heap_swap(u, t);\n        down(t);\n    }\n}\n\nvoid up(int u)\n{\n    while (u \/ 2 && h[u] < h[u \/ 2])\n    {\n        heap_swap(u, u \/ 2);\n        u >>= 1;\n    }\n}\n\n\/\/ O(n)\u5efa\u5806\nfor (int i = n \/ 2; i; i -- ) down(i);\n<\/code><\/pre>\n
\u4e00\u822c\u54c8\u5e0c<\/h3>\n
(1) \u62c9\u94fe\u6cd5\n    int h[N], e[N], ne[N], idx;\n\n    \/\/ \u5411\u54c8\u5e0c\u8868\u4e2d\u63d2\u5165\u4e00\u4e2a\u6570\n    void insert(int x)\n    {\n        int k = (x % N + N) % N;\n        e[idx] = x;\n        ne[idx] = h[k];\n        h[k] = idx ++ ;\n    }\n\n    \/\/ \u5728\u54c8\u5e0c\u8868\u4e2d\u67e5\u8be2\u67d0\u4e2a\u6570\u662f\u5426\u5b58\u5728\n    bool find(int x)\n    {\n        int k = (x % N + N) % N;\n        for (int i = h[k]; i != -1; i = ne[i])\n            if (e[i] == x)\n                return true;\n\n        return false;\n    }\n\n(2) \u5f00\u653e\u5bfb\u5740\u6cd5\n    int h[N];\n\n    \/\/ \u5982\u679cx\u5728\u54c8\u5e0c\u8868\u4e2d\uff0c\u8fd4\u56dex\u7684\u4e0b\u6807\uff1b\u5982\u679cx\u4e0d\u5728\u54c8\u5e0c\u8868\u4e2d\uff0c\u8fd4\u56dex\u5e94\u8be5\u63d2\u5165\u7684\u4f4d\u7f6e\n    int find(int x)\n    {\n        int t = (x % N + N) % N;\n        while (h[t] != null && h[t] != x)\n        {\n            t ++ ;\n            if (t == N) t = 0;\n        }\n        return t;\n    }\n<\/code><\/pre>\n
\u5b57\u7b26\u4e32\u54c8\u5e0c<\/h3>\n
\u6838\u5fc3\u601d\u60f3\uff1a\u5c06\u5b57\u7b26\u4e32\u770b\u6210P\u8fdb\u5236\u6570\uff0cP\u7684\u7ecf\u9a8c\u503c\u662f131\u621613331\uff0c\u53d6\u8fd9\u4e24\u4e2a\u503c\u7684\u51b2\u7a81\u6982\u7387\u4f4e\n\u5c0f\u6280\u5de7\uff1a\u53d6\u6a21\u7684\u6570\u75282^64\uff0c\u8fd9\u6837\u76f4\u63a5\u7528unsigned long long\u5b58\u50a8\uff0c\u6ea2\u51fa\u7684\u7ed3\u679c\u5c31\u662f\u53d6\u6a21\u7684\u7ed3\u679c\n\ntypedef unsigned long long ULL;\nULL h[N], p[N]; \/\/ h[k]\u5b58\u50a8\u5b57\u7b26\u4e32\u524dk\u4e2a\u5b57\u6bcd\u7684\u54c8\u5e0c\u503c, p[k]\u5b58\u50a8 P^k mod 2^64\n\n\/\/ \u521d\u59cb\u5316\np[0] = 1;\nfor (int i = 1; i <= n; i ++ )\n{\n    h[i] = h[i - 1] * P + str[i];\n    p[i] = p[i - 1] * P;\n}\n\n\/\/ \u8ba1\u7b97\u5b50\u4e32 str[l ~ r] \u7684\u54c8\u5e0c\u503c\nULL get(int l, int r)\n{\n    return h[r] - h[l - 1] * p[r - l + 1];\n}<\/code><\/pre>\n
\u9ad8\u7ea7\u6570\u636e\u7ed3\u6784<\/h2>\n
ST \u8868<\/h3>\n
\u8be6\u7ec6\u7406\u8bba<\/a>
\nST[p][i] \u8868\u793a\u4ece i \u70b9\u5f00\u59cb\u5171${2^p}$ \u4e2a\u6570\u7684\u6700\u5927\u503c\uff0c\u5373[i, i + ${2^p}$ - 1] \u533a\u95f4\u6700\u5927\u503c<\/p>\n
void ST(){\n        for(int i = 1; i <= n; i ++) st[0][i] = x[i];\n        int p = log(n) \/ log(2);\n        for(int k = 1; k <= p; k ++){\n            for(int i = 1; i + (1 << k) - 1 <= n; i ++){\n                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);\n            }\n        }\n    }\nint query(int l, int r){\n        int p = __lg(r -  l + 1);\n        \/\/ int p = log(r - l + 1) \/ log(2);\n        return max(st[p][l], st[p][r - (1 << p) + 1]);\n}<\/code><\/pre>\n
\u6811\u72b6\u6570\u7ec4<\/h3>\n
\"\"<\/div><\/p>\n
typedef long long LL;\nint a[N]; \/\/ a \u662f\u9700\u8981\u7ef4\u62a4\u7684\u6570\u7ec4\nLL tr[N]; \n\nint lowbit(int x)\n{\n    return x & -x;\n}\n\nvoid add(LL c[], int x, int v)\n{\n    for (int i = x; i <= n; i += lowbit(i))\n        c[i] += v;\n}\n\nLL query(LL c[], int x)\n{\n    LL res = 0;\n    for (int i = x; i; i -= lowbit(i))\n        res += c[i];\n    return res;\n}\n\nint main() {\n  \/\/ \u539f\u5730 O\uff08n\uff09\u5efa\u6811\u72b6\u6570\u7ec4\n    for (int x = 1; x <= n; ++x)\n        for (int i = x - 1; i > x - lowbit(x); i -= lowbit(i))\n            tr[x] += tr[i];\n}<\/code><\/pre>\n
\u7ebf\u6bb5\u6811<\/h3>\n
\"\"<\/div><\/p>\n
typedef long long LL;\nint w[N]; \/\/ \u8981\u7ef4\u62a4\u7684\u6570\u7ec4\nstruct Node\n{\n    int l, r;\n    LL sum, add; \/\/ \u4f9d\u636e\u60c5\u51b5\u81ea\u5b9a\u4e49\u53d8\u91cf\n}tr[N * 4];\n\nvoid pushup(int u) {\n    \/\/ \u81ea\u5b9a\u4e49\n}\n\nvoid pushdowm(int u) {\n    \/\/ \u81ea\u5b9a\u4e49\n}\n\n\/\/ \u5de6\u95ed\u53f3\u95ed\nvoid build(int u, int l, int r) {\n    if (l == r) tr[u] = {l, r, w[l], 0};\n    else {\n      tr[u] = {l, r};\n      int mid = l + r >> 1;\n      build(u << 1, 1, mid), build(u << 1 | 1, mid + 1, r);\n      pushup(u);\n    }\n}\n\nvoid modify(int u, int l, int r) {\n\n    if (l <= tr[u].l && tr[u].r <= r)\n    {\n        \/\/ \u81ea\u5b9a\u4e49\n    }\n    else\n    {\n        pushdown(u);\n        int mid = tr[u].l + tr[u].r >> 1;\n        if (l <= mid) modify(u << 1, l, r);\n        if (r > mid) modify(u << 1 | 1, l, r);\n        pushup(u);\n    }\n\n}\n\nLL query(int u, int l, int r)\n{\n    if (l <= tr[u].l && tr[u].r <= r) {\n        \/\/ \u81ea\u5b9a\u4e49\n    }\n    pushdown(u);\n    int mid = tr[u].l + tr[u].r >> 1;\n    LL v = 0;\n    if (l <= mid) v = query(u << 1, l, r);\n    if (r > mid) v += query(u << 1 | 1, l, r);\n    return v;\n}\n\nint main() {\n    \/\/ \u5de6\u95ed\u53f3\u95ed\uff0c\u7f16\u53f7\u4ece 1 \u5f00\u59cb\n    bulid(1, 1, n);\n}<\/code><\/pre>\n
\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811<\/h3>\n
\u4f8b\u9898<\/a><\/p>\n
#define ls(u) tr[u].L\n#define rs(u) tr[u].R\nclass RangeModule {\n    static const int N = 1E6;\n    struct node{\n        int l, r;\n        int L, R;\n        int sum = 0;\n        int f = 0;\n    }tr[4 * N];\n    int idx = 1;\n    void push_up(int u) {\n        tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;\n    }\n    void push_dowm(int u) {\n        int& L = ls(u), &R = rs(u);\n        if (!L) {\n            L = ++ idx;\n            tr[L] = {tr[u].l, tr[u].l + tr[u].r >> 1};\n        }\n        if (!R) {\n            R = ++ idx;\n            tr[R] = {(tr[u].l + tr[u].r >> 1) + 1, tr[u].r};\n        }\n\n        if (tr[u].f == 0) return;\n        else if (tr[u].f == -1) {\n            tr[L].sum = 0;\n            tr[R].sum = 0;\n        }else {\n            int len = tr[u].r - tr[u].l + 1;\n            tr[L].sum = len - len \/ 2;\n            tr[R].sum = len \/ 2;\n        }\n        tr[L].f = tr[u].f;\n        tr[R].f = tr[u].f;\n        tr[u].f = 0;\n    }\n    void update(int u, int l, int r, int f) {\n        if (l <= tr[u].l && tr[u].r <= r) {\n            tr[u].f = f;\n            if (f == 1)\n                tr[u].sum = tr[u].r - tr[u].l + 1;\n            else tr[u].sum = 0;\n            return;\n        }\n        int mid = tr[u].r + tr[u].l >> 1;\n        push_dowm(u);\n        if (l <= mid) update(ls(u), l, r, f);\n        if (r > mid) update(rs(u), l, r, f);\n        push_up(u);\n    }\n    int query(int u, int l, int r) {\n        if (l <= tr[u].l && tr[u].r <= r) {\n            return tr[u].sum;\n        }\n        int mid = tr[u].l + tr[u].r >> 1;\n        push_dowm(u);\n        int ret = 0;\n        if (l <= mid) ret += query(ls(u), l, r);\n        if (r > mid) ret += query(rs(u), l, r);\n        return ret;\n    }\npublic:\n    RangeModule() {\n        tr[1] = {1, 1000000005};\n    }\n\n    void addRange(int left, int right) {\n        update(1, left, right - 1, 1);\n    }\n\n    bool queryRange(int left, int right) {\n        \/\/ if (left == 13 && right == 15) cout << query(1, 13, 14) << endl;\n        return query(1, left, right - 1) == (right - left);\n    }\n\n    void removeRange(int left, int right) {\n        update(1, left, right - 1, -1);\n    }\n};\n\n\/**\n * Your RangeModule object will be instantiated and called as such:\n * RangeModule* obj = new RangeModule();\n * obj->addRange(left,right);\n * bool param_2 = obj->queryRange(left,right);\n * obj->removeRange(left,right);\n *\/<\/code><\/pre>\n
\u73c2\u6735\u8389\u6811<\/h3>\n
\u8be6\u7ec6\u7406\u8bba<\/a><\/p>\n
    struct Node {\n        int l, r;\n        mutable int v;\n        Node(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}\n        inline bool operator<(const Node &o) const { return l < o.l; }\n    };\n    set<Node> odt;\n    const int n = 1e9;\n    auto split(int x) {\n        if (x > n) return odt.end();\n        auto it = odt.lower_bound(Node{x, 0, 0});\n        if (it != odt.end() && it->l == x) return it;\n        --it;\n        int l = it->l, r = it->r, v = it->v;\n        odt.erase(it);\n        odt.insert(Node(l, x - 1, v));\n        return odt.insert(Node(x, r, v)).first;\n    }\n    void assign(int l, int r, int v) {\n        auto itr = split(r + 1), itl = split(l);\n        odt.erase(itl, itr);\n        odt.insert(Node(l, r, v));    \n    }\n    int query(int l, int r) {\n        auto itr = split(r + 1), itl = split(l);\n        int res = 0;\n        for (; itl != itr; ++itl) {\n            res += (itl->r - itl->l + 1) * itl->v;\n        }\n        return res;\n    }<\/code><\/pre>\n
\u5e73\u8861\u6811<\/h3>\n
Treap<\/h4>\n
 \u7b80\u6982\uff1a\u6bcf\u4e2a\u8282\u70b9\u5305\u542b key \u503c \u548c \u968f\u673a\u751f\u6210\u7684 val \u503c\uff0c\u6ee1\u8db3 \u6309 key \u7684\u4e8c\u53c9\u641c\u7d22\u6811 \u7684\u540c\u65f6 \u6ee1\u8db3 \u6309 val \u7684\u5c0f\uff08\u6216\u5927\uff09\u9876\u5806 \u7684\u6027\u8d28<\/p>\n
struct node{\n    int l, r;\n    int key, val;\n    int cnt, sz; \/\/ \u81ea\u5b9a\u4e49\n}tr[N];\nint idx, root;\n\nvoid push_up(int p) {\n    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + tr[p].cnt;\n    \/\/ \u81ea\u5b9a\u4e49\n}\n\nint get_node(int x) {\n    tr[++ idx].key = x;\n    tr[idx].val = rand();\n    tr[idx].cnt = tr[idx].sz = 1;\n    return idx;\n}\n\/\/ \u5de6\u65cb\nvoid zag(int& p) {\n    int q = tr[p].r;\n    tr[p].r = tr[q].l, tr[q].l = p, p = q;\n    push_up(tr[p].l), push_up(p);\n}\n\/\/ \u53f3\u65cb\nvoid zip(int& p) {\n    int q = tr[p].l;\n    tr[p].l = tr[q].r, tr[q].r = p, p = q;\n    push_up(tr[p].r), push_up(p);\n}\n\nvoid built() {\n    get_node(INF), get_node(-INF); \/\/ \u4e24\u4e2a\u54e8\u5b50\u8282\u70b9\n    root = 1;\n    tr[root].l = 2;\n    push_up(root);\n    if (tr[1].val < tr[2].val) zip(root); \/\/ \u8fd9\u91cc\u662f val \u7684\u5c0f\u9876\u5806\n}\n\nvoid insert(int& p, int x) {\n    if (!p) p = get_node(x);\n    else if (tr[p].key == x) tr[p].cnt ++;\n    else if (tr[p].key < x) {\n        insert(tr[p].r, x);\n        if (tr[tr[p].r].val > tr[p].val) zag(p);\n    }else {\n        insert(tr[p].l, x);\n        if (tr[tr[p].l].val > tr[p].val) zip(p);\n    }\n    push_up(p);\n}\n\nvoid del(int& p, int key) {\n    if (!p) return;\n    if (tr[p].key == key) {\n        if (tr[p].cnt > 1) {\n            tr[p].cnt --;\n        }\n        else if (tr[p].l || tr[p].r ) {\n            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {\n                zip(p);\n                del(tr[p].r, key);\n            }else {\n                zag(p);\n                del(tr[p].l, key);\n            }\n\n        }else p = 0;\n    }else if (key > tr[p].key) {\n        del(tr[p].r, key);\n    }\n    else {\n        del(tr[p].l, key);\n    }\n    push_up(p);\n}\nint look_for_rank(int p, int x) {\n    if (tr[p].key == x) {\n        return tr[tr[p].l].sz + 1;\n    }\n    else if (x < tr[p].key) {\n        return look_for_rank(tr[p].l, x);\n    }\n    else  {\n        return tr[tr[p].l].sz + tr[p].cnt + look_for_rank(tr[p].r, x);\n    }\n}\n<\/code><\/pre>\n
Splay<\/h4>\n
 \u7b80\u6982\uff1a\u6bcf\u64cd\u4f5c\u4e00\u6b21\u540e\uff0c\u5c06\u8be5\u64cd\u4f5c\u540e\u7684\u8282\u70b9\u65cb\u8f6c\u5230\u6839\u8282\u70b9<\/p>\n
struct node{\n    int s[2], p, v; \/\/ s\uff1a \u4e24\u4e2a\u5b50\u8282\u70b9\u7f16\u53f7\uff0c p\uff1a \u7236\u8282\u70b9\u7f16\u53f7 v\uff1a\u5f53\u524d\u70b9\u6743\u503c\n    int sz, flag;\n    void init(int _v, int _p) {\n        v = _v, p = _p;\n        sz = 1;\n    }\n\n}tr[N];\nint root, idx; \n\nvoid pushup(int u) {\n    tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;\n    \/\/ \u81ea\u5b9a\u4e49\n}\nvoid pushdown(int u) {\n    if (tr[u].flag) {\n        swap(tr[u].s[0], tr[u].s[1]);\n        tr[tr[u].s[0]].flag ^= 1;\n        tr[tr[u].s[1]].flag ^= 1;\n        tr[u].flag = 0;\n    }\n\n}\n\n\/\/ \u5de6\u53f3\u65cb\u5408\u5e76\u5199\u6cd5\nvoid rotate(int u) {\n    int y = tr[u].p, z = tr[y].p;\n    int k = tr[y].s[1] == u;\n    tr[z].s[tr[z].s[1] == y] = u, tr[u].p = z;\n    tr[y].s[k] = tr[u].s[k ^ 1], tr[tr[u].s[k ^ 1]].p = y;\n    tr[u].s[k ^ 1] = y, tr[y].p = u;\n    pushup(u), pushup(y);\n}\n\nvoid splay(int u, int k) {\n    while (tr[u].p != k) {\n        int y = tr[u].p, z = tr[y].p;\n        if (z != k) {\n            if ((tr[y].s[1] == u) ^ (tr[z].s[1] == y) ) rotate(u);\n            else rotate(y);\n        }\n        rotate(u);\n    }\n    if (!k) root = u;\n}\n\n\/\/ \u63d2\u5165\u4e00\u4e2a\u6570\nvoid insert(int v) {\n    int u = root, p = 0;\n    while (u) {\n        p = u, u = tr[u].s[v > tr[u].v];\n    }\n    u = ++ idx; \/\/ \u8282\u70b9\u7f16\u53f7\u4ece 1 \u5f00\u59cb\n    if (p) tr[p].s[v > tr[p].v] = u;\n    tr[u].init(v, p);\n    splay(u, 0); \/\/ \u8f6c\u5230 \u6839\u8282\u70b9\n}\n<\/code><\/pre>\n
\u83ab\u961f<\/h3>\n
 \u7b80\u6982\uff1a1.\u5206\u5757\uff1b2.\u6bcf\u4e2a\u5904\u7406\u533a\u95f4\u6309\u5de6\u7aef\u70b9\u7684\u6240\u5728\u5757\u6392\u5e8f\uff0c\u53f3\u7aef\u70b9\u4ece\u5de6\u5230\u53f3\u6392\u5e8f\uff1b3.\u5904\u7406\u6bcf\u4e2a\u64cd\u4f5c\u533a\u95f4<\/p>\n
\u6811\u94fe\u5256\u5206<\/h3>\n
 \u7b80\u6982\uff1a1.\u6839\u636e\u5b50\u8282\u70b9\u7684\u6743\u503c\u5927\u5c0f\u5206\u4e3a\u91cd\u8f7b\u513f\u5b50\uff1b2.\u5f53\u524d\u8282\u70b9\u8fde\u5411\u91cd\u513f\u5b50\u4e3a\u91cd\u8fb9\uff0c\u5176\u4f59\u8f7b\u8fb9; 3.\u91cd\u8fb9 \u6784\u6210\u7684\u6781\u5927\u8def\u5f84\u4e3a\u91cd\u94fe
\n
\"\"<\/div>
\n
\"\"<\/div><\/p>\n
int h[N], w[N], e[M], ne[M], idx; \/\/\u5efa\u6811\nint id[N], nw[N], cnt; \/\/id:\u8282\u70b9\u7684dfn\u5e8f\u7f16\u53f7\uff0cnw[id[i]]\u662fi\u7684\u6743\u503cw\uff08w -> nw\u7684\u6620\u5c04\uff09\nint dep[N], sz[N], top[N], fa[N], son[N];\n\/\/sz:\u5b50\u6811\u8282\u70b9\u4e2a\u6570\uff0ctop:\u91cd\u94fe\u7684\u9876\u70b9\uff0cson:\u91cd\u513f\u5b50\uff0cfa:\u7236\u8282\u70b9\nstruct SegmentTree\n{\n    int l, r;\n    LL sum, flag;\n}tr[N << 2];\n\nvoid add(int a, int b)\n{\n    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;\n}\n\/\/dfs1\u9884\u5904\u7406\nvoid dfs1(int u, int father, int depth)\n{\n    dep[u] = depth, fa[u] = father, sz[u] = 1;\n    for (int i = h[u]; ~i; i = ne[i])\n    {\n        int j = e[i];\n        if (j == father) continue;\n        dfs1(j, u, depth + 1);\n        sz[u] += sz[j];\n        if (sz[son[u]] < sz[j]) son[u] = j; \/\/\u91cd\u513f\u5b50\u662f\u5b50\u6811\u8282\u70b9\u6700\u591a\u7684\u513f\u5b50\n    }\n}\n\/\/dfs2\u505a\u5256\u5206\uff08t\u662f\u91cd\u94fe\u7684\u9876\u70b9\uff09\nvoid dfs2(int u, int t)\n{   \/\/ id \u4e3a\u6bcf\u4e2a\u8282\u70b9\u5206\u914d\u7f16\u53f7\uff0c nw \u4e3a w \u7684\u6620\u5c04\uff0c top \u4e3a\u5f53\u524d\u8282\u70b9 u \u7684\u91cd\u94fe\u9876\u70b9\n    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;\n    if (!son[u]) return; \/\/\u53f6\u8282\u70b9\u7ed3\u675f\n    dfs2(son[u], t); \/\/\u91cd\u513f\u5b50\u91cd\u94fe\u5256\u5206\n    \/\/\u5904\u7406\u8f7b\u513f\u5b50\n    for (int i = h[u]; ~i; i = ne[i])\n    {\n        int j = e[i];\n        if (j == fa[u] || j == son[u]) continue;\n        dfs2(j, j); \/\/\u8f7b\u513f\u5b50\u7684\u91cd\u94fe\u9876\u70b9\u5c31\u662f\u4ed6\u81ea\u5df1\n    }\n}\n\n\/\/------------------------\u7ebf\u6bb5\u6811\u7684\u90e8\u5206------------------------\\\\\n\nvoid pushup(int u)\n{\n    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;\n}\n\nvoid pushdown(int u)\n{\n    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];\n    if (root.flag)\n    {\n        left.sum += root.flag * (left.r - left.l + 1);\n        left.flag += root.flag;\n        right.sum += root.flag * (right.r - right.l + 1);\n        right.flag += root.flag;\n        root.flag = 0;\n    }\n}\n\nvoid build(int u, int l, int r)\n{\n    tr[u] = {l, r, nw[r], 0};\n    if (l == r) return;\n    int mid = l + r >> 1;\n    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);\n    pushup(u);\n}\n\nvoid update(int u, int l, int r, int k)\n{\n    if (l <= tr[u].l && r >= tr[u].r)\n    {\n        tr[u].flag += k;\n        tr[u].sum += k * (tr[u].r - tr[u].l + 1);\n        return;\n    }\n    pushdown(u);\n    int mid = tr[u].l + tr[u].r >> 1;\n    if (l <= mid) update(u << 1, l, r, k);\n    if (r > mid) update(u << 1 | 1, l, r, k);\n    pushup(u);\n}\n\nLL query(int u, int l, int r)\n{\n    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;\n    pushdown(u);\n    int mid = tr[u].l + tr[u].r >> 1;\n    LL res = 0;\n    if (l <= mid) res += query(u << 1, l, r);\n    if (r > mid) res += query(u << 1 | 1, l, r);\n    return res;\n}\n\n\/\/------------------------\u7ebf\u6bb5\u6811\u7684\u90e8\u5206------------------------\\\\\n\nvoid update_path(int u, int v, int k)\n{\n    while (top[u] != top[v])    \/\/\u5411\u4e0a\u722c\u627e\u5230\u76f8\u540c\u91cd\u94fe\n    {\n        if (dep[top[u]] < dep[top[v]]) swap(u, v);\n        update(1, id[top[u]], id[u], k);    \/\/dfs\u5e8f\u539f\u56e0\uff0c\u4e0a\u9762\u8282\u70b9\u7684id\u5fc5\u7136\u5c0f\u4e8e\u4e0b\u9762\u8282\u70b9\u7684id\n        u = fa[top[u]];\n    }\n    if (dep[u] < dep[v]) swap(u, v);\n    update(1, id[v], id[u], k); \/\/\u5728\u540c\u4e00\u91cd\u94fe\u4e2d\uff0c\u5904\u7406\u5269\u4f59\u533a\u95f4\n}\nLL query_path(int u, int v)\n{\n    LL res = 0;\n    while (top[u] != top[v])    \/\/\u5411\u4e0a\u722c\u627e\u5230\u76f8\u540c\u91cd\u94fe\n    {\n        if (dep[top[u]] < dep[top[v]]) swap(u, v);\n        res += query(1, id[top[u]], id[u]);\n        u = fa[top[u]];\n    }\n    if (dep[u] < dep[v]) swap(u, v);\n    res += query(1, id[v], id[u]);  \/\/\u5728\u540c\u4e00\u91cd\u94fe\u4e2d\uff0c\u5904\u7406\u5269\u4f59\u533a\u95f4\n    return res;\n}\nvoid update_tree(int u, int k) \/\/\u5b50\u6811\u5168\u90e8\u52a0\u4e0ak\n{\n    update(1, id[u], id[u] + sz[u] - 1, k); \/\/\u7531\u4e8edfs\u5e8f\u7684\u539f\u56e0\uff0c\u53ef\u4ee5\u5229\u7528\u5b50\u6811\u8282\u70b9\u4e2a\u6570\u76f4\u63a5\u627e\u5230\u533a\u95f4\n}\nLL query_tree(int u)\n{\n    return query(1, id[u], id[u] + sz[u] - 1); \/\/\u539f\u56e0\u540c\u4e0a\n}\n\nint main() {\n    \/\/ \u9884\u5904\u7406\n    dfs1(1, -1, 1);\n    \/\/ \u6811\u94fe\u5256\u5206\n    dfs2(1, 1);\n    \/\/ \u7ebf\u6bb5\u6811\u7ef4\u62a4\n    build(1, 1, n); \n}\n<\/code><\/pre>\n
\u52a8\u6001\u6811<\/h3>\n
 \u7b80\u6982\uff1a1.\u4efb\u610f\u9009\u4e00\u6761\u8fde\u5411\u5b50\u8282\u70b9\u7684\u8fb9\u4e3a\u5b9e\u8fb9\uff1b2.\u5b9e\u8fb9\u6784\u6210\u7684\u6781\u5927\u8def\u5f84\u4e3a\u5b9e\u94fe\uff1b3.\u7528 Splay \u7ef4\u62a4\u6bcf\u4e2a\u5b9e\u94fe
\n\u53c2\u8003\u6587\u7ae0<\/a>
\n
\"\"<\/div><\/p>\n
struct Splay\n{\n    int s[2], p, v;\n    int sum, rev; \/\/ \u81ea\u5b9a\u4e49\n}tr[N];\n\nbool isroot(int u)  \/\/\u5224\u65ad u \u662f\u5426\u4e3a\u5b9e\u94fe\u7684\u9876\u90e8\n{\n    return tr[tr[u].p].s[0] != u && tr[tr[u].p].s[1] != u;\n}\n\/\/------------------Splay\u7cfb\u51fd\u6570------------------\\\\\n\nvoid pushup(int u)\n{\n    tr[u].sum = tr[tr[u].s[0]].sum ^ tr[u].v ^ tr[tr[u].s[1]].sum;\n}\nvoid pushrev(int u)\n{\n    swap(tr[u].s[0], tr[u].s[1]);\n    tr[u].rev ^= 1;\n}\nvoid pushdown(int u)\n{\n    if (tr[u].rev)\n    {\n        pushrev(tr[u].s[0]);\n        pushrev(tr[u].s[1]);\n        tr[u].rev = 0;\n    }\n}\nvoid rotate(int x)\n{\n    int y = tr[x].p, z = tr[y].p;\n    int k = tr[y].s[1] == x;\n    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x; \/\/\u552f\u4e00\u7684\u4e0d\u540c\u5904\n    tr[x].p = z;\n    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;\n    tr[x].s[k ^ 1] = y, tr[y].p = x;\n    pushup(y), pushup(x);\n}\nvoid splay(int x)   \/\/\u8fed\u4ee3\u5199\u6cd5\n{\n    static int stk[N];  \/\/\u5148\u81ea\u4e0a\u800c\u4e0b\u4e0b\u4f20\u61d2\u6807\u8bb0\n    int tt = 0, t = x;\n    stk[ ++ tt] = t;\n    while (!isroot(t)) stk[ ++ tt] = t = tr[t].p;\n    while (tt) pushdown(stk[tt -- ]);\n    \/\/\u63a5\u4e0b\u6765\u57fa\u672c\u4e0esplay\u677f\u5b50\u76f8\u540c\n    while (!isroot(x))\n    {\n        int y = tr[x].p, z = tr[y].p;\n        if (!isroot(y))\n            if ((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) rotate(x);\n            else rotate(y);\n        rotate(x);\n    }\n}\n\/\/------------------Splay\u7cfb\u51fd\u6570------------------\\\\\n\nvoid access(int x)  \/\/\u5efa\u7acb\u4e00\u6761\u4ece\u6839\u8282\u70b9\u5230 x \u7684\u5b9e\u94fe\uff08\u540c\u65f6\u5c06 x \u53d8\u6210\u5bf9\u5e94 splay \u7684\u6839\u8282\u70b9\uff09\n{\n    int z = x;  \/\/\u8bb0\u5f55\u521d\u59cb\u7684\u8282\u70b9\u7f16\u53f7\n    for (int y = 0; x; y = x, x = tr[x].p) \/\/x\u6cbf\u7740\u865a\u8fb9\u5f80\u4e0a\u627e\u6839\n    {\n        splay(x);   \/\/\u5148\u8f6c\u5230\u5f53\u524d\u8f85\u52a9\u6811\u7684\u6839\n        tr[x].s[1] = y, pushup(x);  \/\/\u628a\u4e0a\u4e2a\u6811\u63a5\u5230\u4e2d\u5e8f\u904d\u5386\u540e\u9762\n    }\n    splay(z);   \/\/\u628a\u521d\u59cb\u7684\u8282\u70b9\u8f6c\u5230\u6839\n}\nvoid makeroot(int x) \/\/\u5c06 x \u53d8\u6210\u539f\u6811\u7684\u6839\u8282\u70b9\uff08\u4e14\u5de6\u5b50\u6811\u4e3a\u7a7a\uff09\n{\n    access(x);  \/\/\u6b64\u65f6x\u4e3a\u8f85\u52a9\u6811\u7684\u6839\u8282\u70b9\uff0c\u76f4\u63a5\u53cd\u8f6c\u4e2d\u5e8f\u904d\u5386\u5373\u53ef\n    pushrev(x);\n}\nint findroot(int x) \/\/\u627e\u5230 x \u6240\u5728\u7684\u539f\u6811\u7684\u6839\u8282\u70b9\uff0c\u518d\u5c06\u539f\u6811\u7684\u6839\u8282\u70b9\u65cb\u8f6c\u5230\u8f85\u52a9\u6811\u7684\u6839\u8282\u70b9\n{\n    access(x);  \/\/\u6253\u901a\u6839\u8282\u70b9\u5230 x \u7684\u5b9e\u94fe\uff0c\u5f53\u524d x \u4f4d\u4e8e\u8f85\u52a9\u6811\u7684\u6839\u8282\u70b9\u4f4d\u7f6e\n    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];  \/\/\u627e\u5230\u8f85\u52a9\u6811\u4e2d\u5e8f\u904d\u5386\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\uff08\u5de6\u4e0b\u89d2\uff09\n    splay(x);   \/\/\u8f6c\u5230\u6839\u8282\u70b9\n    return x;\n}\nvoid split(int x, int y)    \/\/\u5c06 x \u5230 y \u7684\u8def\u5f84\u53d8\u4e3a\u5b9e\u8fb9\u8def\u5f84\n{\n    makeroot(x);    \/\/\u5148\u628a x \u8bbe\u4e3a\u6839\n    access(y);      \/\/\u5728\u6253\u901a\u6839\u5230 y \u7684\u5b9e\u94fe\u5373\u53ef\n}\nvoid link(int x, int y) \/\/\u82e5 x , y \u4e0d\u8fde\u901a\uff0c\u5219\u52a0\u5165 (x, y) \u8fd9\u6761\u8fb9\n{\n    makeroot(x);    \/\/\u5148\u628a x \u8bbe\u4e3a\u6839\n    if (findroot(y) != x) tr[x].p = y;  \/\/\u5982\u679c\u4e0d\u8fde\u901a\uff0c\u5219\u628a x \u7684\u5b9e\u94fe\u63a5\u5230 y \u4e0a\u5373\u53ef\n}\nvoid cut(int x, int y)  \/\/\u82e5\u8fb9 (x, y) \u5b58\u5728\uff0c\u5219\u5220\u6389\uff08x, y\uff09\u8fd9\u6761\u8fb9\n{\n    makeroot(x);\n    if (findroot(y) == x && tr[x].s[1] == y && !tr[y].s[0])\n    {\n        tr[y].p = tr[x].s[1] = 0;\n        pushup(x);\n    }\n}\n<\/code><\/pre>\n
\u5de6\u504f\u6811<\/h3>\n
 \u7b80\u6982\uff1a\u6bcf\u4e2a\u8282\u70b9\u6709\u4e00\u4e2a dist, \u8868\u793a\u5f53\u524d\u8282\u70b9\u5230\u7a7a\u8282\u70b9\u7684\u6700\u8fd1\u8ddd\u79bb\u3002\u5176\u4e2d\u5de6\u8282\u70b9\u7684 dist \u5927\u4e8e\u53f3\u8282\u70b9\u7684 dist;<\/p>\n
struct T{\n    int l, r, v, d, f;\n    \/\/ l, r \u8868\u793a\u5de6\u53f3\u513f\u5b50, v \u8868\u793a\u503c\n    \/\/ d \u8868\u793a\u4ece\u5f53\u524d\u8282\u70b9\u5230\u6700\u8fd1\u53f6\u5b50\u8282\u70b9\u7684\u8ddd\u79bb, f \u8868\u793a\u5f53\u524d\u8282\u70b9\u7684\u7236\u4eb2\n} t[N];\n\nint find(int x) {\n    return t[x].f == x ? x : t[x].f = find(t[x].f);\n}\n\nint merge(int x, int y) { \/\/ \u9012\u5f52\u5408\u5e76\u51fd\u6570\n    if (!x || !y) return x + y;\n    if (t[x].v > t[y].v || (t[x].v == t[y].v && x > y)) swap(x, y);\n    rs = merge(rs, y);\n    if (t[ls].d < t[rs].d) swap(ls, rs);\n    t[x].d = t[rs].d + 1;\n    return x;\n}\n\nint work(int x, int y) { \/\/ \u5408\u5e76 x, y \u4e24\u4e2a\u5806\u3002\n    if (x == y) return 0;\n    if (!x || !y) return t[x + y].f = x + y;\n    if (t[x].v > t[y].v || (t[x].v == t[y].v && x > y)) swap(x, y);\n    t[x].f = t[y].f = x;\n    merge(x, y); return x;\n}\n\nvoid del(int x) { \/\/ \u5220\u9664\u4e00\u4e2a\u6570\n    t[x].f = work(ls, rs);\n}<\/code><\/pre>\n
\u540e\u7f00\u6570\u7ec4<\/h3>\n
\/\/x--\u5b58\u50a8\u7b2c\u4e00\u5173\u952e\u5b57\n\/\/y--\u5b58\u50a8\u7b2c\u4e8c\u5173\u952e\u5b57\n\/\/c--\u5b58\u50a8\u6bcf\u4e2a\u6570\u503c\u7684\u6570\u76ee\n\/\/rk--rk[i]\u8868\u793a\u4ecei\u5f00\u59cb\u7684\u540e\u7f00\u7684\u6392\u540d\n\/\/sa--sa[i]\u8868\u793a\u6392\u540d\u4e3ai\u7684\u540e\u7f00\u7684\u8d77\u59cb\u4e0b\u6807\n\/\/h--h[i]\u8868\u793a\u6392\u540d\u4e3ai\u7684\u540e\u7f00\u548c\u6392\u540d\u4e3ai - 1\u7684\u540e\u7f00\u7684\u6700\u957f\u524d\u7f00 \nint x[N], y[N], c[N], rk[N], sa[N], h[N];\nchar s[N];\nvoid get_sa(){\n    for(int i = 1 ; i <= n ; ++i) c[x[i] = s[i]]++;\n    for(int i = 2 ; i <= m ; ++i) c[i] += c[i - 1];\n    for(int i = n ; i ; --i) sa[c[x[i]]--] = i;\n    for(int k = 1 ; k <= n ; k <<= 1){\n        int num = 0;\n        \/\/\u5148\u6309\u7167\u7b2c\u4e8c\u5173\u952e\u5b57\u6392\u5e8f\uff0c\u4e0b\u6807\u4ecei\u5f00\u59cb\u7684\u540e\u7f00\u7684\u7b2c\u4e8c\u5173\u952e\u5b57\u4e3a\u4ecei+k\u5f00\u59cb\u7684\u7b2c\u4e00\u5173\u952e\u5b57 \n        \/\/\u5148\u5c06\u65e0\u7b2c\u4e8c\u5173\u952e\u5b57\u7684\u540e\u7f00\u6392\u5148\u540d\uff0c\u6b64\u65f6y[i]\u8868\u793a\u6309\u7167\u7b2c\u4e8c\u5173\u952e\u5b57\u6392\u540d\u4e3ai\u7684\u8d77\u59cb\u4e0b\u6807 \n        for(int i = n - k + 1 ; i <= n ; ++i) y[++num] = i;\n        for(int i = 1 ; i <= n ; ++i){\n            \/\/\u4e0a\u4e00\u5c42\u5faa\u73af\u4e2d\u6309\u7167\u7b2c\u4e00\u5173\u952e\u5b57\u7684\u6392\u540d\u7684\u4e0b\u6807\u5df2\u7ecf\u5b58\u5728sa\u6570\u7ec4\u4e2d\n            \/\/\u6309\u4ece\u5c0f\u5230\u5927\u987a\u5e8f\u679a\u4e3esa\u6570\u7ec4\u53ef\u4fdd\u8bc1\u6309\u7167\u7b2c\u4e00\u5173\u952e\u5b57\u4ece\u5c0f\u5230\u5927\n            \/\/\u6240\u6709\u8d77\u59cb\u4e0b\u6807\u8d85\u8fc7k\u624d\u5b58\u5728\u7b2c\u4e8c\u5173\u952e\u5b57\n            \/\/\u5c06\u6240\u6709\u5b58\u5728\u7b2c\u4e8c\u5173\u952e\u5b57\u7684\u540e\u7f00\u5b58\u50a8\u5728y\u6570\u7ec4\u4e2d\uff0c\u6b64\u65f6\u662f\u6309i + k\u7684\u7b2c\u4e00\u5173\u952e\u5b57\uff0c\u4e0b\u6807\u8981-k \n            if(sa[i] > k) y[++num] = sa[i] - k;\n        } \n        \/\/\u5c06\u8ba1\u6570\u6570\u7ec4\u6e05\u7a7a \n        for(int i = 1 ; i <= m ; ++i) c[i] = 0;\n        for(int i = 1 ; i <= n ; ++i) c[x[i]]++;\n        for(int i = 2 ; i <= m ; ++i) c[i] += c[i - 1];\n        \/\/y\u6570\u7ec4\u5b58\u50a8\u7684\u662f\u6309\u7167\u7b2c\u4e8c\u5173\u952e\u5b57\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\u540e\u7684\u540e\u7f00\u7684\u8d77\u59cb\u4e0b\u6807 \n        \/\/i\u4ece\u5927\u5230\u5c0f\u679a\u4e3e\u5373\u53ef\u4fdd\u8bc1\u6309\u7167\u7b2c\u4e00\u5173\u952e\u5b57\u6392\u5e8f\u540e\u4f9d\u7136\u662f\u6309\u7167\u7b2c\u4e8c\u5173\u952e\u5b57\u6392\u5e8f\u540e\u7684\u76f8\u5bf9\u987a\u5e8f\u4e0d\u53d8 \n        for(int i = n ; i ; --i) sa[c[x[y[i]]]--] = y[i],y[i] = 0;\n        swap(x,y),num = 1;\n        \/\/\u5c06\u6240\u6709\u540e\u7f00\u79bb\u6563\u5316 \n        x[sa[1]] = 1;\n        \/\/\u6b64\u65f6y\u5b58\u50a8\u7684\u662f\u4ecei\u5f00\u59cb\u7684\u540e\u7f00\u7684\u7b2c\u4e00\u5173\u952e\u5b57 \n        for(int i = 2 ; i <= n ; ++i){\n            \/\/\u82e5\u5f53\u524d\u540e\u7f00\u548c\u6392\u540d\u524d\u4e00\u4f4d\u7684\u540e\u7f00\u7b2c\u4e00\u5173\u952e\u5b57\u548c\u7b2c\u4e8c\u5173\u952e\u5b57\u76f8\u540c\u5219\u79bb\u6563\u5316\u540e\u7684\u6570\u503c\u76f8\u540c\uff0c\u5426\u5219+1 \n            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] and y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;\n        } \n        if(num == n) break;\n        m = num;\n    }\n}\nvoid get_h(){ \n    for(int i = 1 ; i <= n ; ++i) rk[sa[i]] = i;\n    for(int i = 1,k = 0 ; i <= n ; ++i){\n        if(rk[i] == 1) continue; \n        \/\/h[rk[i]] >= h[rk[i - 1]] - 1\n        if(k) k--;\n        \/\/j\u4e3a\u6392\u540d\u524d\u4e00\u4f4d\u7684\u8d77\u59cb\u4e0b\u6807 \n        int j = sa[rk[i] - 1];\n        \/\/\u6c42\u6700\u957f\u76f8\u540c\u524d\u7f00 \n        while(i + k <= n and j + k <= n and s[i + k] == s[j + k]) k++;\n        h[rk[i]] = k;\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u57fa\u672c\u6570\u636e\u7ed3\u6784 \u5355\u94fe\u8868 \/\/ head\u5b58\u50a8\u94fe\u8868\u5934\uff0ce[]\u5b58\u50a8\u8282\u70b9\u7684\u503c\uff0cne[]\u5b58\u50a8\u8282\u70b9\u7684next\u6307\u9488\uff0cidx\u8868\u793a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[19,25],"class_list":["post-129","post","type-post","status-publish","format-standard","hentry","category-science-and-engineering","tag-data-structure","tag-algorithm-templates"],"_links":{"self":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=129"}],"version-history":[{"count":7,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/129\/revisions"}],"predecessor-version":[{"id":336,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/129\/revisions\/336"}],"wp:attachment":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}