LOJ3277

Solution

先把题目转化为保留尽量多星星,使得权值和最大

考虑按AA数组的最大值分治,得到一个二叉树的结构 (似乎叫笛卡尔树?不太清楚)

设当前在节点xx,对应的区间为[l,r][l, r],区间最大值为wxw_x

注意到此时在[l,r][l, r]中,最多只能出现一个纵坐标>wx> w_x的星星

于是考虑设f(x)f(x)表示在xx节点,只用横坐标在[l,r][l, r]内,纵坐标wfa(x)\le w_{fa(x)}的星星的最大权值和

若不存在>wx> w_x的星星,则答案为f(ls(x))+f(rs(x))f(ls(x)) + f(rs(x))

若存在,则枚举所有x[l,r],y[wx+1,wfa(x)]x\in [l, r], y \in [w_x + 1, w_{fa(x)}]的星星,找到其横坐标对应在二叉树上的节点(设为pp)

那么答案就是f(ls(p))+f(rs(p))+f(bro(p))+f(bro(fa(p)))+f(bro(fa(fa(p))))+...f(ls(p)) + f(rs(p)) + f(bro(p)) + f(bro(fa(p))) + f(bro(fa(fa(p)))) + ...,因为所有pp的祖先都不能再出现另一个>wx> w_x的数了

这样暴力模拟是O(n2)O(n^2)的,用线段树合并维护即可做到O(nlogn)O(n \log n) (每次把左子树的答案加上右子树的ff值,右子树的答案加上左子树的ff值,再合并)

Code

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;

int N, M;
int A[MAXN + 5];

vector <pii> vec[MAXN + 5];

namespace RMQ
{
const int MAX_LOG = log2(MAXN);

int Log[MAXN + 5];
pii F[MAX_LOG + 1][MAXN + 5];

inline void init ()
{
Log[1] = 0; for (int i = 2; i <= N; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= N; ++i) F[0][i] = mp (A[i], i);
for (int i = 1; i <= Log[N]; ++i)
for (int j = 1; j + (1 << i) - 1 <= N; ++j)
F[i][j] = max (F[i - 1][j], F[i - 1][j + (1 << (i - 1))]);
}

inline int query (int l, int r)
{
int k = Log[r - l + 1];
return max (F[k][l], F[k][r - (1 << k) + 1]).y;
}
}

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls node[o].ch[0]
#define rs node[o].ch[1]
#define lson ls, l, mid
#define rson rs, mid + 1, r

const int MAXN = :: MAXN * 60;

int O[:: MAXN + 5];

struct info
{
int ch[2];
LL max, tag;
} node[MAXN + 5];

int node_cnt;

inline void push_up (int o) { node[o].max = max (node[ls].max, node[rs].max); }


inline void push_down (int o)
{
if (!node[o].tag) return ;
if (ls) node[ls].max += node[o].tag, node[ls].tag += node[o].tag;
if (rs) node[rs].max += node[o].tag, node[rs].tag += node[o].tag;
node[o].tag = 0;
}

inline void insert (int &o, int l, int r, int x, LL val)
{
if (!o) o = ++node_cnt;
if (l == r) return void (Chkmax (node[o].max, val));
push_down (o);
if (x <= mid) insert (lson, x, val);
else insert (rson, x, val);
push_up (o);
}

inline LL query (int o, int l, int r, int x, int y)
{
if (x > y || !o) return 0;
if (x <= l && r <= y) return node[o].max;

push_down (o);

LL ans = 0;
if (x <= mid) Chkmax (ans, query (lson, x, y));
if (y > mid) Chkmax (ans, query (rson, x, y));
return ans;
}

inline int merge (int x, int y, int l, int r, LL val1, LL val2)
{
if (!x && !y) return 0;
if (!x) { node[y].max += val1, node[y].tag += val1; return y; }
if (!y) { node[x].max += val2, node[x].tag += val2; return x; }
if (l == r) { node[x].max = max (node[x].max + val2, node[y].max + val1); return x; }
push_down (x), push_down (y);
node[x].ch[0] = merge (node[x].ch[0], node[y].ch[0], l, mid, val1, val2);
node[x].ch[1] = merge (node[x].ch[1], node[y].ch[1], mid + 1, r, val1, val2);
node[x].max = max (node[x].max + val2, node[y].max + val1);
return x;
}

#undef mid
}

using SEG :: O;

namespace TREE
{
const int MAXN = :: MAXN * 4;

struct info
{
int ch[2], p, fa;
} node[MAXN + 5];

int node_cnt, id[MAXN + 5];

inline void build (int &o, int l, int r)
{
if (l > r) return ;
o = ++node_cnt;

int p = RMQ :: query (l, r);
id[node[o].p = p] = o;

build (node[o].ch[0], l, p - 1), build (node[o].ch[1], p + 1, r);

if (node[o].ch[0]) node[node[o].ch[0]].fa = o;
if (node[o].ch[1]) node[node[o].ch[1]].fa = o;
}

LL F[MAXN + 5];

inline LL solve (int o, int l, int r, int fw)
{
if (l > r) return 0;

int p = node[o].p;

F[o] = solve (node[o].ch[0], l, p - 1, A[p]) + solve (node[o].ch[1], p + 1, r, A[p]);

O[o] = SEG :: merge (O[node[o].ch[0]], O[node[o].ch[1]], 1, N, F[node[o].ch[0]], F[node[o].ch[1]]);

for (pii t : vec[p]) SEG :: insert (O[o], 1, N, t.x, (LL) t.y + F[node[o].ch[0]] + F[node[o].ch[1]]);

Chkmax (F[o], SEG :: query (O[o], 1, N, A[p] + 1, fw));

return F[o];
}
}

LL sum;

inline void Solve ()
{
RMQ :: init ();

int o = 0;
TREE :: build (o, 1, N);

cout << sum - TREE :: solve (o, 1, N, N) << endl;
}

inline void Input ()
{
N = read<int>();
for (int i = 1; i <= N; ++i) A[i] = read<int>();
M = read<int>();
for (int i = 1; i <= M; ++i)
{
int x = read<int>(), y = read<int>(), c = read<int>();
sum += c;
vec[x].pb (mp (y, c));
}
}

int main ()
{
#ifdef hk_cnyali
freopen("constellation3.in", "r", stdin);
freopen("constellation3.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}