#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MN = 2e5+5;
int N,A[MN],X[MN],Y[MN],C[MN],T[MN<<!];
ll L[MN],R[MN];
vector<int> V[MN];
void upt(int s, int e, int x, int v, int i)
{
int m = (s+e)/2;
if(s==e){
T[i] = v;
return;
}
if(x<=m) upt(s,m,x,v,i<<1);
else upt(m+1,e,x,v,i<<1|1);
T[i] = A[T[i<<1]]>A[T[i<<1|1]] ? T[i<<1] : T[i<<1|1];
}
int getm(int s, int e, int x, int y, int i)
{
if(e<x||y<s) return 0;
if(x<=s&&e<=y) return T[i];
int m = (s+e)/2;
int l = getm(s,m,x,y,i<<1), r = getm(m+1,e,x,y,i<<1|1);
return A[l]>A[r] ? l : r;
}
int maxc(int x, int y)
{
int res = 0;
for(int i:V[x]){
if(Y[i]>y) continue;
res = max(res,C[i]);
}
return res;
}
ll solve(int s, int e, int y)
{
if(s<1||e>N||s>e) return 0;
//cout << s << ' ' << e << ' ' << y << '\n';
int m = getm(1,N,s,e,1);
if(L[m]<0) L[m] = solve(s,m-1,A[m]);
if(R[m]<0) R[m] = solve(m+1,e,A[m]);
ll res = L[m]+R[m]+maxc(m,y);
res = max(res,solve(s,m-1,y)+R[m]);
res = max(res,L[m]+solve(m+1,e,y));
return res;
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> N;
for(int i=1; i<=N; i++){
cin >> A[i];
upt(1,N,i,i,1);
L[i] = R[i] = -1;
}
A[0] = -1;
int M;
cin >> M;
ll sum = 0;
for(int i=0; i<M; i++){
cin >> X[i] >> Y[i] >> C[i];
V[X[i]].push_back(i);
sum += C[i];
}
cout << sum-solve(1,N,N);
}
Compilation message
constellation3.cpp:8:38: error: expected primary-expression before ']' token
8 | int N,A[MN],X[MN],Y[MN],C[MN],T[MN<<!];
| ^
constellation3.cpp: In function 'void upt(int, int, int, int, int)':
constellation3.cpp:16:3: error: 'T' was not declared in this scope
16 | T[i] = v;
| ^
constellation3.cpp:21:2: error: 'T' was not declared in this scope
21 | T[i] = A[T[i<<1]]>A[T[i<<1|1]] ? T[i<<1] : T[i<<1|1];
| ^
constellation3.cpp: In function 'int getm(int, int, int, int, int)':
constellation3.cpp:27:24: error: 'T' was not declared in this scope
27 | if(x<=s&&e<=y) return T[i];
| ^
