标签: 并查集

[ONTAK2010]Peaks 题解

[ONTAK2010]Peaks 题解

题目地址:BZOJ:Problem 3545. — [ONTAK2010]Peaks

题目描述

在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。

题意简述

有一个图,点和边都有权值。回答若干询问,每个询问表示只保留图中边权不大于x的边,v所在的连通块中,点权k大

输入输出格式

输入格式:
第一行三个数N,M,Q。
第二行N个数,第i个数为h_i
接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径。
接下来Q行,每行三个数v x k,表示一组询问。

输出格式:
对于每组询问,输出一个整数表示答案。

输入输出样例

输入样例#1:

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2

输出样例#1:

6
1
-1
8

说明

【数据范围】
N<=10^5, M,Q<=5*10^5,h_i,c,x<=10^9。

题解

首先,连通性可以使用并查集维护。我们可以先对点权离散化,考虑每个连通块维护一个权值线段树,使用动态开点写法,在并查集的代表元处记下根下标。
我们考虑离线解决这个问题,对询问和边都排序,从小到大加边,并启发式合并连通块的线段树。由于线段树规模倍增,启发式合并的复杂度是期望O(\log n)的。因此总复杂度是O(n \log n)的,可以接受。
谁来告诉我为什么我的线段树常数看上去很优秀?这好像已经不是第一次了

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 500005;

int n, m, q;

int fa[MAXN], siz[MAXN];

inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct Node {
    int lch, rch, val;
} tr[MAXN << 4];
int rt[MAXN], tot;

inline void insert(int &o, int l, int r, int x) {
    if(!o) o = ++tot;
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline int query(int o, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1, rsiz = tr[tr[o].rch].val;
    if(k <= rsiz) return query(tr[o].rch, mid + 1, r, k);
    else return query(tr[o].lch, l, mid, k - rsiz);
}

inline int merge(int o1, int o2) {
    if(!o1) return o2;
    if(!o2) return o1;
    if(!tr[o1].lch && !tr[o1].rch) {
        tr[o1].val += tr[o2].val;
        return o1;
    }
    tr[o1].lch = merge(tr[o1].lch, tr[o2].lch);
    tr[o1].rch = merge(tr[o1].rch, tr[o2].rch);
    tr[o1].val = tr[tr[o1].lch].val + tr[tr[o1].rch].val;
    return o1;
}

int w[MAXN];

std::vector<int> tmp;

struct Edge {
    int u, v, w;
} edges[MAXN];

inline bool cmpE(Edge a, Edge b) {
    return a.w < b.w;
}

struct Query {
    int v, x, k, id;
} qur[MAXN];

inline bool cmpQ(Query a, Query b) {
    return a.x < b.x;
}

int ans[MAXN];

int main() {
    n = readint(); m = readint(); q = readint();
    for(int i = 1; i <= n; i++) {
        fa[i] = i; siz[i] = 1;
    }
    tmp.push_back(-1);
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
        tmp.push_back(w[i]);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i = 1; i <= n; i++) {
        w[i] = std::lower_bound(tmp.begin(), tmp.end(), w[i]) - tmp.begin();
        insert(rt[i], 1, n, w[i]);
    }
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    std::sort(edges + 1, edges + m + 1, cmpE);
    for(int i = 1; i <= q; i++) {
        qur[i].v = readint(); qur[i].x = readint(); qur[i].k = readint(); qur[i].id = i;
    }
    std::sort(qur + 1, qur + q + 1, cmpQ);
    int ne = 1;
    for(int i = 1; i <= q; i++) {
        for(; ne <= m && edges[ne].w <= qur[i].x; ne++) {
            int u = edges[ne].u, v = edges[ne].v, fu = find(u), fv = find(v);
            if(fu == fv) continue;
            if(siz[fu] > siz[fv]) {
                std::swap(u, v); std::swap(fu, fv);
            }
            rt[fv] = merge(rt[fu], rt[fv]);
            fa[fu] = fv; siz[fv] += siz[fu];
        }
        int fv = find(qur[i].v);
        if(tr[rt[fv]].val < qur[i].k) ans[qur[i].id] = -1;
        else ans[qur[i].id] = tmp[query(rt[fv], 1, n, qur[i].k)];
    }
    for(int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}
[SCOI2011]棘手的操作 题解

[SCOI2011]棘手的操作 题解

题目地址:洛谷:【P3273】[SCOI2011]棘手的操作 – 洛谷、BZOJ:Problem 2333. — [SCOI2011]棘手的操作

题目描述

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:

  • U x y: 加一条边,连接第x个节点和第y个节点
  • A1 x v: 将第x个节点的权值增加v
  • A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
  • A3 v: 将所有节点的权值都增加v
  • F1 x: 输出第x个节点当前的权值
  • F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值
  • F3: 输出所有节点中,权值最大的节点的权值

输入输出格式

输入格式:
输入的第一行是一个整数N,代表节点个数。接下来一行输入N个整数,a[1], a[2], …, a[N],代表N个节点的初始权值。再下一行输入一个整数Q,代表接下来的操作数。最后输入Q行,每行的格式如题目描述所示。
输出格式:
对于操作F1, F2, F3,输出对应的结果,每个结果占一行。

输入输出样例

输入样例#1:

3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

输出样例#1:

-10
10
10

说明

对于30%的数据,保证 N<=100,Q<=10000
对于80%的数据,保证 N<=100000,Q<=100000
对于100%的数据,保证 N<=300000,Q<=300000
对于所有的数据,保证输入合法,并且 -1000<=v, a[1], a[2], …, a[N]<=1000

题解

解法1:线段树 + 并查集

考虑离线解决这个题,我们可以把操作中同一连通块的元素连续地排列在一个序列中,这样连通块操作就变成了区间操作,这个可以用线段树维护区间最大值。
至于如何连续排列,可以考虑用链表来存储当前连通块序列,然后合并连通块的时候合并链表,这样就自然成为连续的一段了。最后再遍历链表给节点加编号就好。

解法2:可并堆

使用可并堆做这个题目就很裸了,也不需要离线。这里我写的是左偏树。
分开管理两类可并堆,一类是联通块的大根堆,一类是所有联通块堆顶元素的大根堆(换句话说,这是一个维护全局的堆)。
U操作:将两个节点所在的堆合并,删去全局堆中消失的那个堆的对顶。
A1操作:将x所在堆中x元素删去,更新x元素的值,再插回去。
A2操作:将x所在堆全局增量加上v。堆全局增量可以在堆顶维护,需要统计这个结点的真实值的时候从该点一路上跳,跳到一个父亲就将该父亲的增量加入真实值。(因为堆并过程中增量仍然在被合并的堆顶)
A3操作:维护总全局增量加v。
F1操作:查询x的真实值。
F2操作:查询x所在堆堆顶的真实值。
F3操作:查询全局堆堆顶的真实值。
这个解法的代码我借鉴了远航之曲的实现思路。

代码

解法1

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

struct io {
    char buf[1 << 26], *op;
    io() {
        fread(op = buf, 1, 1 << 26, stdin);
    }
    inline int readint() {
        register int res = 0, neg = 1;
        while(*op < '0' || *op > '9') if(*op++ == '-') neg = -1;
        while(*op >= '0' && *op <= '9') res = res * 10 + *op++ - '0';
        return res * neg;
    }
    inline char readchar() {
        return *op++;
    }
} ip;

#define readint ip.readint
#define readchar ip.readchar

inline bool isop(char c) {
    return c == 'A' || c == 'U' || c == 'F'; 
}

inline char readop() {
    char c;
    while(!isop(c = readchar()));
    return c;
}

int n, a[300005], q, opop1[300005], opx[300005], opy[300005], idx[300005], inv[300005], tot = 1;
char opop[300005];

// Linked List

int pre[300005], nxt[300005], head[300005], tail[300005];

// Union-Find

int fa[300005]; 

inline int find(int x) {
    int r = x;
    while(fa[r] != r) r = fa[r];
    while(fa[x] != x) {
        int ofa = fa[x];
        fa[x] = r;
        x = ofa;
    }
    return r;
}

// Seg Tree

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

int tree[1200005], lazy[1200005]; 

inline void build(int o, int l, int r) {
    if(l == r) {
        tree[o] = a[inv[l]];
        return;
    }
    build(lch, l, mid);
    build(rch, mid + 1, r);
    tree[o] = std::max(tree[lch], tree[rch]);
}

inline void pushdown(int o) {
    if(lazy[o] != 0) {
        lazy[lch] += lazy[o];
        lazy[rch] += lazy[o];
        tree[lch] += lazy[o];
        tree[rch] += lazy[o];
        lazy[o] = 0;
    }
}

inline void add(int o, int l, int r, int ll, int rr, int v) {
    if(l == ll && r == rr) {
        tree[o] += v;
        lazy[o] += v;
        return;
    }
    pushdown(o);
    if(rr <= mid) {
        add(lch, l, mid, ll, rr, v);
    } else if(ll > mid) {
        add(rch, mid + 1, r, ll, rr, v);
    } else {
        add(lch, l, mid, ll, mid, v);
        add(rch, mid + 1, r, mid + 1, rr, v);
    }
    tree[o] = std::max(tree[lch], tree[rch]);
}

inline int query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) {
        return tree[o];
    }
    pushdown(o);
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        return std::max(query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
    }
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        fa[i] = head[i] = tail[i] = i;
    }
    q = readint();
    for(int i = 1; i <= q; i++) {
        opop[i] = readop();
        if(opop[i] == 'U') {
            opx[i] = readint();
            opy[i] = readint();
            int f1 = find(opx[i]), f2 = find(opy[i]);
            if(f1 != f2) {
                fa[f2] = f1;
                pre[head[f2]] = tail[f1];
                nxt[tail[f1]] = head[f2];
                tail[f1] = tail[f2];
            }
        } else if(opop[i] == 'A') {
            opop1[i] = readint();
            if(opop1[i] < 3) {
                opx[i] = readint();
            }
            opy[i] = readint();
        } else if(opop[i] == 'F') {
            opop1[i] = readint();
            if(opop1[i] < 3) {
                opx[i] = readint();
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!pre[i]) {
            for(int j = i; j; j = nxt[j]) {
                idx[j] = tot++; 
                inv[idx[j]] = j;
            }
        }
    }
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        fa[i] = head[i] = tail[i] = i;
    }
    for(int i = 1; i <= q; i++) {
        if(opop[i] == 'U') {
            int f1 = find(idx[opx[i]]), f2 = find(idx[opy[i]]);
            if(f1 != f2) {
                fa[f2] = f1;
                if(head[f1] < head[f2]) {
                    tail[f1] = tail[f2];
                } else {
                    head[f1] = head[f2];
                }
            }
        } else if(opop[i] == 'A') {
            if(opop1[i] == 1) {
                add(1, 1, n, idx[opx[i]], idx[opx[i]], opy[i]);
            } else if(opop1[i] == 2) {
                int f = find(idx[opx[i]]);
                add(1, 1, n, head[f], tail[f], opy[i]);
            } else {
                add(1, 1, n, 1, n, opy[i]);
            }
        } else if(opop[i] == 'F') {
            if(opop1[i] == 1) {
                printf("%d\n", query(1, 1, n, idx[opx[i]], idx[opx[i]]));
            } else if(opop1[i] == 2) {
                int f = find(idx[opx[i]]);
                printf("%d\n", query(1, 1, n, head[f], tail[f]));
            } else { 
                printf("%d\n", query(1, 1, n, 1, n));
            }
        }
    }
    return 0;
}

解法2

// Code by KSkun, 2018/2
#include <cstdio>
#include <queue>

struct io {
    char buf[1 << 26], *op;
    io() {
        fread(op = buf, 1, 1 << 26, stdin);
    }
    inline int readint() {
        register int res = 0, neg = 1;
        while(*op < '0' || *op > '9') if(*op++ == '-') neg = -1;
        while(*op >= '0' && *op <= '9') res = res * 10 + *op++ - '0';
        return res * neg;
    }
    inline char readchar() {
        return *op++;
    }
} ip;

#define readint ip.readint
#define readchar ip.readchar

inline bool isop(char c) {
    return c == 'U' || c == 'A' || c == 'F';
}

inline void readop(char* str) {
    char c;
    while(!isop(c = readchar()));
    str[0] = c;
    if(c == 'A' || c == 'F') str[1] = readchar();
}

int n, m, x, y, z, add = 0;
char op[5];

struct LeftistTree {
    int dis[300005], fa[300005], ch[300005][2], val[300005], add[300005], root;
    inline int toadd(int x) {
        int res = 0;
        while(x = fa[x]) res += add[x];
        return res; 
    }
    inline void clear(int x) {
        fa[x] = ch[x][0] = ch[x][1] = 0; 
    } 
    inline void pushdown(int x) {
        if(ch[x][0]) {
            val[ch[x][0]] += add[x];
            add[ch[x][0]] += add[x];
        }
        if(ch[x][1]) {
            val[ch[x][1]] += add[x];
            add[ch[x][1]] += add[x];
        }
        add[x] = 0;
    }
    inline int merge(int x, int y) {
        if(!x) return y;
        if(!y) return x;
        if(val[x] < val[y]) std::swap(x, y);
        pushdown(x);
        ch[x][1] = merge(ch[x][1], y);
        fa[ch[x][1]] = x;
        if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
        dis[x] = dis[ch[x][1]] + 1;
        return x;
    }
    inline int froot(int x) {
        while(fa[x]) x = fa[x];
        return x;
    }
    inline void delet(int x) {
        pushdown(x);
        int f = merge(ch[x][0], ch[x][1]);
        fa[f] = fa[x];
        if(fa[x]) ch[fa[x]][ch[fa[x]][0] == x ? 0 : 1] = f;
        int t = fa[x];
        if(!t) {
            root = f;
            return;
        }
        while(t) {
            if(dis[ch[t][0]] < dis[ch[t][1]]) std::swap(ch[t][0], ch[t][1]);
            if(dis[t] == dis[ch[t][1]] + 1) return;
            dis[t] = dis[ch[t][1]] + 1;
            if(!fa[t]) root = t;
            t = fa[t];
        }
    }
    inline void addtree(int x, int v) {
        int rt = froot(x);
        val[rt] += v;
        add[rt] += v;
    }
    inline int addpoint(int x, int v) {
        int rt = froot(x);
        if(rt == x) {
            if(!ch[x][0] && !ch[x][1]) {
                val[x] += v;
                return x; 
            } else {
                rt = ch[x][0] ? ch[x][0] : ch[x][1];
            }
        }
        delet(x);
        val[x] += v + toadd(x);
        clear(x);
        return merge(froot(rt), x);
    }
    inline void build() {
        std::queue<int> que;
        for(int i = 1; i <= n; i++) {
            que.push(i);
        }
        while(que.size() > 1) {
            int x = que.front();
            que.pop();
            int y = que.front();
            que.pop();
            que.push(merge(x, y));
        }
        root = que.front();
    }
};

LeftistTree lt1, lt2;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        lt1.val[i] = lt2.val[i] = readint();
    }
    lt1.dis[0] = lt2.dis[0] = -1;
    lt2.build();
    m = readint();
    for(int i = 1; i <= m; i++) {
        readop(op);
        if(op[0] == 'U') {
            x = readint();
            y = readint();
            int fx = lt1.froot(x), fy = lt1.froot(y), rt;
            if(fx != fy) {
                rt = lt1.merge(fx, fy);
                if(rt == fx) lt2.delet(fy);
                if(rt == fy) lt2.delet(fx);
            }
        }
        if(op[0] == 'A') {
            if(op[1] == '1') {
                x = readint();
                y = readint();
                int fx = lt1.froot(x), rt;
                lt2.delet(fx);
                rt = lt1.addpoint(x, y);
                lt2.val[rt] = lt1.val[rt];
                lt2.clear(rt);
                lt2.root = lt2.merge(lt2.root, rt);
            }
            if(op[1] == '2') {
                x = readint();
                y = readint();
                int fx = lt1.froot(x);
                lt2.delet(fx);
                lt1.val[fx] += y;
                lt1.add[fx] += y;
                lt2.val[fx] = lt1.val[fx];
                lt2.clear(fx);
                lt2.root = lt2.merge(lt2.root, fx);
            }
            if(op[1] == '3') {
                x = readint();
                add += x;
            }
        }
        if(op[0] == 'F') {
            if(op[1] == '1') {
                x = readint();
                printf("%d\n", lt1.val[x] + lt1.toadd(x) + add);
            }
            if(op[1] == '2') {
                x = readint();
                printf("%d\n", lt1.val[lt1.froot(x)] + add);
            }
            if(op[1] == '3') {
                printf("%d\n", lt2.val[lt2.root] + add);
            }
        }
    }
    return 0;
}

调试留下来的数据生成器

因为经常WA,手写了一个数据生成器,偶尔会崩掉不要介意qwq,可自由调整n和q的取值。

// Code by KSkun, 2018/2 
#include <cstdio>
#include <cstdlib>
#include <ctime> 

int n, q;
char str[10][5] = {"U", "A1", "A2", "A3", "F1", "F2", "F3"}; 

int main() {
    freopen("p3273.in", "w", stdout);
    srand(time(NULL));
    n = rand() % 50;
    q = rand() % 50;
    printf("%d\n", n);
    for(int i = 1; i <= n; i++) {
        printf("%d ", rand() - RAND_MAX / 2);
    }
    printf("\n");
    printf("%d\n", q);
    for(int i = 1; i <= q; i++) {
        int op = rand() % 7;
        printf("%s ", str[op]);
        if(op == 0) {
            printf("%d %d ", rand() % n + 1, rand() % n + 1);
        }
        if(op == 1 || op == 2 || op == 4 || op == 5) {
            printf("%d ", rand() % n + 1);
        }
        if(op == 1 || op == 2 || op == 3) {
            printf("%d ", rand() - RAND_MAX / 2);
        }
        printf("\n");
    }
    return 0;
}