线段树
可以先把纵坐标离散化，然后按横坐标排序，然后按照x来枚举矩形的左右边界，因为排完序之后相同的
x肯定是在一起的。用线段树维护相同y下的权值，这样问题就变成区间最大子段和。
#include#define INF 2333333333333333333#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define range(x) (x).begin(), (x).end()#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){ int ret = 0, w = 0; char ch = 0; while(!isdigit(ch)){ w |= ch == '-', ch = getchar(); } while(isdigit(ch)){ ret = (ret << 3) + (ret << 1) + (ch ^ 48); ch = getchar(); } return w ? -ret : ret;}template inline A lcm(A a, A b){ return a / __gcd(a, b) * b; }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 3000;int _, n, x[N], y[N], w[N], a[N];LL pre[N<<2], suf[N<<2], sum[N<<2], tree[N<<2];struct Col{ int x, y, w; Col(){} Col(int x, int y, int w): x(x), y(y), w(w){} bool operator < (const Col &rhs) const { return x < rhs.x; }};vector v;void push_up(int rt){ int l = rt << 1, r = rt << 1 | 1; pre[rt] = max(pre[l], sum[l] + pre[r]); suf[rt] = max(suf[r], sum[r] + suf[l]); sum[rt] = sum[l] + sum[r]; tree[rt] = max(suf[l] + pre[r], max(tree[l], tree[r]));}void buildTree(int rt, int l, int r){ if(l == r){ pre[rt] = suf[rt] = sum[rt] = tree[rt] = 0; return; } int mid = (l + r) >> 1; buildTree(rt << 1, l, mid); buildTree(rt << 1 | 1, mid + 1, r); push_up(rt);}void insert(int rt, int l, int r, int pos, LL val){ if(l == r){ pre[rt] += val, suf[rt] += val, sum[rt] += val, tree[rt] += val; return; } int mid = (l + r) >> 1; if(pos <= mid) insert(rt << 1, l, mid, pos, val); else insert(rt << 1 | 1, mid + 1, r, pos, val); push_up(rt);}int main(){ //freopen("data.txt", "r", stdin); //freopen("out.txt", "w", stdout); for(_ = read(); _; _ --){ n = read(); for(int i = 1; i <= n; i ++){ x[i] = read(), y[i] = read(), w[i] = read(); a[i] = y[i]; } sort(a + 1, a + n + 1); int k = (int)(unique(a + 1, a + n + 1) - a - 1); for(int i = 1; i <= n; i ++){ int p = (int)(lower_bound(a + 1, a + k + 1, y[i]) - a); v.emplace_back(x[i], p, w[i]); } sort(range(v)); LL ans = 0; for(int i = 0; i < n; i ++){ if(i == 0 || v[i].x != v[i - 1].x){ buildTree(1, 1, k); int j = i; for(; j < n; j ++){ if(v[j].x == v[i].x) insert(1, 1, k, v[j].y, v[j].w); else break; } ans = max(ans, tree[1]); int p; for(; j < n; j = p){ for(p = j; p < n; p ++){ if(v[j].x == v[p].x) insert(1, 1, k, v[p].y, v[p].w); else break; } ans = max(ans, tree[1]); } } } printf("%lld\n", ans); v.clear(); } return 0;}