#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;
const int maxN = 200'000;
const int maxM = 200'000;
const int lgM = 18;
const int lgN = 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));
// }
// };
// int lowest_pow[1+maxN+1];
//
// struct sparse_table
// {
// int** mx;
//
// sparse_table(int N)
// {
// // cerr << "creating sparse table\n";
// mx = new int*[1+N+1];
// for(int i = 0; i <= N+1; i++)
// mx[i] = new int[lgN];
//
//
// for(int i = 0; i <= N+1; i++)
// mx[i][0] = A[i];
//
// for(int e = 1; e < lgN; e++)
// {
// for(int i = 0; i <= N+1; i++)
// {
// if(i + (1 << e) - 1 > N+1)
// continue;
//
// mx[i][e] = max(mx[i][e-1], mx[i + (1 << (e-1))][e-1]);
// }
// }
// }
//
// int rangemax(int l, int r)
// {
// // cerr << "range max " << l << ' ' << r << '\n';
// int p = lowest_pow[r-l+1];
// // cerr << "p = " << p << '\n';
// return max(mx[l][p], mx[r - (1 << p) + 1][p]);
// }
// };
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];
// long long anc_dp_sum[1+maxM][lgM]; //exclusive
int** anc;
vector<int>** desc;
long long** anc_dp_sum;
vector<int> depth(1+maxM, 0);
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()
{
anc = new int*[1+maxM];
desc = new vector<int>*[1+maxM];
anc_dp_sum = new long long*[1+maxM];
for(int i = 0; i <= 1+maxM; i++)
{
anc[i] = new int[lgM];
desc[i] = new vector<int>[lgM];
anc_dp_sum[i] = new long long[lgM];
}
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];
}
lowest_pow[1] = 0;
for(int i = 2; i <= N+1; i++)
lowest_pow[i] = 1 + lowest_pow[i/2];
// cerr << "total cost = " << total_cost << '\n';
sparse_table S(N);
// segtree S1(0, N+1);
// cerr << "check\n";
// cerr << "\n\n\n";
assert(N + M <= 10000);
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:174:9: warning: unused variable 'u1' [-Wunused-variable]
174 | int u1 = u;
| ^~
constellation3.cpp: In function 'int main()':
constellation3.cpp:288:5: error: 'lowest_pow' was not declared in this scope
288 | lowest_pow[1] = 0;
| ^~~~~~~~~~
constellation3.cpp:298:5: error: 'sparse_table' was not declared in this scope
298 | sparse_table S(N);
| ^~~~~~~~~~~~
constellation3.cpp:317:16: error: 'S' was not declared in this scope
317 | if(S.rangemax(mid, hi) >= Y[j])
| ^
constellation3.cpp:334:16: error: 'S' was not declared in this scope
334 | if(S.rangemax(lo, mid) >= Y[j])
| ^
constellation3.cpp:391:17: warning: unused variable 'c' [-Wunused-variable]
391 | for(int c: closings[i])
| ^
