本文共 3170 字，大约阅读时间需要 10 分钟。
https://www.lydsy.com/JudgeOnline/problem.php?id=4653
首先很容易想到离散之后排序，用线段树或者树状数组去维护。
问题在于按照什么排序，如果按照左端点右端点排序，线段树就需要维护最大值最小值和区间和等等信息，在区间和超过M之后最大值就变为了K大到最大的信息，不但麻烦而且难以下手。
所以想到直接按照区间长度排序，仅仅维护一个区间最值，代表这个区间里最大的点被覆盖了多少次，然后用一种尺取的思想，使得线段树里的最大值一值不超过M，如果超过了就在尾部开始删除直到M以下，与此同时更新最大值。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 5e5 + 10;const int maxm = 2e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int Hash[maxn * 2];int len[maxn];PII line[maxn];struct Tree{ int l,r,lazy,Max;}tree[maxn << 3];void Build(int t,int l,int r){ tree[t].l = l; tree[t].r = r; tree[t].lazy = tree[t].Max = 0; if(l == r) return; int m = (l + r) >> 1; Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);}void Pushdown(int t){ if(tree[t].lazy){ tree[t << 1].lazy += tree[t].lazy; tree[t << 1 | 1].lazy += tree[t].lazy; tree[t << 1].Max += tree[t].lazy; tree[t << 1 | 1].Max += tree[t].lazy; tree[t].lazy = 0; }}void Pushup(int t){ tree[t].Max = max(tree[t << 1].Max,tree[t << 1 | 1].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) >> 1; if(r <= m) update(t << 1,l,r,w); else if(l > m) update(t << 1 | 1,l,r,w); else{ update(t << 1,l,m,w); update(t << 1 | 1,m + 1,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 = 0; for(int i = 1; i <= N; i ++){ line[i].fi = read(); line[i].se = read(); Hash[++cnt] = line[i].fi; Hash[++cnt] = line[i].se; } sort(Hash + 1,Hash + 1 + cnt); sort(line + 1,line + 1 + N,cmp); cnt = unique(Hash + 1,Hash + 1 + cnt) - Hash - 1; for(int i = 1; i <= N ; i ++){ len[i] = line[i].se - line[i].fi; line[i].fi = lower_bound(Hash + 1,Hash + 1 + cnt,line[i].fi) - Hash; line[i].se = lower_bound(Hash + 1,Hash + 1 + cnt,line[i].se) - Hash; } Build(1,1,cnt); int tail = 1; int ans = INF; for(int i = 1; i <= N ; i ++){ update(1,line[i].fi,line[i].se,1); while(tree[1].Max >= M){ ans = min(ans,len[i] - len[tail]); update(1,line[tail].fi,line[tail].se,-1); tail++; } } if(ans == INF) ans = -1; Pri(ans); return 0;}
转载于:https://www.cnblogs.com/Hugh-Locke/p/10361551.html