hdu_5792_World is Exploding(树状数组+逆序对)

题目链接：hdu_5792_World is Exploding

题意：

给你一个数列，让你找有多少个（a,b,c,d）满足a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,A_a<A_b,A_c>A_d.

题解：

如果abcd可以相等，那么就是所有的顺序对和逆序对相乘，但这里要不相等，所以我们减去相等的情况就行。

要满足Aa<Ab,Ac>Ad，考虑其中一个数A_i 然后我们可以发现，建立在A_i的顺序对和逆序上，bd不会相等，

所以我们只需要找出每一个A_i前后顺序对和逆序对，然后对应交叉相乘，就是a=c的情况，然后总答案减去就行

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define F(i,a,b) for(int i=a;i<=b;i++)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int N=5E4+7;
 8 int a[N],n,idx[N],len,tr[N],t1[N],t2[N],t3[N],t4[N];
 9 
10 inline void add(int x,int c){while(x<=n)tr[x]+=c,x+=x&-x;}
11 inline int ask(int x){int an=0;while(x)an+=tr[x],x-=x&-x;return an;}
12 
13 int getid(int x){return lower_bound(idx+1,idx+1+len,x)-idx;}
14 
15 int main()
16 {
17     while(~scanf("%d",&n))
18     {
19         F(i,1,n)scanf("%d",a+i),idx[i]=a[i],tr[i]=0;
20         sort(idx+1,idx+1+n),len=1;
21         F(i,2,n)if(idx[i]!=idx[len])idx[++len]=idx[i];
22         ll zheng=0,ni=0,ans;
23         F(i,1,n)
24         {
25             int x=getid(a[i]);
26             int now=ask(x-1);
27             zheng+=now,t1[i]=now,t2[i]=ask(n)-ask(x),ni+=t2[i];
28             add(x,1);
29         }
30         F(i,1,n)tr[i]=0;
31         for(int i=n;i>=1;i--)
32         {
33             int x=getid(a[i]);
34             int now=ask(x-1);
35             t4[i]=now,t3[i]=ask(n)-ask(x);
36             add(x,1);
37         }
38         ans=zheng*ni;
39         F(i,1,n)ans-=t1[i]*t2[i]+t1[i]*t4[i]+t3[i]*t2[i]+t3[i]*t4[i];
40         printf("%lld
",ans);
41     }
42     return 0;
43 }

View Code