#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 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;
vector<int> lowest_pow(100+maxN);
struct sparse_table
{
int** mx;
sparse_table()
{
// 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]);
}
}
// cerr << "sparse table built\n";
}
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];
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))
{
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)
{
anc_dp_sum[u][e] = anc_dp_sum[u][e-1] + anc_dp_sum[ anc[u][e-1] ][e-1];
for(int v: desc[u][e])
binary_lift(v, e+1);
}
void dfs2(int u)
{
for(int v: desc[u][0])
{
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];
}
else
{
int sb = star_bottom[u];
dbg_flag = 1;
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) ];
dbg_flag = 0;
dp[u] = max(child_dp_sum[u], new_dp);
}
}
int main()
{
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 < lowest_pow.size(); i++)
lowest_pow[i] = 1 + lowest_pow[i/2];
sparse_table S;
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;
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 << "done\n";
}
// cerr << "check\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++)
{
for(int o: openings[i])
{
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();
}
for(int c: closings[i])
{
ST.pop_back();
}
}
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++)
{
if(anc[j][0] == 0)
{
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:195:16: error: expected ';' before 'cin'
195 | cin.tie(NULL)
| ^
| ;
196 |
197 | cin >> N;
| ~~~
constellation3.cpp:211:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for(int i = 2; i < lowest_pow.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:295:17: warning: unused variable 'c' [-Wunused-variable]
295 | for(int c: closings[i])
| ^
