hdu 5792 World is Exploding 树状数组+离散化+容斥

World is Exploding

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 727 Accepted Submission(s): 348

Problem Description

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies:

Input

The input consists of multiple test cases.
Each test case begin with an integer n in a single line.

The next line contains n integers

Output

For each test case,output a line contains an integer.

Sample Input

4 2 4 1 3 4 1 2 3 4

Sample Output

1 0

Author

ZSTU

Source

2016 Multi-University Training Contest 5

题意：给你n个数字，要求从中找到下标i<j，a[i]<a[j]；p<q，a[p]>a[q]且i,j,p,q互不相等的组数；

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef  long long  ll;
typedef unsigned long long ull;
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x7f7f7f7f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define CT continue;
#define PF printf
#define SC scanf
const int mod=1000000007;
const int N=1e6+10;
int tmp[N],a[N],n,m,c[N],pos[N];
ll lmin[N],rmin[N],lmax[N],rmax[N];

int lowbit(int i)
{
    return i&(-i);
}

void add(int x)
{
    while(x<=m)
    {
      c[x]+=1;
      x+=lowbit(x);
    }
}

int query(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    while(~scanf("%d",&n))
    {
         for(int i=1;i<=n;i++)
          {
              scanf("%d",&tmp[i]);
              a[i]=tmp[i];
          }

         sort(tmp+1,tmp+n+1);
         m=unique(tmp+1,tmp+n+1)-tmp-1;

         for(int i=1;i<=n;i++)
             pos[i]=lower_bound(tmp+1,tmp+m+1,a[i])-tmp;

         MM(c,0);
         for(int i=1;i<=n;i++)
         {
             lmin[i]=query(pos[i]-1);
             lmax[i]=query(m)-query(pos[i]);
             add(pos[i]);
         }


         MM(c,0);
         for(int i=n;i>=1;i--)
         {
             rmin[i]=query(pos[i]-1);
             rmax[i]=query(m)-query(pos[i]);
             add(pos[i]);
         }

         ll ans=0,l=0,r=0;
         for(int i=1;i<=n;i++)  {r+=rmax[i],l+=lmax[i];};
         ans=l*r;
         for(int i=1;i<=n;i++)
         {
             ans-=lmin[i]*rmin[i];
             ans-=lmax[i]*rmax[i];
             ans-=lmax[i]*lmin[i];
             ans-=rmax[i]*rmin[i];
         }
         printf("%lld
",ans);
    }
    return 0;
}

　　分析：比赛的时候又是只想到暴力枚举，结果发现肯定超时，复杂度又不会降下来，就跪了。。。

后来看了下题解，结果发现跟以前做的一道题很像。是以前做过的题的综合。

解决：既然超时了的话，就想想通过什么办法把复杂度降下来，，于是BIT，BIT可以在logn的时间内

求出每个点两侧>或<的数的个数；

BIT：因为只关心数据的相对大小，数据范围又很大，所以需要离散化

离散化：sort排好序后，用unique去重，然后对于原数组的每个数，利用lower_bound();找到其在去重

之后数组中的位置，记录下来，作为在BIT中的位置。

按原来的顺序枚举每个数，对于query(pos[i]-1)为查找在1-i中小于其的数的个数。query(m)-query(pos[i])为在1-i中>其的个数，因为是从小到大枚举所以都是l;然后将其在BIT中的对应位置的值+1，

然后从大到小枚举一下