A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2687: 交与并 双指针 单调性
发表于: | 分类: Oi | 评论:0 | 阅读:108

这题大家写题都不写证明我给差评

显然被包含的区间的计算没有不包含的优,因为并更大,所以先去掉所有的包含区间并更新一波答案

首先这个东西等价选择两个区间表示选取了最左面和最右面的两个区间。然后如果大力枚举大概是$n^2$的

然后我就在想线段树怎么做

最后无耻的开了题解

某博客:这东西是有单调性的扫扫就行了

于是我就开始证单调,写了十分钟最后证出来然后问$Infinity37$

然后发现他就默认单调的……好了我们来看看他为什么单调

我们假设这个东西他不是单调的

那么就是说当$l_1 < l_2< l_3 <l_4, r_1 < r_2 < r_3 < r_4$的时候

$(r_2-l_3)(r_3-l_2)>(r_3-l_1)(r_1-l_3)$ 且 $(r_4-l_2)(r_2-l_4) < (r_4-l_1)(r_1-l_4)$

注意到$a>b,c>d,a+c>b+d$

所以我们把同向的东西加到一起然后大力展开

然后分别提取出$r_4,l_1,l_2,r_3$,其实就是因式分解

然后你最后会推出这样一个东西$(r_4-r_3)(r_1-r_2)+(l_3-l_4)(l_2-l_1) > 0$

md俩负数加一起最后大于0你在逗我,证毕

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+5;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data{
    LL l, r;
    bool operator < (const data &z) const {
        return l != z.l ? l < z.l : r > z.r;
    }
} a[N];

inline LL calc(int x,int y) {
    return (a[x].r-a[y].l)*(a[y].r-a[x].l);
}

bool flag[N];

int main() {
    int n = read();
    for(int i=1;i<=n;++i) a[i].l = read(), a[i].r = read();
    sort(a+1,a+n+1);
    register int j;
    int now = 0 , mxp = 0;
    LL ans = 0;
    for(int i=1;i<=n;++i) {
        if(a[i].r<=now) { 
            flag[i] = mxp;
            ans = max(ans, (LL)(a[i].r-a[i].l)*(a[mxp].r-a[mxp].l));
        }
        else flag[i] = 0;
        if(now < a[i].r) {
            now = a[i].r;
            mxp = i;
        }
    }  
    int top = 0;
    for(int i=1;i<=n;++i) if(flag[i] == 0) a[++top] = a[i];
    n = top;
    j = 2;
    for(int i=1;i<n;++i) {
        if(i == j) ++j;
        while(j+1<=n && calc(i,j+1) > calc(i,j)) ++ j;
        ans = max(ans, calc(i,j));
    }
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP