【題解】TIOJ 1974 . 十字射擊（Cross）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 200005;
int n, seg[maxn*4], lazy[maxn*4], l[maxn], d[maxn], r[maxn], u[maxn], w[maxn];
vector <int> id;
vector <pair<int, pair<int, int>>> v;

int get_id(int x){
    return lower_bound(id.begin(), id.end(), x)-id.begin()+1;
}
void update(int x, int l, int r, int ul, int ur, int u){
    //cout << x << " " << l << " " << r << " " << ul << " " << ur << " " << u << "\n";
    if (ul <= l && r <= ur){
        seg[x] += u;
        lazy[x] += u;
        return;
    }
    int mid = (l+r)/2;
    seg[x*2] += lazy[x];
    lazy[x*2] += lazy[x];
    seg[x*2+1] += lazy[x];
    lazy[x*2+1] += lazy[x];
    lazy[x] = 0;
    if (ul <= mid) update(x*2, l, mid, ul, ur, u);
    if (ur > mid) update(x*2+1, mid+1, r, ul, ur, u);
    seg[x] = max(seg[x*2], seg[x*2+1]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> l[i] >> d[i] >> r[i] >> u[i] >> w[i];
        id.push_back(d[i]);
        id.push_back(u[i]);
        v.push_back({l[i], {i, 1}});
        v.push_back({r[i]+1, {i, -1}});
    }
    sort(v.begin(), v.end());
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    for (int i = 1; i <= n; i++){
        update(1, 1, (int)id.size(), get_id(d[i]), get_id(u[i]), w[i]);
    }
    int ans = 0, sum = 0;
    for (int i = 0; i < v.size(); i++){
        int now = v[i].first;
        while (i < v.size() && v[i].first == now){
            int j = v[i].second.first;
            if (v[i].second.second == 1){
                update(1, 1, (int)id.size(), get_id(d[j]), get_id(u[j]), -w[j]);
                sum += w[j];
            }
            else{
                update(1, 1, (int)id.size(), get_id(d[j]), get_id(u[j]), w[j]);
                sum -= w[j];
            }
            i++;
        }
        i--;
        ans = max(ans, seg[1]+sum);
    }
    cout << ans << "\n";
}