HDU 6638 最大子矩阵 线段树 发表于 2019-08-19 | 分类于 ACM题解 | 阅读次数: 最大子矩阵的O(N^2logN)做法 题目链接 思路枚举y坐标的上界和下界,将x坐标离散化后在对应位置更新,直到将矩阵压缩成一维序列进行更新。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <queue>#include <stack>#include <ctype.h>using namespace std;typedef long long ll;const int maxn = 2005;struct Node{ ll sum , sum_max, pre_max, post_max;}tr[maxn << 2];struct node{ int x, y,value;}a[maxn];int x[maxn];bool cmp(node a, node b){ if(a.y == b.y) { return a.x < b.x; } return a.y < b.y;}void pushup(int node){ int ls = node << 1; int rs = node << 1|1; tr[node].sum = tr[ls].sum + tr[rs].sum; tr[node].sum_max = max(max(tr[ls].sum_max,tr[rs].sum_max),tr[ls].post_max + tr[rs].pre_max); tr[node].post_max = max(tr[rs].post_max, tr[ls].post_max + tr[rs].sum); tr[node].pre_max = max(tr[ls].pre_max,tr[ls].sum + tr[rs].pre_max );}void update(int node , int l, int r, int pos , int k){ if(l == r && l == pos) { tr[node].post_max += k; tr[node].pre_max += k; tr[node].sum += k; tr[node].sum_max += k; return; } int mid = (l + r ) >> 1; if(pos <= mid) update(node << 1, l, mid, pos, k); else update(node << 1|1, mid + 1, r, pos, k); pushup(node);}int main(){ int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); int tot = 0; for(int i = 1; i <= n; ++i) { scanf("%d %d %d",&a[i].x,&a[i].y , &a[i].value); x[++tot] = a[i].x; } sort(a + 1, a + n + 1, cmp); sort(x + 1, x + tot + 1); ll Max = -1; tot = unique(x + 1, x + tot + 1) - x - 1; for(int i = 1; i <= n; ++i) { if(i != 1 && a[i].y == a[i - 1].y) continue; memset(tr, 0, sizeof(tr)); for(int j = i ; j <= n; ++j) { int pos = lower_bound(x + 1, x + tot + 1, a[j].x) - x ; update(1, 1, tot, pos, a[j].value); if(j == n || (a[j].y != a[j + 1].y)) { Max = max(tr[1].sum_max, Max); } } } cout << Max << '\n'; }} 打赏