【题解】HackerRank-Cyclical Queries

Posted on In Disqus:

题目

https://www.hackerrank.com/contests/w38/challenges/cyclical-queries

题意

给一个带边权的有向环。

每次对最初的环上的一个点 \(x\) 进行询问，设离 \(x\) 最远的点是 \(y\)（如果有多个，选取最后添加的那个），要求支持以下操作：

  1. 从 \(y\) 连一条权为 \(w\) 的边到一个新结点。
  2. 从 \(x\) 连一条权为 \(w\) 的边到一个新结点。
  3. 删除 \(y\)。
  4. 求 \(x\) 于 \(y\) 之间的距离。

题解

  • 显然有出度的点不会被删。
  • 如果没有删除操作，那么图的形状就是一个环，环上的一些点伸出一棵树，但是我们完全不关心树的形态，只需要记录树上所有点的深度。
  • 考虑删除操作，这个环可能会断裂。
  • 需要实现的函数就是查最远点，插入点和删除点。
  • 线段树维护查询点 1 的区间最大值（不考虑已经被删除的结点），也就是 \(f[i]=max_d[i]+dis(1,i)\)，那么如果查询的是 \(k\)，那么 1~k-1 的 \(f'[i]=f[i] + dis(k,1)\)，k~n 的 \(f'[i]=f[i]-dis(1, k)\) 。
  • 环断的位置用 set 维护，查询时只考虑没断的部分。
  • 实现比较麻烦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 1E5 + 100;
struct P {
    LL dep, idx;
};
bool operator < (const P& x, const P& y) {
    return x.dep < y.dep || (x.dep == y.dep && x.idx < y.idx);
}
priority_queue<P> S[N];
set<int> deleted;
int n;
LL a[N], Sum, ps[N];

inline pair<LL, LL> f(int x) {
    return {S[x].top().dep + ps[x], S[x].top().idx};
};


namespace seg {
#define mid ((l + r) >> 1)
#define lson o * 2, l, mid
#define rson o * 2 + 1, mid + 1, r
    int mx[N << 2];
    inline int Max(int a, int b) {
        if (a == -1) return b; if (b == -1) return a;
        return f(a) < f(b) ? b : a;
    }
    inline void up(int o) { mx[o] = Max(mx[o * 2], mx[o * 2 + 1]); }
    void build(int o, int l, int r) {
        if (l == r) mx[o] = l;
        else { build(lson); build(rson); up(o); }
    }
    void update(int k, int o, int l, int r) {
        if (k > r || k < l || l == r) return;
        update(k, lson); update(k, rson); up(o);
    }
    int query(int ql, int qr, int o, int l, int r) {
        if (qr < l || r < ql) return -1;
        if (ql <= l && r <= qr) return mx[o];
        return Max(query(ql, qr, lson), query(ql, qr, rson));
    }

}
LL ans, clk;

void add(int x, int w, int sp) {
    S[x].push({sp * S[x].top().dep + w, clk});
    seg::update(x, 1, 1, n);
}
void del(int x) {
    S[x].pop();
    if (S[x].empty()) {
        deleted.insert(x);
        deleted.insert(x + n);
    } else seg::update(x, 1, 1, n);
}
int query(int x) {
    auto it = deleted.upper_bound(x);
    int ed = it == deleted.end() ? x + n - 1 : *it - 1;
    int t1 = seg::query(x, min(n, ed), 1, 1, n);
    int t2 = ed <= n ? -1 :
             seg::query(1, ed - n, 1, 1, n);
    auto v1 = f(t1), v2 = f(t2);

    v1.first -= ps[x];
    ans = v1.first;
    if (t2 == -1) return t1;

    v2.first += Sum - ps[x];
    ans = max(v1.first, v2.first);

    return v1 > v2 ? t1 : t2;
}


int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    cin >> n;
    FOR (i, 1, n + 1) scanf("%lld", &a[i]);
    Sum = accumulate(a + 1, a + n + 1, 0LL);
    FOR (i, 1, n + 1) ps[i] = ps[i - 1] + a[i - 1];
    FOR (i, 1, n + 1) S[i].push({0, 0});
    seg::build(1, 1, n);
    int Qn; cin >> Qn;
    for (clk = 1; clk <= Qn; ++clk) {
        int tp, x; scanf("%d%d", &tp, &x);
        if (tp <= 2) {
            LL w; scanf("%lld", &w);
            if (tp == 1) add(query(x), w, 1);
            else add(x, w, 0);
        } else {
            if (tp == 3) del(query(x));
            else { query(x); printf("%lld\n", ans); }
        }
    }
}