#树状数组#[ssloj 1474] 简单计算题 [jzoj] Tiny Counting

Title

Solution

假如 $a,b,c,d$可以相等，那么 $ans$是顺序对和逆序对的乘积。可以减去不合法的的方案数。
$ls,lb,rs,rb$指的是比分别左边比 $i$小的，大的，右边比 $i$小的，大的的数量。
排除以下四种情况：

• $a=c$
• $S_d<S_{a=c}<S_b$
• $(a=c)<b,d$
• $rs*rb$

• $a=d$
• $S_c>S_{a=d}<S_b$
• $c<(a=d)<b$
• $lb*rb$

• $b=c$
• $S_a<S_{b=c}>S_d$
• $a<(a=c)<d$
• $ls*rs$

• $b=d$
• $S_a<S_{b=d}<S_c$
• $a,c<(b=d)$
• $lb*ls$

以第一和第二种情况举例：
第一种

第二种

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define rep(i,x,y) for(register ll i=x;i<=y;i++)
using namespace std; 
ll n,ans,t[100500],a[100500],b[100500],p,q,ls[100005],lb[100005],rs[100005],rb[100005]; 
inline void add(ll x,ll y){for(;x<=n;x+=x&(-x)) b[x]+=y;}
inline ll ask(ll x){ll q=0; for(;x;x-=x&(-x)) q+=b[x]; return q;}
int main(){scanf("%lld",&n); rep(i,1,n) scanf("%lld",&a[i]),t[i]=a[i]; sort(t+1,t+n+1); int m=unique(t+1,t+n+1)-t-1; rep(i,1,n) a[i]=lower_bound(t+1,t+m+1,a[i])-t; rep(i,1,n){ls[i]=ask(a[i]-1); lb[i]=ask(n)-ask(a[i]); p+=ls[i]; add(a[i],1); }memset(b,0,sizeof(b)); for(int i=n;i>=1;i--){rs[i]=ask(a[i]-1); rb[i]=ask(n)-ask(a[i]); q+=rs[i]; add(a[i],1); }rep(i,1,n) ans=p*q; rep(i,1,n) ans-=ls[i]*rs[i]+rs[i]*rb[i]+rb[i]*lb[i]+lb[i]*ls[i]; printf("%lld",ans); return 0; 	
}