| by XianKa | No comments

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

传送门

题意很简单,就是求矩阵的最大子矩阵。

数据范围是坐标很多,但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界,再依次加入某些x相同的点,这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界,用区间连续最大和来“确定”上下边界。

联动ACWING126

#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 
Read the rest Read More