HDU5792 树状数组

http://acm.hdu.edu.cn/showproblem.php?pid=5792

题意：给一组序列，从中找出一个四元组，使四个元素下标两两不同，且a<ｂ，ｃ＜ｄ有X_a< X_b , X_c > X_d。问一共有多少组满足要求的四元组。

思路：使用树状数组保存左边小于，左边大于，右边小于，右边大于当前位的数的个数。保存逆序对，顺序对组数。在逆序对X顺序对的结果中存在b,c为同一数，a,d为同一数，a,c为同一数，d,b为同一数的情况，将这些情况数量减去得到答案。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 using namespace std;
  6 const int N = 50005;
  7 typedef long long LL;
  8 
  9 int tmp[N] , arr[N];
 10 int n,cnt; //cnt为离散后不同数的个数
 11 int ls[N],rs[N],rb[N],lb[N]; // ls：左边小于当前位的数的个数 ， rs：右边小于当前位的数的个数，lb：左边大于当前位的数的个数，rb：右边大于当前位的数的个数
 12 int tls[N],trs[N],trb[N],tlb[N]; // 树状数组
 13 LL ans,suml,sumb; //答案，逆序对个数，顺序对个数
 14 
 15 
 16 void init()
 17 {
 18     memset(tls,0,sizeof (tls));
 19     memset(trs,0,sizeof (trs));
 20     memset(tlb,0,sizeof (tlb));
 21     memset(trb,0,sizeof (trb));
 22     ans = suml = sumb = 0;
 23 }
 24 
 25 LL getl(int p,int *tr)
 26 {
 27     LL res = 0;
 28     while (p > 0)
 29     {
 30         res += (LL)tr[p];
 31         p -= (p&-p);
 32     }
 33     return res;
 34 }
 35 
 36 LL getr(int p,int *tr)
 37 {
 38     LL res = 0;
 39     while (p <= cnt)
 40     {
 41         res += (LL)tr[p];
 42         p += (p&-p);
 43     }
 44     return res;
 45 }
 46 
 47 void upl(int p,int *tr)
 48 {
 49     while (p<=cnt)
 50     {
 51         tr[p] += 1;
 52         p += (p&-p);
 53     }
 54 }
 55 
 56 void upr(int p,int *tr)
 57 {
 58     while (p > 0)
 59     {
 60         tr[p] += 1;
 61         p -= (p&-p);
 62     }
 63 }
 64 
 65 
 66 int main()
 67 {
 68     while (scanf("%d",&n)==1)
 69     {
 70         init();
 71         for (int i=0;i<n;i++)
 72         {
 73             scanf("%d",&arr[i]);
 74         }
 75         tmp[0] = arr[0];
 76         cnt = 1;
 77         for (int i=1;i<n;i++)
 78         {
 79             if (arr[i]!=tmp[cnt-1])
 80                 tmp[cnt++] = arr[i]; //去重
 81         }
 82         sort(tmp,tmp+cnt);
 83         for (int i=0;i<n;i++)
 84         {
 85             arr[i] = lower_bound(tmp,tmp+cnt,arr[i]) - tmp + 1; //离散化
 86             ls[i] = getl(arr[i]-1,tls); lb[i] = getr(arr[i]+1,tlb);
 87             upl(arr[i],tls); upr(arr[i],tlb);
 88             suml += ls[i]; sumb += lb[i];
 89         }
 90         for (int i=n-1;i>=0;i--)
 91         {
 92             rb[i] = getr(arr[i]+1,trb); rs[i] = getl(arr[i]-1,trs);
 93             upl(arr[i],trs); upr(arr[i],trb);
 94         }
 95         
 96         ans = suml * sumb; //逆序对数乘顺序对数，结果存在不合法的情况
 97         for (int i=0;i<n;i++)
 98         {
 99             ans -= (rs[i] * rb[i] + ls[i] * lb[i] + ls[i] * rs[i] + lb[i] * rb[i]);
100             // rs[i]*rb[i]为a,c重合的情况 ， ls[i]*lb[i]为b,d重合的情况 ， ls[i]*rs[i]为c,b重合的情况 ， lb[i]*rb[i]为a,d重合的情况
101         }
102         printf("%I64d
",ans);
103 
104     }
105     return 0;
106 }