自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:30:14，当前版本为作者最后更新于2021-02-23 18:40:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

如果数据水，敬请谅解，也希望提供强数据。
如果有时间复杂度更优秀的做法，请写题解，我会感激的。
先看部分分吧。

10pts

每个点开一个堆，然后就是常规操作了。

20pts

只有添加，没有删除，相当于区间取 max，区间 max。那就意味着我们可以用线段树维护。

40pts

发现单点删除最大值用线段树不太好操作，也不好进行标记下放和信息。上传我们考虑暴力一点，用分块维护信息，每个块开一个堆代表整块都被插入的东西，每个点也要开一个堆，然后开一个 maxx 数组代表块内最大值。
插入的时候我们边角暴力，中间插入整块的堆，然后更新 maxx。
删除的时候我们比较它自己的堆和它所属的块的堆。如果他自己的堆的堆顶更大，则直接删除，然后更新 maxx。如果它所属的堆更大，则删除掉之后，把它塞入块内其余点的堆里，因为它们还存在这个值，所以不用更新 maxx。
查询的时候我们边角暴力询问单点堆顶和整块堆顶，中间的整块直接查询 maxx，就解决了。
时间复杂度在块长为 $\sqrt{n}$ 时复杂度较优，为 $O(n\sqrt{n}logn)$。代码如下，比较短。本来这是这个题的标算，但是……

60pts(1)

既然要 polylog，首先堆的一个 log 很难避免，我们剩下的那个 log 就可以往线段树上想。
考虑使用标记永久化，这个永久化的标记形成了一个堆。我们再在线段树里维护一个 maxx，代表这个区间的最大值。这样，插入和查询操作就很好处理了。
现在我们考虑删除，由于是单点，首先我们找到这个最大值，然后在线段树里找到这个标记。我们需要把这个标记移除，并将其加入这个区间的其它点内，你可以再写一个 pushdown，也可以直接跑两遍插入（这样常数要大一点）。
时间复杂度 $O(nlog^2n)$，代码挺好写的。
我终于知道 lxl 为什么直接拒了。

60pts(2)

如果你的分块可以支持区间修改，则可以通过 60 分的数据。

100pts

我们考虑怎么优化 60 分的线段树，使它支持区间修改。
我们可以想到先找到这一段的最大值是哪一个，然后把标记从这个区间上面移除。这样做看起来时间复杂度是不对的，但我们可以进行剪枝。如果这一个区间的最大值比我们需要删去的小，我们就不去了。
乍一看复杂度还是不对，但我们可以分析一下。我们时间复杂度相当于对于每一个最大值的连续区间，把它在线段树上分成不超过 log 个区间。由于我们插入的时候是整段一起插入同一个值，所以插入均摊下来会产生 $mlogn$ 个线段树区间。
我们每删除一个产生的线段树区间，最多花 $logn$ 时间递归下去删除标记。所以删除的时间复杂度为均摊 $O(mlog^2n)$ （堆的复杂度和向下递归的复杂度是并列的）由于插入和查询的复杂度也是这个量级，所以总复杂度 $O((n+m)log^2n)$。
代码十分好写，不到 2k。如果哪里没叙述清楚，请向我提出。

#include <bits/stdc++.h>
#define lc id<<1
#define rc id<<1|1
using namespace std;
const int maxn=2e5+5;
struct tree {
	int l,r,mid,maxx;
	priority_queue<int> q;
} t[maxn*4];
int n,m;
void build(int id,int l,int r) {
	t[id]=(tree) {
		l,r,(l+r)/2,-1
	};
	t[id].q.push(-1);
	if(l==r)return;
	int mid=(l+r)/2;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void addtag(int id,int v) {
	t[id].q.push(v);
	t[id].maxx=max(t[id].maxx,v);
}
void pushup(int id) {
	t[id].maxx=max(max(t[lc].maxx,t[rc].maxx),t[id].q.top());
}
void pushdown(int id,int l,int r,int k) {//把 k 这个标记往 l,r 之外区间插入
	if(t[id].l>=l&&t[id].r<=r) return;
	if(l>t[id].mid)addtag(lc,k),pushdown(rc,l,r,k);
	else if(r<=t[id].mid)addtag(rc,k),pushdown(lc,l,r,k);
	else pushdown(lc,l,r,k),pushdown(rc,l,r,k);
	pushup(id);
}
void add(int id,int l,int r,int v) {
	if(t[id].l>=l&&t[id].r<=r) {
		addtag(id,v);
		return;
	}
	if(l<=t[id].mid)add(lc,l,r,v);
	if(r>t[id].mid)add(rc,l,r,v);
	pushup(id);
}
void del(int id,int l,int r,int k) {
	if(t[id].l>=l&&t[id].r<=r&&t[id].maxx<k)return;//核心：剪枝
	if(t[id].q.top()==k) {
		t[id].q.pop();
		pushdown(id,l,r,k);
		if(t[id].l==t[id].r)t[id].maxx=t[id].q.top();
		else pushup(id);
		return;//由于只pop一个，这里弄完标记就走了
	}
	if(l<=t[id].mid)del(lc,l,r,k);
	if(r>t[id].mid)del(rc,l,r,k);
	pushup(id);
}
int ask(int id,int l,int r) {
	if(t[id].l>=l&&t[id].r<=r) {
		return t[id].maxx;
	}
	int ans=t[id].q.top();
	if(l<=t[id].mid)ans=max(ans,ask(lc,l,r));
	if(r>t[id].mid)ans=max(ans,ask(rc,l,r));
	return ans;
}
int main() {
	t[0].q.push(-1),t[0].maxx=-1;
	int op,x,y,z;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(register int i=1; i<=m; i++) {
		scanf("%d%d%d",&op,&x,&y);
		switch(op) {
			case 1: {
				scanf("%d",&z);
				add(1,x,y,z);
				break;
			}
			case 2: {
				z=ask(1,x,y);
				if(z!=-1)del(1,x,y,z);
				break;
			}
			case 3: {
				printf("%d\n",ask(1,x,y));
				break;
			}
		}
	}
	return 0;
}