自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

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

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

以下是正文

题目简述

• 给定长度为 $n$ 的数列 $a$。
• 求有多少对 $(l,r)$ 使得 ：

题目分析

假设 $s_i$ 为前缀和，本题即求有多少对 $(l,r)$ 使得：

这显然是正序对个数，直接归并求解即可（如果不会逆序对的同学可以点这里）。

代码

#include<iostream>
using namespace std;
#define ll long long
const int MAXN=1e5+5;
int n,a;
int s[MAXN];
int t[MAXN];
ll ans=0;
void msort(int l,int r){
	if(l==r)
		return;
	int mid=(l+r)/2;
	msort(l,mid);
	msort(mid+1,r);
	int p=l,q=mid+1,k=l;
	while(p<=mid&&q<=r){
		if(s[p]>=s[q])
			t[k++]=s[q++]; 
		else
			t[k++]=s[p++],ans+=r-q+1;
	}
	while(p<=mid)
		t[k++]=s[p++];
	while(q<=r)
		t[k++]=s[q++];
	for(int i=l;i<=r;i++)
		s[i]=t[i];
	return; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		s[i]=s[i-1]+a;
	}
	msort(0,n);
	//for(int i=1;i<=n;i++)
	//	cout<<s[i]<<" ";
	cout<<ans;
}