# 【題解】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";
}
```