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

时间：2023-03-09 03:31:07
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: a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad.
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 A1,A2⋯An.
1≤n≤50000
0≤Ai≤1e9

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
 题意：给你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\n",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，

然后从大到小枚举一下

相关文章