题意

给定 的直方图与 个带权关键点，定义两个点有边为它们形成的矩形与直方图无交，求最大权独立集补集的权。

思路

考虑对于直方图有经典转化，将其看作为笛卡尔树然后自底向上合并。

我们定义关键点 的控制区间为 ，满足其中的每个点的直方图高度都小于等于 的高度，显然，对于 （高度大于 ）跟 有边当且仅当 。

然后进行贪心，考虑我们试着往最大权独立集插入权值为 的点，使得总计权值为 的一些点弹出。

我们设这个 的数组为 。

先假定 ，此时 必然插入，那么我们令 。

---

然后考虑 ：

1. 如果 则不插入（弹出 ），因为 的控制区间肯定比其下的的点要大，更容易冲突，而且没有使答案更优。

2. 如果 则插入，但是其可能不在最终答案里，考虑这种情况：

   5
     8
   #4

   最优解显然为保留 ，但是插入 的时候其会弹出 ，所以我们需要进行撤销操作。

   对于上面某个点 ，假定其没有被弹出），其插入有两种情况：

   1. 弹出 ，并且将 放回，这意味着 只与 有连边。这对应为 。
   2. 弹出 ，但不将 放回，这意味着 与 都有连边，即在 中。这对应为 。

   于是我们直接令 ， 原有的 会恰好抵消掉。

   注意到我们只讨论了 中仅有一个点的情况，剩余的可以归纳证明。

CODE

#include<cstdio>
#include<vector>
using namespace std;
using ll=long long;
const int N=1000010,FSIZE=1<<24;
int n,m,l[N],r[N];
ll ans;
vector<int> h[N];
vector<pair<int,int>> s[N];
struct FT{
    ll a[N];
    void modify(int x,int y,ll c){
        a[x]+=c;
        a[++y]-=c;
        for(;x!=y;)
            if(x<y) a[x+=x&-x]+=c;
            else a[y+=y&-y]-=c;
    }   
    ll query(int x){
        ll re=0;
        for(;x;x-=x&-x) re+=a[x];
        return(re);
    }
}t;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
int get(int *s,int x){return(s[x]?s[x]=get(s,s[x]):x);}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1,x;i<=n;++i){
        read(x);
        h[x].push_back(i);
    }
    read(m);
    for(int i=1,x,y,c;i<=m;++i){
        read(x);read(y);read(c);
        s[y].emplace_back(x,c);
    }
    for(int i=1;i<=n;++i){
        for(auto j:s[i]){
            int p=j.first;
            ll x=t.query(p);
            if(x<j.second){
                ans+=x;
                t.modify(get(l,p),get(r,p),j.second-x);
            }else ans+=j.second;
        }
        for(auto j:h[i]) l[j+1]=r[j-1]=j;
    }
    printf("%lld\n",ans);
    return(0);
}