【题解】HackerRank-Cyclical Queries

题目

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$,那么 1k-1 的 $f’[i]=f[i] + dis(k,1)$,kn 的 $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); }
}
}
}