先看代码：

#include<bits/stdc++.h>
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
#define G(v, i, u) for(int i=head[u], v=e[i].v; i; v=e[i=e[i].nxt].v)
#define de(x) cout<<#x<<" "<<x<<"  "
#define nd cout<<endl
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
using namespace std;
typedef long long ll;
const int N=2e5+7;
struct line{
    int l; ll w;
};
int n, m, x, y, a[N], b[N];
ll d[N], f[N], s[N];
vector<int> at[N], ec[N];
vector<line> z[N];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m>>x>>y;
    rep(i, 1, x) cin>>d[i];
    rep(i, 1, n){
        cin>>a[i]>>b[i];
        at[b[i]].emplace_back(i);
        ec[a[i]].emplace_back(i);
        s[i]=s[i-1]+d[b[i]];
    }
    while(m--){
        int p, q; ll c;
        cin>>p>>q>>c;
        vector<int> &at=::at[q], &ec=::ec[p];
        if(at.size()<ec.size()){
            for(auto x:at){
                auto it=lower_bound(ec.begin(), ec.end(), x);
                if(it!=ec.begin()){
                    --it;
                    ll w=c-(s[x-1]-s[*it-1]);
                    if(w>0){
                        z[x].emplace_back((line){*it, w});
                    }
                }
            }
        } else{
            for(auto x:ec){
                auto it=upper_bound(at.begin(), at.end(), x);
                if(it!=at.end()){
                    ll w=c-(s[*it-1]-s[x-1]);
                    if(w>0){
                        z[*it].emplace_back((line){x, w});
                    }
                }
            }
        }
    }
    rep(i, 1, n){
        f[i]=f[i-1];
        for(auto x:z[i])
            f[i]=max(f[i], f[x.l-1]+x.w);
    }
    cout<<s[n]+f[n]<<'\n';
}

思路比较奇怪，先用vector存下攻击类型和异常状态类型出现的位置，然后对于每一种反应，枚举位置数较小的一个，二分出最接近的另一个并计算答案。

窝认为复杂度应该为 $O(n\sqrt n \log n)$，但是不会证，有没有大佬来帮帮这个蒟蒻QwQ