## 【19HDU多校】HDU-6638 Snowy Smile 扫描线/区间连续最大和

### 传送门

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll r)
{
t[p].l = l; t[p].r = r;
if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum = 0, t[p].dat = 0; return;}
ll mid = (l + r) >> 1;
build(ls(p), l, mid); build(rs(p), mid + 1, r);
t[p].dat = t[p].rsum = t[p].lsum = t[p].sum = 0;
}
void update(ll p, ll l, ll r, ll v)
{
if(l <= t[p].l && r >= t[p].r)
{
t[p].dat += v;
t[p].lsum += v;
t[p].rsum += v;
t[p].sum += v;
return ;
}
ll mid = (t[p].l + t[p].r) >> 1;
if(l <= mid) update(ls(p), l, r, v);
if(r > mid) update(rs(p), l, r, v);
t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
t[p].lsum = max(t[ls(p)].lsum, t[ls(p)].sum + t[rs(p)].lsum);
t[p].rsum = max(t[rs(p)].rsum, t[rs(p)].sum + t[ls(p)].rsum);
t[p].dat = max(max(t[ls(p)].dat, t[rs(p)].dat), t[ls(p)].rsum + t[rs(p)].lsum);
}
{
return t[1].dat;
}
pair<pair<int,int> ,int > a[maxn];
set<int> st;
unordered_map<int,int> ump;
int main()
{
int T; cin >> T;
while(T--)
{
int x, y, w;
st.clear();
ump.clear();
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", &x, &y, &w);
a[i] = {{x, y}, w};
st.insert(y);
}
int cnt = 0;
for(auto it = st.begin(); it != st.end(); it++)
ump[*it] = ++cnt;

sort(a + 1, a + 1 + n);
ll ans = LONG_LONG_MIN;
for(int i = 1; i <= n; i++)
{
if(a[i].first.first == a[i - 1].first.first) continue;
build(1, 1, cnt);
for(int k = i; k <= n;)
{
int j = k;
while(j <= n && a[j].first.first == a[k].first.first)
{
int y = ump[a[j].first.second], w = a[j].second;
update(1, y, y, w);
j++;
}
ans = max(ans, ask());
k = j;
}
}
cout << ans << endl;
}
}