自动搬运

查看原文

来自洛谷，原作者为

	BFqwq 青く广がった あの空のように、昙りなく笑えたら あなたに会いたい。

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

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

以下是正文

---

放一下本题的官方题解吧。

其实这个题写正解代码难度相当的高。为了防止空间不够用的现象，我把本题空间改成了 500MB（不过由于我使用了一些优化，所以我的空间其实小。

对于有一些暴力能够跑过本题的情况，其实出题人根本就没有想到有这样的暴力，不过还是在这里向大家道歉。

以下是本题的官方题解。

Subtask 1

考虑暴力修改，暴力查询逆序对，复杂度 $\operatorname O(n^3)$。

Subtask 2

将逆序对改用归并排序或权值树查询，复杂度 $\operatorname O(n^2\log n)$。

Subtask 3

由于修改长度是 $1$，直接考虑使用树套树维护动态逆序对。在修改时查询 $[1,l-1]$ 区间大于原数的和 $[r+1,n]$ 区间小于原数的数的个数并减去，然后对新数做类似的查询并加上。在查询逆序对时，可直接输出。复杂度 $\operatorname O(n\log^2 n )$

Subtask 4

显而易见，在值域缩小的同时，修改区间也随之缩小。

于是我们可以考虑对每个值建一个树状数组，如果对应位置有这个值，则树状数组该位置的值就是 $1$，否则是 $0$。

在修改时，对 $[1,l-1]$ 区间的每个值分别做一个查询并做一个后缀和，对 $[r+1,n]$ 区间的每个值也做一个查询并做一个前缀和，然后对每个值，我们就可以用 $\operatorname O(1)$ 的复杂度修改并维护了。

注意不要忘了清楚修改区间内部对逆序对的贡献，这部分可以暴力。

由于值域可以认为是 $\operatorname O(\log n)$，故此处的复杂度为 $\operatorname O(n\log^2 n)$。

Subtask 5

由于第两次操作一就会重置一次，我们可以考虑直接用数学方法计算出修改的贡献。

对于奇数次操作，直接重置，逆序对清零。

对于偶数次操作，分为 $l<x$ 和 $l>x$ 两种。

如果 $l<x$，则我们修改完后的该区间的值为 $[x,x+r-l]$，易知 $[l,r]$ 与 $[x,x+r-l]$ 的交集为 $[x,l-1]$。

则对于值在 $[x,l-1]$ 区间的数，对逆序对的贡献显然是一个公差为 $-1$ 的等差数列，我们可以直接对此进行求和。

而对于值在 $[l,x-r+l]$ 区间的数，显然对逆序对没有贡献，直接忽略。

如果 $l>r$ 则类似讨论。

于是，我们就可以 $\operatorname O(1)$ 完成对逆序对个数的计数（注意此时我们并不需要直接修改这个数列），复杂度 $\operatorname O(n)$。

Subtask 6

考虑颜色段均摊。

这是一种类似于珂朵莉树的 trick（事实上这就是珂朵莉树的推平操作），复杂度为均摊 $\operatorname O(n\times k)$，其中 $k$ 为单次修改的复杂度。

对于一个区间染色的操作，我们可以直接将一个区间维护为一个点，并且将他装入在 $set$ 或其他容器中。

在修改时，我们在 $set$ 中找到我们需要清除的所有区间（如果边界被包含则将边界所在的区间断开变成两个区间），并暴力将它们逐个清除，再插入新的区间。

为什么这样做的复杂度是正确的呢？我们可以来证明一下。

最初的时候，每个数单独构成一个区间，所以一共有 $n$ 个区间。

而每次操作的时候，我们增加的区间包括断开左右边界区间时增加的两个区间，以及插入的新区间。

这样一来，整个操作过程中区间的总个数就是 $n+3m$ 个。

而显然一个区间最多被插入一次，删除一次，且 $nm$ 同级，所以复杂度为均摊 $\operatorname O(n\times k)$。

本题中的操作一并不是颜色段均摊，但显然可以用类似的方法，均摊 $\operatorname O(n\times k)$ 完成修改。

但我们在修改的同时，还需要再维护一个动态逆序对，于是考虑令 $k=\log^2n$，使用树套树修改

考虑插入一个新段对逆序对的贡献（删除就将贡献减去）。

假设这个区间是 $[l,r]$，这个区间的值的范围是 $[x,y](r-l=y-x)$。

那么我们大致可以其他的数分为以下几类：

1. 位于 $[1,l-1]$ 区间且值小于 $x$ 的数。这类数没有贡献，直接无视。
2. 位于 $[r+1,n]$ 区间且值大于 $y$ 的数。这类数同样没有贡献，直接无视。
3. 位于 $[1,l-1]$ 区间且值大于 $y$ 的数。这类数对区间内的所有数都有贡献，只需统计个数并乘以 $r-l+1$。
4. 位于 $[r+1,n]$ 区间且值小于 $x$ 的数。这类数同样对区间内的所有数都有贡献，处理方法同上。
5. 位于 $[1,l-1]$ 区间且值位于 $[x,y]$ 之间的数。注意到，对于值为 $t(t\in[x,y])$ 的数，它对这个区间的贡献为 $t-x$，因为这个区间内前 $t-x$ 个数的值会小于 $t-x$。于是我们可以对权值维护区间内的个数以及区间和，也就是一个范围内值在某个区间的数有几个，以及这几个数加起来是多少。然后用和减去个数乘以 $x$ 就是我们所要的结果。
6. 位于 $[r+1,n]$ 区间且值位于 $[x,y]$ 之间的数。处理方式类似于第五类数。

这样一来，我们就在修改的同时完成了对逆序对的维护，而复杂度没有发生变化。

于是最终的复杂度就是 $\operatorname O(n\log^2 n)$。

总结

本题的难度并不高，没有涉及到很复杂的维护方法，也没有涉及到很高级的数据结构，主要还是对一些基本技巧的灵活应用。另外，有一个颜色段均摊的操作值得大家掌握。

另外，本题可能出现空间不够用的情况。在本题的 std 代码中，树套树中的内层线段树使用的是标记永久化的线段树，这也大大节省了本题的空间。出题人没有测试过下放的空间，但看到部分其他用户的提交记录，感觉下放的确空间大了好多。

贴一份代码吧，供大家参考。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
char cr[200];int ttt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    while(x) cr[++ttt]=x%10+'0',x/=10;
    while(ttt) putchar(cr[ttt--]);
    putchar(k);
}
inline void printl(register ll x,register char k='\n') {
    if(!x) putchar('0');
    while(x) cr[++ttt]=x%10+'0',x/=10;
    while(ttt) putchar(cr[ttt--]);
    putchar(k);
}
const int maxn=52233;
const int len=30000;
struct seg{
	int v,ls,rs,tag;
	ll sum;
}t[maxn*160];
struct ask{
	int v;
	ll sum;
	friend ask operator +(ask a,ask b){
		return (ask){a.v+b.v,a.sum+b.sum};
	}
	friend ask operator -(ask a,ask b){
		return (ask){a.v-b.v,a.sum-b.sum};
	}
};
int rt[maxn],m,n,tot,st[maxn*128],top,tem[maxn][2],cnt[2];
int nnd(){
	if(top) return st[top--];
	return ++tot;
}
int del(int o){
	if(t[o].tag||t[o].sum||t[o].v||t[o].ls||t[o].rs) return o;
	st[++top]=o;
	return 0;
}
inline void change(int &o,register int l,register int r,register int ql,register int qr,register int v){
	if(!o) o=nnd();
	if(ql<=l&&r<=qr){
		t[o].v+=v*(r-l+1);
		t[o].sum+=v*(l+r)*(r-l+1)/2;
		t[o].tag+=v;
		o=del(o);
		return;
	}
	int mid=l+r>>1;
	if(ql<=mid) change(t[o].ls,l,mid,ql,qr,v);
	if(qr>mid) change(t[o].rs,mid+1,r,ql,qr,v);
	t[o].v=t[t[o].ls].v+t[t[o].rs].v+t[o].tag*(r-l+1);
	t[o].sum=t[t[o].ls].sum+t[t[o].rs].sum+(ll)t[o].tag*(l+r)*(r-l+1)/2;
	o=del(o);
}
inline void add(register int x,register int ql,register int qr,register int v){
	for(register int i=x;i<=n;i+=(i&-i)) 
		change(rt[i],1,len,ql,qr,v);
}
inline ask query(register int o,register int l,register int r,register int ql,register int qr,register ll tag){
	if(ql<=l&&r<=qr){
		ask res=(ask){0,0};
		res.v=t[o].v+tag*(r-l+1);
		res.sum=t[o].sum+tag*(r+l)*(r-l+1)/2;
		return res;
	}
	int mid=l+r>>1;ask res=(ask){0,0};
	if(ql<=mid) res=res+query(t[o].ls,l,mid,ql,qr,tag+t[o].tag);
	if(qr>mid) res=res+query(t[o].rs,mid+1,r,ql,qr,tag+t[o].tag);
	return res;
}
ask find(register int l,register int r,register int ql,register int qr){
	if(ql>qr||l>r) return (ask){0,0};
	if(l>r) return (ask){0,0};
	ask res=(ask){0,0};
	for(register int i=r;i;i-=(i&-i)) 
		res=res+query(rt[i],1,len,ql,qr,0);
	for(register int i=l-1;i;i-=(i&-i)) 
		res=res-query(rt[i],1,len,ql,qr,0);
	return res;
}
struct node{
	int l,r,v;
	friend bool operator <(node a,node b){
		return a.l<b.l;
	}
}tmp1,tmp2,tmp;
set<node> s;
set<node>::iterator it,it1,it2;
ll ans;
inline void split(register int x){
	it=s.upper_bound((node){x,0,0});it--;
	if(it->l==x) return;
	tmp1=(node){it->l,x-1,it->v};
	tmp2=(node){x,it->r,it->v+x-it->l};
	add(it->l,it->v+x-it->l,it->v+it->r-it->l,-1);
	add(x,it->v+x-it->l,it->v+it->r-it->l,1);
	s.erase(*it);
	s.insert(tmp1);s.insert(tmp2);
}
inline void update(register int l,register int r,register int x){
	if(l!=1) split(l);
	if(r!=n) split(r+1);
	while(1){
		tmp=*s.lower_bound((node){l,0,0});
		if(tmp.l==r+1) break;
		int tl=tmp.l,tr=tmp.r,vl=tmp.v,vr=tmp.v+tmp.r-tmp.l;
		add(tl,vl,vr,-1);
		ans-=find(1,tl-1,vr+1,len).v*(tr-tl+1)+find(tr+1,n,1,vl-1).v*(tr-tl+1);
		ask res=find(1,tl-1,vl,vr);
		ans-=res.sum-res.v*vl;
		res=find(tr+1,n,vl,vr);
		ans-=res.v*vr-res.sum;
		s.erase(tmp);
	}
	s.insert((node){l,r,x});
	add(l,x,x+r-l,1);
	register int vr=r-l+x,vl=x;
	ans+=find(1,l-1,vr+1,len).v*(r-l+1)+find(r+1,n,1,vl-1).v*(r-l+1);
	ask res=find(1,l-1,vl,vr);
	ans+=res.sum-res.v*vl;
	res=find(r+1,n,vl,vr);
	ans+=res.v*vr-res.sum;
}
signed main(){
	n=read();m=read();
	for(register int i=1;i<=n;i++){
		int x=read();
		s.insert((node){i,i,x});
		add(i,x,x,1);
		ans+=find(1,i-1,x+1,len).v;
	}
	s.insert((node){n+1,0,0});
	for(register int i=1;i<=m;i++){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),x=read();
			update(l,r,x);
		}
		if(opt==2) printl(ans);
	}
	return 0;
}