NKOJ 3697 乒乓比赛

问题描述

n个乒乓球爱好者站成一排，从左往右编号1到n。他们要组织比赛切磋技术。每个人都有一个不同的技能值，编号i个人的技能值为ai。 每场比赛需要3个人：两名选手，一名裁判。要求作为裁判的那一个乒乓球爱好者所站的位置必须在两名选手的之间，并且技能值也在两名选手的之间。 问一共能组织多少场不同的比赛。

---

输入格式

第一行，一个整数n。 第二行，n个空格间隔的整数，按照从左往右的顺序给出了每个乒乓球爱好者的能力值ai。

---

输出格式

一行，一个整数，表示所求结果

---

样例输入1

3 1 2 3

---

样例输出1

1

---

样例输入2

5 9 1 4 3 6

---

样例输出2

3

---

样例输入3

7 7 10 5 4 8 1 6

---

样例输出3

9

---

数据范围

3<=n<=50000 1<=ai<=200000

---

这道题很水啊==没必要做太多的解释，正向反向跑一遍逆序对然后统计一下， ci记的是在该范围内比ai小的数，最后可以得出一个方程算就行了

#include<iostream> #include<cstring> #define MEM memset(c,0,sizeof(c)) #define lowbit(x) x&(-x) using namespace std; long long ans=0,n; long long s1[200005],s2[200005]; long long a[50005],c[200005]; int getsum(int x) { int sum=0; for(int i=x;i>0;i-=lowbit(i))sum+=c[i]; return sum; } void modify(int x,int y) { for(int i=x;i<=200000;i+=lowbit(i))c[i]+=y; } int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; MEM; for(int i=1;i<=n;i++) { modify(a[i],1); s1[i]=getsum(a[i]-1); } MEM; for(int i=n;i>=1;i--) { modify(a[i],1); s2[i]=getsum(a[i]-1); } for(int i=2;i<=n;i++) ans+=(n-i-s2[i])*s1[i]+(i-s1[i]-1)*s2[i]; cout<<ans; }