BZOJ4653 尺取法 + 线段树

时间：2021-07-27 06:43:22

https://www.lydsy.com/JudgeOnline/problem.php?id=4653

首先很容易想到离散之后排序，用线段树或者树状数组去维护。

问题在于按照什么排序，如果按照左端点右端点排序，线段树就需要维护最大值最小值和区间和等等信息，在区间和超过M之后最大值就变为了K大到最大的信息，不但麻烦而且难以下手。

所以想到直接按照区间长度排序，仅仅维护一个区间最值，代表这个区间里最大的点被覆盖了多少次，然后用一种尺取的思想，使得线段树里的最大值一值不超过M，如果超过了就在尾部开始删除直到M以下，与此同时更新最大值。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

int read(){int x = ,f = ;char c = getchar();while (c<'' || c>''){if (c == '-') f = -;c = getchar();}

while (c >= ''&&c <= ''){x = x *  + c - '';c = getchar();}return x*f;}

const double eps = 1e-;

const int maxn = 5e5 + ;

const int maxm = 2e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

int Hash[maxn * ];

int len[maxn];

PII line[maxn];

struct Tree{

    int l,r,lazy,Max;

}tree[maxn << ];

void Build(int t,int l,int r){

    tree[t].l = l; tree[t].r = r;

    tree[t].lazy = tree[t].Max = ;

    if(l == r) return;

    int m = (l + r) >> ;

    Build(t << ,l,m); Build(t <<  | ,m + ,r);

}

void Pushdown(int t){

    if(tree[t].lazy){

        tree[t << ].lazy += tree[t].lazy;

        tree[t <<  | ].lazy += tree[t].lazy;

        tree[t << ].Max += tree[t].lazy;

        tree[t <<  | ].Max += tree[t].lazy;

        tree[t].lazy = ;

    }

}

void Pushup(int t){

    tree[t].Max = max(tree[t << ].Max,tree[t <<  | ].Max);

}

void update(int t,int l,int r,int w){

    if(l <= tree[t].l && tree[t].r <= r){

        tree[t].Max += w;

        tree[t].lazy += w;

        return;

    }

    Pushdown(t);

    int m = (tree[t].l + tree[t].r) >> ;

    if(r <= m) update(t << ,l,r,w);

    else if(l > m) update(t <<  | ,l,r,w);

    else{

        update(t << ,l,m,w); update(t <<  | ,m + ,r,w);

    }

    Pushup(t);

}

bool cmp(PII a,PII b){

    return a.se - a.fi < b.se - b.fi;

}

int main(){

    Sca2(N,M);

    int cnt = ;

    for(int i = ; i <= N; i ++){

        line[i].fi = read(); line[i].se = read();

        Hash[++cnt] = line[i].fi; Hash[++cnt] = line[i].se;

    }

    sort(Hash + ,Hash +  + cnt);

    sort(line + ,line +  + N,cmp);

    cnt = unique(Hash + ,Hash +  + cnt) - Hash - ;

    for(int i = ; i <= N ; i ++){

        len[i] = line[i].se - line[i].fi;

        line[i].fi = lower_bound(Hash + ,Hash +  + cnt,line[i].fi) - Hash;

        line[i].se = lower_bound(Hash + ,Hash +  + cnt,line[i].se) - Hash;

    }

    Build(,,cnt);

    int tail = ;

    int ans = INF;

    for(int i = ; i <= N ; i ++){

        update(,line[i].fi,line[i].se,);

        while(tree[].Max >= M){

            ans = min(ans,len[i] - len[tail]);

            update(,line[tail].fi,line[tail].se,-);

            tail++;

        }

    }

    if(ans == INF) ans = -;

    Pri(ans);

    return ;

}

相关文章