正题

---

题目大意

一个序列$S$，求有多少个互不相同的4元组$(a,b,c,d)$使得$$a<b且S_a<S_b$$
$$c<b且S_c>S_d$$

---

解题思路

若可以重复其实答案就是逆序对个数乘上正序对个数。

然后我们考虑将重复的去掉
这里定义$u{p}_1,dow{n}_1$为左边大于/小于该数的个数，$up2,down2$为右边大于/小于该数的个数。
若$a=c$，那么有$S_d<S_{a=c}<S_b$，且$(a=c)<b,d$，为$up2\ast down2$
若$a=d$，那么有$S_c>S_{a=d}<S_b$，且$c<(a=d)<b$，为$up1\ast up2$
若$b=c$，那么有$S_a<S_{b=c}>S_d$，且$a<(b=d)<d$，为$down1\ast down2$
若$b=d$，那么有$S_a<S_{b=d}<S_c$，且$a,c<(b=d)$，为$up1\ast down1$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) #define ll long long using namespace std; const ll N=1e5+100; ll n,a[N],c[N],s1,s2,z,m; struct Tree_array{ll t[N];void Clear(){memset(t,0,sizeof(t));}void Change(ll x,ll z){while(x<=m){t[x]+=z;x+=lowbit(x);}}ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);} return ans;} }T1,T2; int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),c[i]=a[i];sort(c+1,c+1+n);m=unique(c+1,c+1+n)-c-1;for(ll i=1;i<=n;i++){a[i]=lower_bound(c+1,c+1+m,a[i])-c;T2.Change(a[i],1);}for(ll i=1;i<=n;i++){ll down1=T1.Ask(a[i]-1),up1=T1.Ask(m)-T1.Ask(a[i]);ll down2=T2.Ask(a[i]-1),up2=T2.Ask(m)-T2.Ask(a[i]);s1+=down1;s2+=down2;z+=up2*down2+up1*up2+down1*down2+up1*down1;T1.Change(a[i],1);T2.Change(a[i],-1);}printf("%lld",s1*s2-z); }

总结

以上是生活随笔为你收集整理的jzoj6342-[NOIP2019模拟2019.9.7]Tiny Counting【树状数组,容斥】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。