自动搬运

查看原文

来自洛谷，原作者为

	qczrz6v4nhp6u Tell me, what scares you.

搬运于2025-08-24 23:06:45，当前版本为作者最后更新于2025-01-06 16:28:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

操作不弱于区间逆序对，考虑分块，设块长为 $B$。

对于散块对散块的贡献，直接把所有数加进去查一遍 BIT 即可，复杂度 $O(\sum mB\log n)$。

对于整块对其他的贡献，我们可以考虑预处理出 $f_{i,j}$，表示第 $i$ 个块与一个前缀 $j$ 产生的贡献，询问可以简单 $O(\frac{n}{B}(n+\sum m))$ 求出。但是空间爆炸了，逐块处理即可。

设 $M=\sum m$，取 $B=\sqrt{\frac{n^2}{M\log n}+\frac{n}{\log n}}$ 有最优复杂度 $O(\sqrt{(n^2M+nM^2)\log n})$，难以通过。

考虑优化 BIT 部分。对于查询，可以压位使得单次计算量减少大约 $6$ 次；对于清空，只要当前位置已经为 $0$ 就不用再往上跑了，清空复杂度优化为 $O(n)$。可以通过。

Code

加了上述几个优化后微调一下块长还是能比较轻松地跑过的。

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
// Fast IO
constexpr int N=5e5+5,B=553,S=B+5,T=N/B+5;
struct node{
	int l,r;
	node(){l=r=0;}
	node(int _l,int _r){l=_l,r=_r;}
};
int n,len,q,a[N];pii num[N];
int tot,pos[N];node rngB[T];ll ans[N];
int m;node rngQ[N],rng[N],rng_[N];
ull b[N];int c[N],mdf[N],cnt;
inline void upd(int x){
	mdf[++cnt]=x;
	static int y,z;y=x&63,z=x>>6;
	b[z]|=1ull<<y;
	for(++z;z<=len;z+=z&-z)++c[z];
}
inline int ask(int x){
	static int y,z;y=x&63,z=x>>6;
	static int res;res=__builtin_popcountll(b[z]&((y==63?0:1ull<<(y+1))-1));
	for(;z;z-=z&-z)res+=c[z];
	return res;
}
inline void clr(int x){
	static int z;z=x>>6;
	b[z]=0;
	for(++z;z<=n;z+=z&-z)
		if(c[z])c[z]=0;
		else break;
}
void clear(){
	for(int i=1;i<=cnt;i++)
		clr(mdf[i]);
	cnt=0;
}
int op[N],s[N];ll sum[N];
vector<node> vec[T];
int main(){
	cin>>n>>q;len=(n>>6)+1;
	for(int i=1;i<=n;i++)cin>>a[i],num[i]=make_pair(a[i],n-i+1);
	sort(num+1,num+n+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(num+1,num+n+1,make_pair(a[i],n-i+1))-num;
	while(rngB[tot].r<n){
		++tot;
		rngB[tot]=node(rngB[tot-1].r+1,rngB[tot-1].r+B);
	}
	rngB[tot].r=n;
	for(int i=1;i<=tot;i++){
		static int l,r;l=rngB[i].l,r=rngB[i].r;
		for(int j=l;j<=r;j++)
			pos[j]=i;
	}
	for(int i=1;i<=q;i++){
		op[i]=-1;
		int mi;cin>>mi;
		rngQ[i]=node(m+1,m+mi);
		while(mi--){
			++m,cin>>rng[m].l>>rng[m].r;
			static int _l,_r,_x,_y,_L,_R;
			_l=rng[m].l,_r=rng[m].r,_x=pos[_l],_y=pos[_r],_L=rngB[_y].l,_R=rngB[_x].r;
			if(_y-_x<=1){
				for(int k=_l;k<=_r;k++)ans[i]+=ask(a[k]-1);
				for(int k=_l;k<=_r;k++)upd(a[k]);
			}
			else{
				vec[_x+1].emplace_back(i,m);
				vec[_y].emplace_back(-i,m);
				rng_[m]=node(_R+1,_L);
				for(int k=_l;k<=_R;k++)ans[i]+=ask(a[k]-1);
				for(int k=_L;k<=_r;k++)ans[i]+=ask(a[k]-1);
				for(int k=_l;k<=_R;k++)upd(a[k]);
				for(int k=_L;k<=_r;k++)upd(a[k]);
			}
		}
		clear();
	}
	for(int u=1;u<=tot;u++){
		static int _L,_R,_sum;
		_L=rngB[u].l,_R=rngB[u].r,_sum=_R-_L+1;
		for(int i=_L;i<=_R;i++)++s[a[i]];
		for(int i=1;i<=n;i++)s[i]+=s[i-1];
		sum[_L]=0;for(int i=_L-1;i>=1;i--)sum[i]=sum[i+1]+_sum-s[a[i]];
		sum[_R]=0;for(int i=_R+1;i<=n;i++)sum[i]=sum[i-1]+s[a[i]-1];
		for(auto &o:vec[u]){
			if(o.l>0)op[o.l]=o.r;
			else op[-o.l]=-1;
		}
		for(int o=1;o<=q;o++){
			if(!~op[o])continue;
			static int from,p,to;from=rngQ[o].l,p=op[o],to=rngQ[o].r;
			for(int i=from;i<p;++i){
				ans[o]+=sum[rng[i].l]-sum[rng[i].r+1];
				ans[o]-=sum[rng_[i].l]-sum[rng_[i].r];
			}
			for(int i=p+1;i<=to;++i)
				ans[o]+=sum[rng[i].r]-sum[rng[i].l-1];
		}
		for(int i=1;i<=n;i++)s[i]=0;
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}