自动搬运

查看原文

来自洛谷，原作者为

	君のNOIP。 清新出题人

搬运于2025-08-24 22:22:20，当前版本为作者最后更新于2020-04-22 13:00:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先讲一下这题各种部分分的复杂度。

---

花式暴力：

• 8分，$O(nm^3)$

• 16分，$O(nm^2)$

• 24分，$O(n^4)$

• 32分，$O(n^3)$

• 40分，$O(n^2logn)$

• 48分，$O(n^2)$

送分结束。

---

认真骗分：

• 64分，在 $O(n^2)$ 做法上加个小优化。

• 84分，数据结构：$O(nklog^2 n)$ 或 $O(nk^2logn)$

---

简单正解：

• 100分，$O(n(k+logn))$

---

48分： $O(n^2)$ 的暴力。

很显然，最优解一定是某两个有标记的点（包括 $-1$ 和 $m+1$）之间的距离 $-1$ ，这两个点只需要满足他们之间（不包括这两个点）的标记数 $\le k$ 即可。

所以我们只需枚举有标记的点作为左端点和右端点即可。

按照这个思路，我们可以直接用 set 和 map ，但是我不太会用。

如果用数组存，只需先离线记录各个输入，然后开个结构体排个序再 map 瞎搞搞就好了。

每次操作的时候，枚举左端点，将右端点不断向右挪就好了。

Code:

#include<bits/stdc++.h>
using namespace std;
int n, m, k;
int ans;
int num[10005], pos[10005], cnt;
struct node{
	int x, a;
} e[10005];
int x[10005], a[10005];
map<int,int>mp;

bool comp(node x,node y){
	return x.x < y.x;
}

int main(){
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
    	cin>>e[i].x>>e[i].a;
    	x[i] = e[i].x, a[i] = e[i].a;
	}
	e[n+1].x = -1;
	sort(e+1,e+2+n,comp);
	for(int i = 1; i <= n + 1; i++){
		if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
		mp[e[i].x] = cnt;
	}
	pos[cnt+1] = m + 1;
	for(int i = 1; i <= n; i++){
		num[mp[x[i]]] += a[i];
		int t = 1, s = 0;
		ans = -1;
		for(int j = 1; j <= cnt; j++){
			s -= num[j];
			while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
			ans = max(ans,pos[t+1] - pos[j] - 2);
		}
		cout<<ans<<endl;
	}
}

---

64分： $O(n^2)$ 的暴力 + 优化。

• 保证测试点 $13\sim 16$ 的 $x_i$ 为随机构造。

很显然，每次操作的答案小于等于上次的答案。

其实在随机数据下，是会有很多相同的答案的。

因为随着操作的增多，答案区间也越来越小，需要更新答案的概率也就越低。

所以如果某次操作的答案与上次的相同，那么就不用再更新答案。

怎么判断某次的答案是不是与上次的相同呢？

我们每次操作后记录下当前答案区间的左右端点，很显然如果某次操作的 $x_i$ 不在上次的答案区间内，就不用更新答案。

Code：

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 1000005
int n, m, k;
int ll, rr;
int ans;
int num[MAX_N], pos[MAX_N], cnt;
struct node{
	int x, a;
}e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
	return x.x < y.x;
}

int main(){
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
    	cin>>e[i].x>>e[i].a;
    	x[i] = e[i].x, a[i] = e[i].a;
	}
	e[n+1].x = -1;
	sort(e+1,e+2+n,comp);
	for(int i = 1;i <= n + 1; i++){
		if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
		mp[e[i].x]= c nt;
	}
	pos[cnt+1] = m+1;
	rr = m;
	for(int i = 1; i <= n; i++){
		num[mp[x[i]]] += a[i];
		if(x[i] >= ll && x[i] <= rr){
			int t = 1, s = 0;
			ans = -1;
			for(int j = 1; j <= cnt; j++){
				s -= num[j];
				while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
				if(pos[t+1] - pos[j] - 2 > ans) ans = pos[t+1] - pos[j] - 2, ll = pos[j] + 1, rr = pos[t+1] - 1;
			}
		}
		cout<<ans<<endl;
	}
}

---

84分：数据结构。

• 方法一：万能的线段树 $O(nk^2logn)$

注意到 $m\le 10^6$ ，那么我们可以直接开线段树维护。

只需维护符合要求的最大区间，从左端点开始的最大区间，从右端点开始的最大区间。

考虑到 $k\le 3$ ，我们只需开二维，每个节点 $k^2$ 暴力更新。

由于是单点修改，不需要下传标记。

询问也很简单，直接输出节点 $1$ 的最大区间即可。

每次上传信息的时候，就维护下该区间内有 $j$ 个标记时的最大区间，从左端点开始的最大区间，从右端点开始的最大区间即可。

所以这个连懒惰标记都不用的线段树就很好打了。

Code：

---

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
#define sum(i,j) tr[i].sum[j]
#define lst(i,j) tr[i].lst[j]
#define rst(i,j) tr[i].rst[j]
int Xr;char Cr;
inline int rd(){
	Xr=0, G();
	while(Cr<'0' || Cr>'9') G();
	while(Cr>='0' && Cr<='9') Xr=(Xr<<3) + (Xr<<1) + (Cr & 15), G();
	return Xr;
}
#define MAX_N 1000005
int n, m, k;
int ans;
int num[MAX_N];
int pos, a;

struct Node {
	int sum[5], lst[5], rst[5];
} tr[MAX_N<<2];

void Push_up(int i,int l,int r) {
	int mid = l + r >> 1;
	for(int j = 0; j <= k; j++)
		sum(i,j) = max(sum(i<<1,j),sum(i<<1|1,j)),
		lst(i,j) = lst(i<<1,j),
		rst(i,j) = rst(i<<1|1,j);
	for(int j = 0; j <= k; j++)
		for(int p = 0; p <= j; p++) {
			if(rst(i<<1,p) && lst(i<<1|1,j-p))sum(i,j) = max(sum(i,j), rst(i<<1,p) + lst(i<<1|1,j-p));
			if(lst(i<<1,p) == mid-l+1 && lst(i<<1|1,j-p)) lst(i,j) = max(lst(i,j), lst(i<<1,p) + lst(i<<1|1,j-p));
			if(rst(i<<1|1,p) == r-mid && rst(i<<1,j-p)) rst(i,j) = max(rst(i,j), rst(i<<1|1,p) + rst(i<<1,j-p));
		}
}

void Build(int i,int l,int r) {
	if(l == r) {
		sum(i,0) = lst(i,0) = rst(i,0) = 1;
		return;
	}
	int mid = l + r >> 1;
	Build(i<<1,l,mid);
	Build(i<<1|1,mid+1,r);
	Push_up(i,l,r);
}

void Change(int i,int l,int r,int P) {
	if(l>=P && r<=P) {
		for(int j=0;j<=k;j++) sum(i,j) = lst(i,j) = rst(i,j) = 0;
		if(num[l] <= k) sum(i,num[l]) = lst(i,num[l]) = rst(i,num[l]) = 1;
		return;
	}
	int mid = l + r >> 1;
	if(mid >= P) Change(i<<1,l,mid,P);
	else Change(i<<1|1,mid+1,r,P);
	Push_up(i,l,r);
}

int main() {
    n=rd(), m=rd(), k=rd();
    Build(1,0,m);
    for(int i = 1;i <= n;i++) {
    	pos=rd(), a=rd();
    	num[pos] += a;
    	Change(1,0,m,pos);
    	ans = -1;
    	for(int j = 0;j <= k; j++) ans = max(ans,sum(1,j) - 1);
    	printf("%d\n",ans);
	}
}

---

• 方法二：树状数组 + 二分 $O(nklog^2n)$

首先我们发现由于每次的答案小于等于上一次的答案，我们不能直接维护最大区间。

但如果将询问倒序处理呢？

我们发现答案变为大于等于上一次的答案。

这样问题就转化为每次删除若干标记。

这样还不够，我们发现每次如果更新答案，那么新的答案区间一定包含此处操作删除标记的那个点。

所以我们只需枚举最多 $k$ 个左端点，我们可以用树状数组维护在某个最终有标记的点的标记数前缀和，然后利用二分查找枚举左右端点即可。

Code：

---

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
    Xr = 0, G();
    while(Cr < '0' || Cr > '9') G();
    while(Cr >= '0' && Cr <= '9')Xr = (Xr<<3) + (Xr<<1) + (Cr & 15), G();
    return Xr;
}
#define LL long long
#define MAX_N 1000005
int n, m, k;
int ans[MAX_N];
int num[MAX_N], pos[MAX_N], cnt;
int ma = -1, s, t;
int sum[MAX_N];
struct node{
	int x, a;
} e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
	return x.x < y.x;
}

void add(int p,int x){
	while(p <= cnt) sum[p] += x, p += p & -p;
}

int gsum(int p){
	int ss=0;
	while(p) ss += sum[p], p -= p & -p;
	return ss;
}

int find_l(int p){
	int ss = gsum(p);
	int l=1, r=p, sss=p;
	while(l <= r){
		int mid = (l + r)>>1;
		if(ss - gsum(mid) <= k) sss = mid, r = mid - 1;
		else l = mid + 1;
	}
	return sss;
}

int find_r_j(int p){
	int ss = gsum(p);
	int l = p + 1, r = cnt, sss = p + 1;
	while(l <= r){
		int mid = (l + r)>>1;
		if(ss < gsum(mid)) sss = mid, r = mid - 1;
		else l = mid + 1;
	}
	return sss;
}

int find_r_t(int p){
	int ss = gsum(p);
	int l = p, r = cnt, sss = p;
	while(l <= r){
		int mid = (l + r)>>1;
		if(gsum(mid) - ss <= k) sss = mid, l = mid + 1;
		else r = mid - 1;
	}
	return sss;
}

int main(){
    n = rd(), m = rd(), k = rd();
    for(int i = 1; i <= n; i++) {
    	e[i].x = rd(), e[i].a = rd();
    	x[i] = e[i].x, a[i] = e[i].a;
	}
	e[n+1].x = -1;
	sort(e+1,e+2+n,comp);
	for(int i = 1; i <= n + 1; i++) {
		if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
		mp[e[i].x] = cnt;
	}
	pos[cnt+1] = m + 1;
	for(int i = 1; i <= n; i++) num[mp[x[i]]] += a[i], add(mp[x[i]],a[i]);
	for(int i = 1; i <= cnt; i++) {
		s -= num[i];
		while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
		ma=max(ma,pos[t+1] - pos[i] - 2);
	}
	ans[n] = ma;
	for(int i = n; i >= 2; i--) {
		int p = mp[x[i]];
		add(p,-a[i]);
		int j = find_l(p), t;
		while(j < p){
			t = find_r_t(j);
			ma = max(ma,pos[t+1] - pos[j] - 2);
			j = find_r_j(j);
		}
		ans[i-1] = ma;
	}
	for(int i = 1; i <= n; i++) printf("%d\n",ans[i]);
}

---

100分：$O(n(k+logn))$ 只需开几个数组直接维护即可 。

考虑反正每次也是最多枚举 $k$ 次左端点，我们可以定两个数组 $l_i,r_i$，表示第 $i$ 个最终有标记点的左边和右边的第一个有标记的点的下标。

初始化：

l[i] = i - 1, r[i] = i + 1;

然后每次倒序操作时，若此点的标记减为 $0$， 更新 ：

if(!num[p]) r[l[p]] = r[p], l[r[p]] = l[p];

其中 $p$ 为此次操作删去标记的点。

然后查询也就只需每次移动到 $l_j,r_j$ 即可，很显然每次操作移动复杂度为 $O(k)$

Code:

---

#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
    Xr = 0, G();
    while(Cr < '0' || Cr > '9') G();
    while(Cr >= '0' && Cr <= '9') Xr = (Xr<<3) + (Xr<<1) + (Cr & 15), G();
    return Xr;
}
#define MAX_N 1000005
int n, m, k;
int ans[MAX_N];
int num[MAX_N], pos[MAX_N], cnt;
int l[MAX_N], r[MAX_N];
int ma = -1, s, t;
struct node{
	int x, a;
} e[MAX_N];
int x[MAX_N], a[MAX_N];
map<int,int>mp;

bool comp(node x,node y){
	return x.x < y.x;
}

int main(){
    n = rd(), m = rd(), k = rd();
    for(int i = 1; i <= n; i++) {
    	e[i].x = rd(), e[i].a = rd();
    	x[i] = e[i].x, a[i] = e[i].a;
	}
	e[n+1].x = -1;
	sort(e+1,e+2+n,comp);
	for(int i = 1; i <= n + 1; i++) {
		if(e[i].x != pos[cnt]) pos[++cnt] = e[i].x;
		mp[e[i].x] = cnt;
	}
	pos[cnt+1] = m + 1;
	for(int i = 1; i <= n; i++) num[mp[x[i]]] += a[i];
	for(int i = 1; i <= cnt; i++) {
		s -= num[i];
		while(s + num[t+1] <= k && t < cnt) t++, s += num[t];
		ma = max(ma, pos[t+1] - pos[i] - 2);
		l[i] = i - 1, r[i] = i + 1;
	}
	ans[n] = ma;
	for(int i = n; i >= 2; i--) {
		int p = mp[x[i]];
		num[p] -= a[i];
		if(!num[p]) r[l[p]] = r[p], l[r[p]] = l[p];
		t = p;
		int j = p;
		s = num[t];
		while(j > 1 && s <= k) j = l[j], s += num[j];
		for(j; j < p; j = r[j]) {
			s -= num[j];		
			while(s + num[r[t]] <= k && r[t] <= cnt) t = r[t], s += num[t];
			ma = max(ma, pos[r[t]] - pos[j] - 2);
		}
		ans[i-1] = ma;
	}
	for(int i = 1; i <= n; i++) printf("%d\n",ans[i]);
}

---

总结：这是一道思维题，细节也不少，不过部分分非常足。

另：我是用 map 的，所以会比较慢， std 被吊打很正常/kk