PTA 森森快递（线段树区间修改）

 先贪心，筛掉包含小区间的大区间（大区间浪费资源），相交区间不影响，按顺序查询修改即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;

typedef struct Point
{
    int x;
    int y;
    Point(int xx, int yy)
    {
        x = xx; y = yy;
    }
}Point;


struct Node
{
    ll val;
    int seg;
}node[maxn << 2];
vector<Point> vec;
int num[maxn];
int n, q;


bool cmp(Point a, Point b)
{
    if(a.y != b.y)  return a.y < b.y;
    return a.x < b.x;
}


void pushup(int rt)
{
    node[rt].val = min(node[rt << 1].val, node[rt << 1|1].val);
}


void build(int rt, int l, int r)
{
    if(l == r)
    {
        node[rt].val = num[l];
        node[rt].seg = 0;
        return;
    }

    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1|1, mid + 1, r);
    pushup(rt);
}



void pushdown(int rt)
{
    node[rt << 1].val += node[rt].seg;
    node[rt << 1|1].val += node[rt].seg;
    node[rt << 1].seg = node[rt << 1|1].seg = node[rt].seg;
    node[rt].seg = 0;
}


int query(int rt, int l, int r, int ql, int qr)
{
    if(l == ql && r == qr)
    {
        return node[rt].val;
    }
    if(node[rt].seg)
        pushdown(rt);

    int mid = l + r >> 1;
    if(qr <= mid)   return query(rt << 1, l, mid, ql, qr);
    else if(ql > mid)   return query(rt << 1|1, mid + 1, r, ql, qr);
    else
        return min(query(rt << 1, l, mid, ql, mid), query(rt << 1|1, mid + 1, r, mid + 1, qr));
    //pushup(rt);
}


void update(int rt, int l, int r, int ql, int qr, int v)
{
    if(ql == l && qr == r)
    {
        node[rt].val += v;
        node[rt].seg += v;
        return;
    }
    if(node[rt].seg)
        pushdown(rt);

    int mid = l + r >> 1;
    if(qr <= mid)   update(rt << 1, l, mid, ql, qr, v);
    else if(ql > mid)   update(rt << 1|1, mid + 1, r, ql, qr, v);
    else
    {
        update(rt << 1, l, mid, ql, mid, v);
        update(rt << 1|1, mid + 1, r, mid + 1, qr, v);
    }
    pushup(rt);
}



int main()
{
    cin >> n >> q;
    for(int i = 1; i < n; i++)      //考虑到线段树root从1开始
        cin >> num[i];

    build(1, 1, n - 1);

    int a, b;
    for(int i = 0; i < q; i++)
    {
        cin >> a >> b;
        if(a > b)   swap(a, b);
        vec.push_back(Point(a, b));
    }
    sort(vec.begin(), vec.end(), cmp);

    ll ans = 0;
    for(int i = 0; i < q; i++)
    {
        a = vec[i].x;
        b = vec[i].y;

        if(a == b)  continue;
        ll cur = query(1, 1, n - 1, a + 1, b);        //
        //cout << "turn " << i << "'s ans: " << cur << endl;
        ans += cur;
        update(1, 1, n - 1, a + 1, b, -cur);
    }
    printf("%lld\n", ans);

    return 0;
}