洛谷 AT_arc168_a [ARC168A] ＜Inversion＞ 题解

逆序对

在一个没有重复数值的序列 $a$ 之中，如果存在一组下标 $i$ 和 $j$ 使得 $i<j$，那么当 $a_i>a_j$ 时，就称 $a_i$ 和 $a_j$ 是序列 $a$ 中的一组逆序对。

思路

显然，对于连续的 $x$ 个 >，会产生 $\sum _{i=1}^{x}i$ 个逆序对，利用高斯求和转换成 $\frac{x\times (x+1)}{2}$。

所以只要从左至右一步步判断 $S$ 的字符，如果其是：

• >：累加 > 的个数（为方便表示，设其为 $x$）。
• <：将答案累加 $\frac{x\times (x+1)}{2}$ 并将 $x$ 清 $0$。

最后输出答案即可。

Code

#include<iostream>
#define int long long//不开long long见祖宗
using namespace std;
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,sum=0,ans=0;
	string str;
	cin>>n>>str,--n;
	for(int i=0;i<n;++i) {
		if(str[i]=='>') ++sum;//累加
		else ans+=(sum+1)*sum/2,sum=0;//累加答案并清0
	}
	cout<<ans+(sum+1)*sum/2;//还要把最后的累加起来
	return 0;
}