自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:55:10，当前版本为作者最后更新于2024-10-01 21:27:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解

Ynoi 的题就必须是紫黑是吧，这题蓝顶多了。这也是我第一篇 Ynoi 的题解。

先赌一把，看到数据范围为 $n,m\le 5\times 10^5$，时间限制为 3s，可以猜到是 $O(n\sqrt{n})$ 莫队。下面分类讨论 add 对答案的贡献，del 即为 add 的逆操作。

若 add 的数下标为 $r+1$，则对答案的贡献为：

$$\sum_{i=l}^{r}[a_{r+1}=a_i]\left(\sum_{j=1}^{r}[a_{r+1}>a_j]-\sum_{j=1}^{i-1}[a_i>a_j]\right) $$

若 add 的数下标为 $l-1$，则对答案的贡献为：

$$\sum_{i=l}^{r}[a_{l-1}=a_i]\left(\sum_{j=1}^{i-1}[a_{i}>a_j]-\sum_{j=1}^{l-2}[a_{l-1}>a_j]\right) $$

对于 $u\in[1,n]$ 使用树状数组预处理 $\displaystyle\sum_{i=1}^{u-1}[a_u>a_i]$ 即可。

其实到这里已经结束了，但是如果想让代码短一点的话，其实上面二个式子是可以合并的，这里不妨设 add 的数下标为 $p\in\{l-1,r+1\}$：

$$\sum_{i=l}^{r}[a_p=a_i]\left|~\sum_{j=1}^{i-1}[a_{i}>a_j]-\sum_{j=1}^{p-1}[a_p>a_j]~\right| $$

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
ll now,ans[maxn],sum[maxn];
int a[maxn],pre[maxn],cnt[maxn];
int n,m,len,tree[maxn];
inline void update(int p,int d){
	while(p<=n) tree[p]+=d,p+=(p&-p);
}
inline int query(int p){
	int res=0;
	while(p>=1) res+=tree[p],p-=(p&-p);
	return res;
}
inline void add(int i){
	now+=abs(1ll*pre[i]*cnt[a[i]]-sum[a[i]]);
	cnt[a[i]]++; sum[a[i]]+=pre[i];
	return; 
}
inline void del(int i){
	sum[a[i]]-=pre[i]; cnt[a[i]]--;
	now-=abs(1ll*pre[i]*cnt[a[i]]-sum[a[i]]);
	return;
}
struct node{int l,r,id;}qry[maxn];
inline bool comp(node u,node v){
	return u.l/len!=v.l/len?u.l<v.l:u.r<v.r;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;  
	len=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) pre[i]=query(a[i]-1),update(a[i],1);
	for(int i=1;i<=m;i++) cin>>qry[i].l>>qry[i].r,qry[i].id=i;
	sort(qry+1,qry+1+m,comp);
	int l=1,r=0; 
	for(int i=1;i<=m;i++){
		while(l>qry[i].l) add(--l);
		while(r<qry[i].r) add(++r);
		while(l<qry[i].l) del(l++);
		while(r>qry[i].r) del(r--);
		ans[qry[i].id]=now;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}