扫描线Tag ArchiveSubscribe

传送门

题意是说给n<=3e5条宽度为1的线段，长度不定。

要求一个对称轴，使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法，更为简单。

1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。

2. 对于这些预处理出的线，仅仅记录一个y坐标，按照坐标从小到大排序。

3. 枚举这些线当作对称轴，从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴，上一条线为下半段。按照扫描线一层一层的计算面积贡献。

4. 在某个线段遇到中线之前，他的面积贡献都是存在的。因为他按照当前扫描线往上翻折，扫描线下方的面积肯定小 于上方，所以贡献是下方面积的两倍 ，于是下边界的贡献flag = 1。

5. 当扫描线遇到中线的时候，肯定是之前某个线段的中线，此时这条线段在扫描线下方的面积大于等于上方面积，同时这条线段已经达到最大的面积贡献，当扫描线再往上走的时候会减少贡献，每当中线网上移动距离 k 的时候，这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失，变成 0 贡献。于是中线的贡献flag = -2，上边界的flag = 1。

6. 所以用变量cnt对当前层做出贡献的线段条数，面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数，于是为了代码方便，把坐标都扩大两倍，同时计算面积的时候不用乘2。

其实最核心的点就是每当对称轴向上移动k距离的时候，整条线就应该缩短2k的距离，这样才能保证图形是对称的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 

传送门

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

数据范围是坐标很多，但是点最多有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