Codeforces 1321 E. World of Darkraft: Battle for Azathoth（線段樹）

題意：

有 n n n 個武器每個武器 a i a_i ai​ 攻擊買這個花費 c a i c_{a_i} cai​​， m m m 個防具每個防禦 b i b_i bi​ 花費 c b i c_{b_i} cbi​​， p p p 個怪物每個 x x x 攻擊 y y y 防禦掉 z z z 金币，武器任選一個防具任選一個，把能殺的怪物都殺掉，能殺的怪物是你的攻擊大于它的防禦 你的防禦大于它的攻擊，問殺怪收益-買裝備花費最多為多少

把武器的初始收益置為 c a i c_{a_i} cai​​，然後按防禦力小到大枚舉每件盔甲，同時不斷更新攻擊力小于目前盔甲防禦力，答案就是武器收益-盔甲價格的最大值。線段樹區間覆寫維護最大。

AC代碼：

const int N = 2e5 + 5;
const int INF = 0x7fffffff;
int n, m, p;

struct node
{
    int a, c;
    node(int x = 0)
    {
        a = x, c = 0;
    }
} wp[N], ar[N];
bool operator<(node a, node b)
{
    return a.a < b.a;
}
struct node2
{
    int x, y, z;
} mon[N];

bool operator<(node2 a, node2 b)
{
    return a.x < b.x;
}

int ans = -INF;
int mx[N << 2], tag[N << 2];

inline void add(int k, int v)
{
    mx[k] += v;
    tag[k] += v;
}
inline void pushup(int k)
{
    mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
}
inline void pushdwn(int k)
{
    add(k << 1, tag[k]);
    add(k << 1 | 1, tag[k]);
    tag[k] = 0;
}
void build(int k, int l, int r)
{
    if (l == r)
    {
        mx[k] = -ar[l].c;
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
    return;
}

void modify(int k, int l, int r, int qx, int qy, int qv)
{
    if (qx <= l && r <= qy)
        return add(k, qv);
    pushdwn(k);
    int mid = l + r >> 1;
    if (qx <= mid)
        modify(k << 1, l, mid, qx, qy, qv);
    if (mid < qy)
        modify(k << 1 | 1, mid + 1, r, qx, qy, qv);
    pushup(k);
    return;
}

int main()
{
    sddd(n, m, p);
    rep(i, 1, n)
        sdd(wp[i].a, wp[i].c);
    rep(i, 1, m)
        sdd(ar[i].a, ar[i].c);
    sort(wp + 1, wp + n + 1);
    sort(ar + 1, ar + m + 1);
    rep(i, 1, p)
        sddd(mon[i].x, mon[i].y, mon[i].z);
    sort(mon + 1, mon + p + 1);
    build(1, 1, m);
    for (int i = 1, s1 = 0; i <= n; i++)
    {
        while (s1 < p && mon[s1 + 1].x < wp[i].a)
        {
            s1++;
            int w = upper_bound(ar + 1, ar + m + 1, node(mon[s1].y)) - ar;
            if (w <= m)
                modify(1, 1, m, w, m, mon[s1].z);
        }
        ans = max(ans, mx[1] - wp[i].c);
    }
    pd(ans);
    return 0;
}