bzoj 1146 网络管理Network (CDQ 整体二分 + 树刨）

缺乏、安全感 2021-12-15 14:51 190阅读 0赞

[题目传送门][Link 1]

题意：求树上路径可修改的第k大值是多少。

题解：CDQ整体二分+树刨。

每一个位置上的数都会有一段持续区间

根据CDQ拆的思维，可以将这个数拆成出现的时间点和消失的时间点。

然后通过整体二分第k大思路 + 树炮询问路径上出现点的个数就好了。

说一下整体二分的思路。

先假设第k大的值是mid， 然后按照时间顺序，出现一个数<=mid标记这个数的位置为1， 消失一个数<=mid，标记这个数的位置为0。

然后对于询问来说，询问路径上的值， 与 k进行比较， 如果 值 >= k则说明这个询问的第k大落在区间\[ l, mid\]之间， 否则落在 \[mid+1,r\]之间，并且第k大是在\[mid+1,r\] 的 k -= 路劲值。

然后将所有 修改且值 <= mid 和 询问第k大落在左边的 询问放到 数组的左边， 其他放到数组的右边， 然后递归下去处理左边 / 右边的这个区间。

这样每个操作最多只会访问lg次。

每次操作的复杂度是lg\*lg。

所以最后的复杂度是n\*lg^3.

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define Fop freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
    #define LL long long
    #define ULL unsigned LL
    #define fi first
    #define se second
    #define pb push_back
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lch(x) tr[x].son[0]
    #define rch(x) tr[x].son[1]
    #define max3(a,b,c) max(a,max(b,c))
    #define min3(a,b,c) min(a,min(b,c))
    typedef pair<int,int> pll;
    const int inf = 0x3f3f3f3f;
    const int _inf = 0xc0c0c0c0;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const LL _INF = 0xc0c0c0c0c0c0c0c0;
    const LL mod =  (int)1e9+7;
    const int N = 8e5 + 100;
    const int M = 2 * N;
    int head[N], to[M], nt[M];
    int sz[N], son[N], deep[N], top[N], fa[N], dfn[N], dto[N], tr[N<<2];
    int tot, dtot;
    int n;
    int a[N];
    struct Node{
        int k, a, b, id;
    }A[M], B[M], C[M];
    /**
    k == -1 Add -> pos[a] = b
    k == -2 Del -> pos[a] = 0
    else k Query with ans[id]
    **/
    void add(int u, int v){
        to[tot] = v; nt[tot] = head[u]; head[u] = tot++;
    
        to[tot] = u; nt[tot] = head[v]; head[v] = tot++;
    }
    void dfs1(int o, int u){
        sz[u] = 1;
        for(int i = head[u]; ~i; i = nt[i]){
            int v = to[i];
            if(v == o) continue;
            dfs1(u, v);
            if(sz[v] > sz[son[u]]) son[u] = v;
            sz[u] += sz[v];
        }
    }
    void dfs2(int o, int u, int t){
        deep[u] = deep[o] + 1;
        top[u] = t;
        fa[u] = o;
        dfn[u] = ++dtot;
        dto[dtot] = u;
        if(son[u]) dfs2(u, son[u], t);
        for(int i = head[u]; ~i; i = nt[i]){
            int v = to[i];
            if(v == o || v == son[u]) continue;
            dfs2(u, v, v);
        }
    }
    void PushUp(int rt){
        tr[rt] = tr[rt<<1] + tr[rt<<1|1];
    }
    int Query(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R)
            return tr[rt];
        int m = l+r >> 1;
        int ret = 0;
        if(L <= m) ret += Query(L, R, lson);
        if(m < R) ret += Query(L, R, rson);
        return ret;
    }
    void Updata(int L, int C, int l, int r, int rt){
        if(l == r){
            tr[rt] = C;
            return ;
        }
        int m = l+r >> 1;
        if(L <= m) Updata(L, C, lson);
        else Updata(L, C, rson);
        PushUp(rt);
        return ;
    }
    int Query_Path(int x, int y){
        int fx = top[x], fy = top[y];
        int ret = 0;
        while(fx != fy){
            if(deep[fx] > deep[fy]){
                ret += Query(dfn[fx],dfn[x],1,n,1);
                x = fa[fx]; fx = top[x];
            }
            else {
                ret += Query(dfn[fy],dfn[y],1,n,1);
                y = fa[fy]; fy = top[y];
            }
        }
        if(deep[x] < deep[y]) ret += Query(dfn[x], dfn[y], 1, n, 1);
        else ret += Query(dfn[y], dfn[x], 1, n,1);
        return ret;
    }
    int lca(int x, int y){
        int fx = top[x], fy = top[y];
        while(fx != fy){
            if(deep[fx] > deep[fy])
                x = fa[fx]; fx = top[x];
            else
                y = fa[fy]; fy = top[y];
        }
        if(deep[x] < deep[y]) return x;
        return y;
    }
    void init(){
        memset(head, -1, sizeof(head));
        memset(son, 0, sizeof son);
        tot = dtot = 0;
    }
    int atot = 0;
    void AddNode(int op, int a, int b, int id){
        A[++atot] = {op, a, b, id};
    }
    int ans[N];
    void cdq(int ansl, int ansr, int l, int r){
        if(l > r) return ;
        if(ansl == ansr){
            for(int i = l; i <= r; ++i)
                if(A[i].id)
                    ans[A[i].id] = ansl;
            return ;
        }
        int mid = ansl+ansr >> 1;
        int tb = 0, tc = 0;
        for(int i = l; i <= r; ++i){
            if(A[i].k == -1){
                if(A[i].b <= mid){
                    B[++tb] = A[i];
                    Updata(dfn[A[i].a], 1, 1, n, 1);
                }
                else {
                    C[++tc] = A[i];
                }
            }
            else if(A[i].k == -2){
                if(A[i].b <= mid){
                    B[++tb] = A[i];
                    Updata(dfn[A[i].a], 0, 1, n, 1);
                }
                else
                    C[++tc] = A[i];
            }
            else {
                int kk = Query_Path(A[i].a, A[i].b);
                if(kk >= A[i].k)
                    B[++tb] = A[i];
                else
                    A[i].k -= kk;
                    C[++tc] = A[i];
            }
        }
        for(int i = 1; i <= tb; ++i)
            A[i+l-1] = B[i];
        for(int i = 1; i <= tc; ++i)
            A[tb+l+i-1] = C[i];
        cdq(ansl, mid, l, tb+l-1);
        cdq(mid+1, ansr, tb+l, r);
    }
    int main(){
        init();
        int q;
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            AddNode(-1, i, a[i], 0);
        }
        int x, y;
        for(int i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            add(x, y);
        }
        int m = 0;
        dfs1(1,1);
        dfs2(1,1,1);
        int k;
        for(int i = 1; i <= q; ++i){
            scanf("%d%d%d", &k, &x, &y);
            if(k) {
                int z = lca(x,y);
                z = deep[x] + deep[y] - deep[z] * 2 + 1;
                if(z < k){
                    ans[++m] = -1;
                }
                else AddNode(z-k+1, x, y, ++m);
            }
            else {
                AddNode(-2, x, a[x], 0);
                AddNode(-1, x, y, 0);
                a[x] = y;
            }
        }
        for(int i = 1; i <= n; ++i)
            AddNode(-2, i, a[i], 0)
        cdq(1, 1e8+10, 1, atot);
        for(int i = 1; i <= m; ++i)
            if(~ans[i]) printf("%d\n", ans[i]);
            else puts("invalid request!");
        return 0;
    }

转载于:https://www.cnblogs.com/MingSD/p/10805687.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1146
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/eb067bdb74be46e9b73419e8d773ee8d.png