{"id":729,"date":"2020-07-27T20:39:09","date_gmt":"2020-07-27T12:39:09","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=729"},"modified":"2022-02-23T16:52:31","modified_gmt":"2022-02-23T08:52:31","slug":"%e4%b8%bb%e5%b8%ad%e6%a0%91%e9%9b%86%e9%94%a6","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/07\/27\/%e4%b8%bb%e5%b8%ad%e6%a0%91%e9%9b%86%e9%94%a6\/","title":{"rendered":"\u4e3b\u5e2d\u6811\u96c6\u9526"},"content":{"rendered":"

Super Mario<\/a><\/h3>\n

\u9898\u610f\uff1an\u4e2a\u6570\uff0cm\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee(L,R,H)\uff0c\u8f93\u51fa\u533a\u95f4[L,R]\u4e2d\u5c0f\u4e8e\u7b49\u4e8eH\u7684\u6570\u6709\u591a\u5c11\u4e2a\u3002\u5728\u6c42\u533a\u95f4\u7b2ck\u5927\u7684\u57fa\u7840\u4e0a\uff0c\u52a0\u4e0a\u4e00\u4e2a\u4e8c\u5206\u5c31\u884c\u4e86\u3002\u5bf9\u533a\u95f4[0, R-L+1]\u8fdb\u884c\u4e8c\u5206\uff0c\u7b2ck\u5927\u7684\u6570\u548cH\u76f8\u6bd4\uff0c\u5bfb\u627e\u7b54\u6848\u3002
\n\/\/\u8fd8\u6709\u4e00\u79cd\u8f83\u4e3a\u7b80\u5355\u7684\u505a\u6cd5\uff0c\u5c06H\u8f6c\u6362\u4e3a\u79bb\u6563\u7684\u6570\u540e\uff0c\u76f4\u63a5\u5728\u76f8\u51cf\u540e\u7684\u7ebf\u6bb5\u6811\u91cc\u8fdb\u884c\u533a\u95f4\u67e5\u8be2\u5373\u53ef\u3002<\/p>\n

#include <cstdio>\n#include <cmath>\n#include <algorithm>\nusing namespace std;\nconst int maxn = 1e5+5;\nstruct num{\n    int val, idx, ser;\n}nums[maxn];\nint n, m;\n\nstruct tree{\n    int left, right, val;\n}tree[maxn*20];\nint top;\nint root[maxn];\nint ser[maxn];\n\ninline int build(int l, int r){\n    int tmp = ++top;\n    if (l==r){\n        tree[top].val = 0;\n        return tmp;\n    }\n    int mid = (l+r)>>1;\n    tree[tmp].left = build(l, mid);\n    tree[tmp].right = build(mid+1, r);\n    tree[tmp].val = 0;\n    return tmp;\n}\ninline int add(int src, int l, int r, int target_idx){\n    int tmp = ++top;\n    if (l==r){\n        tree[tmp].val = tree[src].val + 1;\n        return tmp;\n    }\n    int mid = (l+r)>>1;\n    if (mid >= target_idx){\n        tree[tmp].left = add(tree[src].left, l, mid, target_idx);\n        tree[tmp].right = tree[src].right;\n    }else{\n        tree[tmp].right = add(tree[src].right, mid+1, r, target_idx);\n        tree[tmp].left = tree[src].left;\n    }\n    tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;\n    return tmp;\n}\ninline int search(int rt1, int rt2, int l, int r, int k){\n    if (l==r){\n        return l;\n    }\n    int x = tree[tree[rt2].left].val - tree[tree[rt1].left].val;\n    int y = tree[tree[rt2].right].val - tree[tree[rt1].right].val;\n    int mid = (l+r)>>1;\n    if (x >= k) return search(tree[rt1].left, tree[rt2].left, l, mid, k);\n    return search(tree[rt1].right, tree[rt2].right, mid+1, r, k-x);\n}\ninline int read(){\n    int x=0;   char ch = getchar();\n    while (ch<'0' || ch>'9')    ch = getchar();\n    while (ch>='0' && ch<='9'){\n        x = x*10 + ch-'0';\n        ch = getchar();\n    }\n    return x;\n}\ninline bool cmp1(struct num a, struct num b){\n    if (a.val != b.val) return a.val < b.val;\n    return a.idx < b.idx;\n}\ninline bool cmp2(struct num a, struct num b){\n    return a.idx < b.idx;\n}\nint main(){\n    int t, L, R, H, k;\n    int l, r, mid;\n    int cas = 0;\n    t = read();\n    while (t--){\n        top = 0;\n        n = read(), m = read();\n        for (int i=1; i<=n; i++){\n            nums[i].val = read();\n            nums[i].idx = i;\n        }\n        sort (nums+1, nums+n+1, cmp1);\n        for (int i=1; i<=n; i++){\n            nums[i].ser = i;\n            ser[i] = nums[i].val;\n        }\n        sort (nums+1, nums+n+1, cmp2);\n        root[0] = build(1, n);\n        for (int i=1; i<=n; i++)\n            root[i] = add(root[i-1], 1, n, nums[i].ser);\n        printf ("Case %d:\\n", ++cas);\n        for (int i=1; i<=m; i++){\n            L = read()+1, R = read()+1, H = read();\n            l = 0, r = R-L+1;\n            while (l<r){\n                mid = ((l+r)>>1) + ((l+r)&1);\n                int tmp = ser[search(root[L-1], root[R], 1, n, mid)];\n                if (tmp <= H) l = mid;\n                else    r = mid-1;\n            }\n            printf ("%d\\n", l);\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n
P2633 Count on a tree<\/a><\/h4>\n
\u4e3b\u5e2d\u6811+LCA\u3002\u5bf9\u6bcf\u4e2a\u7ed3\u70b9\u7ed3\u70b9\u7ebf\u6bb5\u6811\uff0c\u8868\u793a\u4ece\u8be5\u7ed3\u70b9\u5230\u6839\u8282\u70b9\u8def\u5f84\u4e0a\u6240\u6709\u7ed3\u70b9\u7684\u6743\u503c\u5efa\u7acb\u8d77\u6765\u7684\u7ebf\u6bb5\u6811\u3002
\n\u8981\u6c42(u, v)\u8def\u5f84\u4e0a\u7b2ck\u5c0f\u503c\uff0c\u53ea\u9700\u6c42\u7ebf\u6bb5\u6811s[u]+s[v]-s[LCA(u,v)]-s[fa[LCA(u,v)]]\u4e0a\u7684\u7b2ck\u5c0f\u503c\u5373\u53ef<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int maxn = 1e5+5;\nint n, m;\n\n\/\/ \u6811\u90e8\u5206\u7684\u53d8\u91cf\nint val[maxn], head[maxn], lg[maxn], fa[maxn], dp[maxn][27], high[maxn];\nstruct edge{\n    int from, to, next;\n}e[maxn*2];\nint tot;\n\n\/\/\u79bb\u6563\u5316\nstruct value{\n    int idx, val;\n}value[maxn];\n\/\/ \u4e3b\u5e2d\u6811\u90e8\u5206\u7684\u53d8\u91cf           \u6ce8\u610f\uff1a\u4e3b\u5e2d\u6811\u7684\u533a\u95f4\u662f\u5efa\u7acb\u5728\u79bb\u6563\u540e\u7684\u6743\u503c\u6570\u91cf\u4e0a\u7684\uff0c\u8fd9\u548c\u6811\u7684\u7ed3\u70b9\u4e2a\u6570n\u76f8\u540c\nstruct tree{\n    int left, right, val;\n}tree[maxn*30];\nint top, cnt;       \/\/top\u8868\u793atree\u7684\u4f7f\u7528\u60c5\u51b5\uff0c cnt\u4e3a\u5f53\u524d\u5df2\u6709\u7684\u7ebf\u6bb5\u6811\u7248\u672c\nint root[maxn];\n\n\/\/\nint mp[maxn];            \/\/\u7ed3\u70b9i\u5bf9\u5e94\u7684\u4e3b\u5e2d\u6811\u7248\u672c\n\ninline int build(int l, int r){\n    int tmp = ++top;\n    if (l==r){\n        tree[tmp].val = 0;\n        return tmp;\n    }\n    int mid = (l+r)>>1;\n    tree[tmp].left = build(l, mid), tree[tmp].right = build(mid+1, r);\n    tree[tmp].val = 0;\n    return tmp;\n}\ninline int add(int src, int l, int r, int target_idx){\n    int tmp = ++top;\n    if (l==r){\n        tree[tmp].val = tree[src].val + 1;\n        return tmp;\n    }\n    int mid = (l+r)>>1;\n    if (mid >= target_idx){\n        tree[tmp].left = add(tree[src].left, l, mid, target_idx);\n        tree[tmp].right = tree[src].right;\n    }else{\n        tree[tmp].right = add(tree[src].right, mid+1, r, target_idx);\n        tree[tmp].left = tree[src].left;\n    }\n    tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;\n    return tmp;\n}\ninline int search(int rt1, int rt2, int rt3, int rt4, int l, int r, int k){            \/\/ u + v - LCA(u, v) - fa[LCA(u, v)]\n    if (l==r)   return l;\n    int x = tree[tree[rt1].left].val + tree[tree[rt2].left].val - tree[tree[rt3].left].val - tree[tree[rt4].left].val;\n    int y = tree[tree[rt1].right].val + tree[tree[rt2].right].val - tree[tree[rt3].right].val - tree[tree[rt4].right].val;\n    int mid = (l+r)>>1;\n    if (x>=k)   return search(tree[rt1].left, tree[rt2].left, tree[rt3].left, tree[rt4].left, l, mid, k);\n    else    return search(tree[rt1].right, tree[rt2].right, tree[rt3].right, tree[rt4].right, mid+1, r, k-x);\n}\n\ninline int LCA(int x, int y){\n    if (high[y] < high[x])  swap(x, y);\n    while (high[y] > high[x])   y = dp[y][lg[high[y]-high[x]]-1];\n    if (x==y)   return x;\n    for (int k=lg[high[x]]-1; k>=0; k--)    if (dp[x][k] != dp[y][k])\n        x = dp[x][k], y = dp[y][k];\n    return dp[x][0];\n}\ninline void dfs(int x, int y){\n    fa[x] = y;\n    high[x] = high[y] + 1;\n    root[++cnt] =  add(root[mp[y]], 1, n, val[x]);\n    mp[x]  = cnt;\n    for (int i=head[x]; i!=-1; i=e[i].next) if (!high[e[i].to])\n        dfs(e[i].to, x);\n    return;\n}\ninline void Add(int from, int to){\n    tot++;\n    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];\n    head[from] = tot;\n    return;\n}\ninline void init(){\n    for (int i=1; i<=n; i++)    lg[i] = lg[i-1] + (1<<lg[i-1]==i);\n    for (int i=1; i<=n; i++)    dp[i][0] = fa[i];\n    for (int k=1; k<=lg[n]-1; k++)  for (int i=1; i<=n; i++)\n        dp[i][k] = dp[dp[i][k-1]][k-1];\n    return;\n}\ninline int read(){\n    int x = 0;  char ch = getchar();\n    while (ch<'0' || ch>'9')    ch = getchar();\n    while (ch>='0' && ch<='9'){\n        x = x*10 + ch-'0';\n        ch = getchar();\n    }\n    return x;\n}\ninline bool cmp(struct value a, struct value b){\n    if (a.val != b.val)\n        return a.val < b.val;\n    return a.idx < b.idx;\n}\nint main(){\n    int from, to, last = 0, u, v, k;\n    n = read(), m = read();\n    for (int i=1; i<=n; i++){\n        value[i].val = read();\n        value[i].idx = i;\n    }\n    sort (value+1, value+n+1, cmp);\n    for (int i=1; i<=n; i++)    val[value[i].idx] = i;\n    top = 0;\n    root[0] = build(1, n);\n\n    memset (head, -1, sizeof head);     tot = 0;\n    for (int i=1; i<n; i++){\n        from = read(), to = read();\n        Add(from, to);  Add(to, from);\n    }\n    dfs(1, 0);\n    init();\n    for (int i=1; i<=m; i++){\n        u = read()^last, v = read(), k = read();\n        int tmp = LCA(u, v);\n        last = value[search(root[mp[u]], root[mp[v]], root[mp[tmp]], root[mp[fa[tmp]]], 1, n, k)].val;\n        printf ("%d\\n", last);\n    }\n    return 0;\n}<\/code><\/pre>\n
\u5c0f\u777f\u777f\u7684\u5144\u5f1f<\/a><\/h4>\n
bfs\u5e8f+\u4e3b\u5e2d\u6811+\u4e8c\u5206
\n\u5728bfs\u5e8f\u4e0a\u6784\u5efa\u4e3b\u5e2d\u6811\uff0c\u7136\u540e\u5bfb\u627e\u533a\u95f4\u4f7f\u7528\u4e8c\u5206\u3002\u5bfb\u627ekth-father\u4f7f\u7528\u500d\u589e\u3002
\n\u65f6\u95f4\u590d\u6742\u5ea6nlogn+mlog^{2}n<\/code><\/p>\n
#include <cstdio>\n#include <queue>\nusing namespace std;\nconst int maxn = 1e6+1;\nstruct edge{\n    int to, next;\n}e[maxn*2];\nint n, m;\nint val[maxn], head[maxn], tot;\nint lg[maxn], pow2[30], dp[maxn][22], depth[maxn];\nint BFS[maxn], mp1[maxn];\n\nstruct tree{            \/\/\u4e3b\u5e2d\u6811\u6570\u636e\u6c60\uff0cleft,right\u5de6\u53f3\u5b69\u5b50\uff0cval\u8be5\u533a\u95f4\u5185\u7684\u6570\u503c\u4e2a\u6570\n    int left, right, val;\n}tree[maxn*25];\nint root[maxn], top;         \/\/\u6bcf\u4e2a\u7248\u672c\u4e3b\u5e2d\u6811\u5728\u6570\u636e\u6c60\u4e2d\u7684\u4e0b\u6807   top\u6570\u636e\u6c60\u4f7f\u7528\u60c5\u51b5\n\ninline int fath(int x, int k){\n    \/\/k--;\n    while (k){\n        x = dp[x][lg[k]-1];\n        k -= pow2[lg[k]-1];\n    }\n    return x;\n}\n\ninline int src1(int l, int r, int k){\n    int t = fath(BFS[r], k), s = depth[BFS[r]], tmp = r;\n    int mid;\n    while (l<r){\n        mid = (l+r) >> 1;\n        if (depth[BFS[mid]] < s)    l = mid+1;\n        else    r = mid;\n    }\n    r = tmp;\n    while (l<r){\n        mid = (l+r) >> 1;\n        if (fath(BFS[mid], k)!=t)    l = mid+1;\n        else    r = mid;\n    }\n    return l;\n}\ninline int src2(int l, int r, int k){\n    int t = fath(BFS[l], k), s = depth[BFS[l]], tmp = l;\n    int mid;\n    while (l<r){\n        mid = ((l+r)>>1) + ((l+r)&1);\n        if (depth[BFS[mid]] > s)    r = mid-1;\n        else    l = mid;\n    }\n    l = tmp;\n    while (l<r){\n        mid = ((l+r)>>1) + ((l+r)&1);\n        if (fath(BFS[mid], k)!=t)    r = mid-1;\n        else    l = mid;\n    }\n    return l;\n}\n\ninline int add(int src, int l, int r, int target){\n    int tmp = ++top;\n    if (l==r){\n        tree[tmp].val = tree[src].val + 1;\n        return tmp;\n    }\n    int mid = (l+r)>>1;\n    if (target<=mid){\n        tree[tmp].left = add(tree[src].left, l, mid, target);\n        tree[tmp].right = tree[src].right;\n    }else{\n        tree[tmp].left = tree[src].left;\n        tree[tmp].right = add(tree[src].right, mid+1, r, target);\n    }\n    tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;\n    return tmp;\n}\ninline int search(int rt1, int rt2, int l, int r, int k){\n    if (k>tree[rt2].val-tree[rt1].val)  return -1;\n    if (l==r)   return l;\n    int x = tree[tree[rt2].left].val - tree[tree[rt1].left].val;\n    int y = tree[tree[rt2].right].val - tree[tree[rt1].right].val;\n    int mid = (l+r)>>1;\n    if (x>=k)   return search(tree[rt1].left, tree[rt2].left, l, mid, k);\n    return search(tree[rt1].right, tree[rt2].right, mid+1, r, k-x);\n}\ninline void bfs(){\n    queue<int> q;\n    int cnt = 0, tmp;\n    q.push(1);\n    while (!q.empty()){\n        tmp = q.front();    q.pop();\n        BFS[++cnt] = tmp, mp1[tmp] = cnt;\n        for (int i=head[tmp]; i; i=e[i].next)   if (!mp1[e[i].to])\n            q.push(e[i].to);\n    }\n    return;\n}\ninline void dfs(int u, int v){\n    dp[u][0] = v;\n    depth[u] = depth[v] + 1;\n    for (int i=head[u]; i; i=e[i].next) if (!depth[e[i].to])\n        dfs(e[i].to, u);\n    return;\n}\nvoid init(){\n    for (int i=1; i<=n; i++)    lg[i] = lg[i-1] + (1<<lg[i-1]==i);\n    pow2[0] = 1;\n    for (int i=1; i<=28; i++)    pow2[i] = 2*pow2[i-1];\n    dfs(1, 0);\n    for (int k=1; k<=lg[n]-1; k++)  for (int i=1; i<=n; i++)\n        dp[i][k] = dp[dp[i][k-1]][k-1];\n    return;\n}\n\ninline void AddEdge(int u, int v){\n    tot++;\n    e[tot].to = v, e[tot].next = head[u];\n    head[u] = tot;\n    return;\n}\ninline int read(){\n    int x=0;    char ch=getchar();\n    while (ch<'0' || ch>'9')    ch=getchar();\n    while (ch>='0' && ch<='9'){\n        x = x*10 + ch-'0';\n        ch=getchar();\n    }\n    return x;\n}\nint main(){\n    int u, v, last = 0, x, k, l, r;\n    n = read(), m = read();\n    for (int i=1; i<=n; i++)    val[i] = read();\n    for (int i=1; i<n; i++){\n        u = read(), v = read();\n        AddEdge(u, v);  AddEdge(v, u);\n    }\n    init();\n    bfs();\n    tree[0].left = tree[0].right = tree[0].val = 0;\n    top = 0;    root[0] = 0;\n    for (int i=1; i<=n; i++){\n        root[i] = add(root[i-1], 1, n, val[BFS[i]]);\n    }\n    for (int i=1; i<=m; i++){\n        x = (read()^last)%n+1, k = read();\n        if (k>depth[x]-1){\n            puts("?");\n            continue;\n        }\n        l = src1(1, mp1[x], k), r = src2(mp1[x], n, k);\n        int tmp = search(root[l-1], root[r], 1, n, k);\n        if (tmp==-1){\n            puts("?");\n            continue;\n        }\n        last = tmp;\n        printf ("%d\\n", last);\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Super Mario \u9898\u610f\uff1an\u4e2a\u6570\uff0cm\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee(L,R,H)\uff0c\u8f93\u51fa\u533a\u95f4[L,R]\u4e2d\u5c0f\u4e8e\u7b49\u4e8e […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[52],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/729"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=729"}],"version-history":[{"count":8,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/729\/revisions"}],"predecessor-version":[{"id":1311,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/729\/revisions\/1311"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=729"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=729"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=729"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}