如果这是世界末日的前一晚，
这是我的回答。
#include <bits/stdc++.h> using namespace std; int main(){ cout<<"Hello, the end."<<endl; }
最后一场了，不写写总结就没了。
T1，先打一个暴力，然后发现可以简单容斥，就$\Theta(N \log N)$
T2不会，一个搜索，还感觉过不了最小点。
T3不会，打了一个$1$分算法（滑稽）
但是想了半天T3……
T2的剪枝有点难打……
就会T1，于是写个。
首先我们发现可以把四元组拆成两个二元组。
那么有$<a,b>,S_a < S_b$和$<c,d>,S_c > S_d$
于是直接用树状数组维护，算出$i$前严格比$S_i$大和小的数的数量就行。
但是有个问题，$a,b,c,d$各不相同，那么就需要算出有那些非法。
于是有
四种情况，同样用树状数组算出并容斥就行了！
//a
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 111111
#define LL long long
using namespace std;
int nn,vn;
int arr[N],val[N];
int pre[N];
LL befs[N],befb[N],afts[N],aftb[N];
LL ans;
inline int fvind(int va){
return lower_bound(val+1,val+vn+1,va)-val;
}
inline int lowbit(int x){
return x&(-x);
}
void add(int pos,int v){
while(pos<=vn+10){
pre[pos]+=v;
pos+=lowbit(pos);
}
}
int query(int pos){
int res=0;
while(pos){
res+=pre[pos];
pos-=lowbit(pos);
}
return res;
}
int main(){
#ifndef LOCAL
freopen("a.in" ,"r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&nn);
for(int i=1;i<=nn;i++){
scanf("%d",arr+i);
val[i]=arr[i];
}
sort(val+1,val+nn+1);
vn=unique(val+1,val+nn+1)-val-1;
for(int i=1;i<=nn;i++)
arr[i]=fvind(arr[i]);
/* for(int i=1;i<=nn;i++)
cout<<arr[i]<<" ";
cout<<endl;*/
for(int i=1;i<=nn;i++){
befs[i]=query(arr[i]-1);
befb[i]=i-1-query(arr[i]);
add(arr[i],1);
}
memset(pre,0,sizeof pre);
for(int i=nn;i>=1;i--){
afts[i]=query(arr[i]-1);
aftb[i]=nn-i-query(arr[i]);
add(arr[i],1);
}
/* cout<<"Befs:";
for(int i=1;i<=nn;i++)
cout<<befs[i]<<" ";
cout<<endl<<"Befb:";
for(int i=1;i<=nn;i++)
cout<<befb[i]<<" ";
cout<<endl<<"Afts:";
for(int i=1;i<=nn;i++)
cout<<afts[i]<<" ";
cout<<endl<<"Aftb:";
for(int i=1;i<=nn;i++)
cout<<aftb[i]<<" ";
cout<<endl;
*/
LL suma=0,sumb=0;
for(int i=1;i<=nn;i++){
suma+=1ll*befs[i];
sumb+=1ll*afts[i];
}
ans=suma*sumb;
for(int i=1;i<=nn;i++){
ans-=1ll*befb[i]*aftb[i];
ans-=1ll*befs[i]*afts[i];
ans-=1ll*befs[i]*befb[i];
ans-=1ll*afts[i]*aftb[i];
}
cout<<ans<<endl;
}
"Hello CSP-S,Hello AFO"
原文：https://www.cnblogs.com/kalginamiemeng/p/Exam20191114.html