#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int maxN = 200'000;
const int maxM = 200'000;
const int lgM = 18;
const int INF = 1'000'000'000;
int N;
vector<int> A(1+maxN+1);
vector<int> star_list[1+maxN];
int M;
vector<int> X(1+maxM);
vector<int> Y(1+maxM);
vector<long long> C(1+maxM);
long long total_cost = 0;
struct segtree
{
int l;
int r;
int mx;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
{
mx = A[l];
}
else
{
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
mx = max(left->mx, right->mx);
}
}
int rangemax(int L, int R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return mx;
else return max(left->rangemax(L, R), right->rangemax(L, R));
}
};
vector<int> left_high(1+maxM);
vector<int> right_high(1+maxM);
struct rectangle
{
int L; //[L, R] x [H, N]
int R;
int H;
int I;
};
bool operator < (rectangle A, rectangle B)
{
if(A.L != B.L)
return A.L < B.L;
else if(A.R != B.R)
return A.R > B.R;
else if(A.H != B.H)
return A.H > B.H;
else
return A.I < B.I;
}
vector<rectangle> rect(1+maxM);
vector<int> star_bottom(1+maxM);
vector<int> openings[1+maxN];
vector<int> closings[1+maxN];
int anc[1+maxM][lgM];
vector<int> desc[1+maxM][lgM];
vector<int> depth(1+maxM, 0);
long long anc_dp_sum[1+maxM][lgM]; //exclusive
vector<long long> dp(1+maxM, 0LL);
vector<long long> child_dp_sum(1+maxM, 0LL);
bool dbg_flag = 0;
void dfs1(int u)
{
for(int v: desc[u][0])
{
depth[v] = depth[u] + 1;
dfs1(v);
}
}
int getAnc(int u, int d)
{
for(int e = 0; e < lgM; e++)
{
if(d & (1 << e))
u = anc[u][e];
}
return u;
}
long long chain_sum(int u, int d)
{
int u1 = u;
long long ans = 0;
for(int e = 0; e < lgM; e++)
{
if(d & (1 << e))
{
// if(dbg_flag)
// {
// cerr << "jumping from " << u << " to " << anc[u][e] << ", adding " << anc_dp_sum[u][e] << " to answer\n";
// }
ans += anc_dp_sum[u][e];
u = anc[u][e];
}
}
// cerr << "chain sum " << u1 << ' ' << d << " " << ans << '\n';
return ans;
}
void binary_lift(int u, int e)
{
// cerr << "binary lift " << u << ' ' << e << '\n';
anc_dp_sum[u][e] = anc_dp_sum[u][e-1] + anc_dp_sum[ anc[u][e-1] ][e-1];
// cerr << "anc dp sum " << u << ' ' << e << " = " << anc_dp_sum[u][e] << '\n';
for(int v: desc[u][e])
binary_lift(v, e+1);
}
void dfs2(int u)
{
// cerr << "\n\n\n\n";
// cerr << "entered dfs2 " << u << "\n";
for(int v: desc[u][0])
{
// cerr << u << " -> " << v << '\n';
dfs2(v);
child_dp_sum[u] += dp[v];
}
for(int v: desc[u][0])
{
anc_dp_sum[v][0] = child_dp_sum[u] - dp[v];
// cerr << "anc dp sum " << v << ' ' << 0 << " = " << anc_dp_sum[v][0] << '\n';
for(int v2: desc[v][0])
binary_lift(v2, 1);
}
if(star_bottom[u] == u)
{
dp[u] = child_dp_sum[u] + C[u];
// cerr << "!!! ";
// cerr << "dp[" << u << "] = " << dp[u] << '\n';
}
else
{
// cerr << "case 2\n";
int sb = star_bottom[u];
long long new_dp = child_dp_sum[sb] + chain_sum(sb, depth[sb] - depth[u]) + C[u];
// new_dp += child_dp_sum[u] - dp[ getAnc(sb, depth[sb] - depth[u] - 1) ];
// cerr << sb << ' ' << child_dp_sum[sb] << ' ' << chain_sum(sb, depth[sb] - depth[u]) << ' ' << C[u] << '\n';
// cerr << child_dp_sum[u] << '\n';
// cerr << new_dp << '\n';
dp[u] = max(child_dp_sum[u], new_dp);
// cerr << "!!! ";
// cerr << "dp[" << u << "] = " << dp[u] << '\n';
}
// cerr << "exited dfs2 " << u << "\n";
// cerr << "\n\n\n\n";
}
int main()
{
assert(1 == 0);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
A[0] = N+1;
for(int i = 1; i <= N; i++) cin >> A[i];
A[N+1] = N+1;
cin >> M;
for(int j = 1; j <= M; j++)
{
cin >> X[j] >> Y[j] >> C[j];
star_list[ X[j] ].push_back(j);
total_cost += C[j];
}
// cerr << "total cost = " << total_cost << '\n';
segtree S(0, N+1);
// cerr << "check\n";
// cerr << "\n\n\n";
for(int j = 1; j <= M; j++)
{
// cerr << "j = " << j << '\n';
int lo, hi, mid;
//closest building on left
lo = 0;
hi = X[j]-1;
while(lo != hi)
{
mid = (lo+hi)/2+1;
if(S.rangemax(mid, hi) >= Y[j])
lo = mid;
else
hi = mid-1;
}
left_high[j] = lo;
// cerr << "part 1 done\n";
//closest building on right
lo = X[j]+1;
hi = N+1;
while(lo != hi)
{
// cerr << lo << ' ' << hi << '\n';
mid = (lo+hi)/2;
if(S.rangemax(lo, mid) >= Y[j])
hi = mid;
else
lo = mid+1;
}
right_high[j] = lo;
// cerr << j << ' ' << left_high[j] << ' ' << right_high[j] << '\n';
rect[j] = rectangle{left_high[j] + 1, right_high[j] - 1, Y[j], j};
openings[rect[j].L].push_back(j);
closings[rect[j].R].push_back(j);
}
// cerr << "\n\n\n\n";
for(int i = 1; i <= N; i++)
{
// cerr << "i = " << i << '\n';
sort(openings[i].begin(), openings[i].end(), [] (int o1, int o2)
{
return rect[o1] < rect[o2];
});
// for(int o: openings[i]) cerr << o << ' ';
// cerr << '\n';
sort(closings[i].begin(), closings[i].end(), [] (int c1, int c2)
{
return rect[c2] < rect[c1]; // REVERSED!!!!!!
});
// for(int c: closings[i]) cerr << c << ' ';
// cerr << '\n';
}
vector<int> ST(1, 0);
anc[0][0] = 0;
for(int i = 1; i <= N; i++)
{
// cerr << "i = " << i << '\n';
for(int o: openings[i])
{
// cerr << " o = " << o << '\n';
// cerr << "parent " << o << " = " << ST.back() << '\n';
anc[o][0] = ST.back();
desc[ anc[o][0] ][0].push_back(o);
ST.push_back(o);
}
for(int j: star_list[i])
{
star_bottom[j] = ST.back();
// cerr << "star bottom of " << j << " = " << star_bottom[j] << '\n';
}
for(int c: closings[i])
{
ST.pop_back();
// cerr << " c = " << c << '\n';
}
}
for(int e = 1; e < lgM; e++)
for(int j = 0; j <= M; j++)
{
anc[j][e] = anc[ anc[j][e-1] ][e-1];
desc[ anc[j][e] ][e].push_back(j);
}
for(int j = 1; j <= M; j++)
if(anc[j][0] == 0)
{
depth[j] = 1;
dfs1(j);
}
long long max_kept = 0;
for(int j = 1; j <= M; j++)
{
// cerr << "anc " << j << " = " << anc[j][0] << '\n';
if(anc[j][0] == 0)
{
// cerr << "calling " << j << '\n';
dfs2(j);
max_kept += dp[j];
}
}
cout << total_cost - max_kept << '\n';
}
Compilation message
constellation3.cpp: In function 'long long int chain_sum(int, int)':
constellation3.cpp:131:9: warning: unused variable 'u1' [-Wunused-variable]
131 | int u1 = u;
| ^~
constellation3.cpp: In function 'int main()':
constellation3.cpp:217:5: error: 'assert' was not declared in this scope
217 | assert(1 == 0);
| ^~~~~~
constellation3.cpp:5:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
4 | #include <set>
+++ |+#include <cassert>
5 | using namespace std;
constellation3.cpp:324:17: warning: unused variable 'c' [-Wunused-variable]
324 | for(int c: closings[i])
| ^
