HDU 5792 L - World is Exploding 。容斥原理 + 树状数组 + 离散化

题目，要求找出有多少对这样的东西，四个数，并且满足num[a]<num[b] &&num[c]>num[d]

要做这题，首先要懂得用树状数组，我设，下面的小于和大于都是严格的小于和大于

dpL_min[i]:表示在第i个数往左，（不包括第i个），有多少个数是少于num[i]的

dpL_max[i]:表示在第i个数往左，（不包括第i个），有多少个数是大于num[i]的

dpR_min[i]:表示在第i个数往右，（不包括第i个），有多少个数是小于num[i]的

dpR_max[i]:表示在第i个数往右，（不包括第i个），有多少个数是大于num[i]的

首先我们能预处理出所有的sumab对数，表示在1--n中有多少对这样的ab对。

sumcd同理。然后默认的ans=sumab*sumcd了

但是有重复的呀。有四种情况是重复的，就是a==d || a==c || b==c || a==c

那么，我们枚举每一个i，表示当前是a==d=num[i]，就是把a和d现在相同，且数字是num[i]，那么要减去的值就是dpR_max[i]*dpL_max[i]; dpR_max[i]表示有多少个数能和num[a]组合，变成num[a]<num[b]的对数。同理dpL_max[i]

再来一个例子吧.。假如现在是a==c=num[i]，那么ans -= dpR_max[i] * dpR_min[i]; dpR_max[i] 表示有多少个数能和num[a]组合，变成num[a]<num[b]的对数。dpR_min[i]表示有多少个数能和num[c]结合，变成num[c]>num[d]这样的对数。

这里和网上说的枚举i作为d值是不同的哦，网上的解释我感觉上是说不通的。反正我是想不明白。我这里的枚举每个i，作为他们相同的数子。

有没可能是a==c && b==d呢？可能的，矛盾了。

这里要注意的还有数字是严格大于，在离散的时候注意一下就可以了

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

int n;

const int maxn =   + ;

struct data

{

    int val,pos;

}book[maxn];

int a[maxn];

int c[maxn];//树状数组

int lowbit (int x)//得到x二进制末尾0的个数的2次方 2^num

{

    return x&(-x);

}

void add (int pos,int val)//在第pos位加上val这个值

{

    while (pos<=n) //n是元素的个数

    {

        c[pos] += val;

        pos += lowbit(pos);

    }

    return ;

}

int get_sum (int pos) //求解：1--pos的总和

{

    int ans = ;

    while (pos)

    {

        ans += c[pos];

        pos -= lowbit(pos);

    }

    return ans;

}

bool cmp (struct data a,struct data b)

{

    return a.val < b.val;

}

int dpL_min[maxn];

int dpL_max[maxn];

int dpR_min[maxn];

int dpR_max[maxn];

void init ()

{

    memset(c,,sizeof c);

    memset(dpR_max,,sizeof dpR_max);

    memset(dpR_min,,sizeof dpR_min);

    memset(dpL_max,,sizeof dpL_max);

    memset(dpL_min,,sizeof dpL_min);

}

void work ()

{

    init();

    for (int i=;i<=n;++i)

    {

        scanf("%d",&book[i].val);

        book[i].pos = i;

    }

    sort(book+,book++n,cmp);

    for (int i=;i<=n;++i)

    {

        if (i>= && book[i].val == book[i-].val) a[book[i].pos] = a[book[i-].pos];

        else a[book[i].pos]=i; //从小到大离散

    }

    for (int i=;i<=n;++i)

    {

        dpL_min[i] = get_sum(a[i]-);

        dpL_max[i] = get_sum(n)-get_sum(a[i]);

        add(a[i],);

    }

    memset(c,,sizeof c);

    for (int i=n;i>=;--i)

    {

        dpR_min[i] = get_sum(a[i]-);

        dpR_max[i] = get_sum(n) - get_sum(a[i]);

        add(a[i],);

    }

    LL sumab = ;

    LL sumcd = ;

    for (int i=;i<=n;++i) sumab += dpL_min[i];

    for (int i=;i<=n;++i) sumcd += dpL_max[i];

    LL ans = sumab * sumcd;

    for (int i=;i<=n;++i)

    {

        ans -= dpL_max[i] * dpR_max[i]; //a==d

        ans -= dpL_max[i] * dpL_min[i]; // b==d

        ans -= dpR_max[i] * dpR_min[i]; // a==c;

        ans -= dpL_min[i] * dpR_min[i]; //c==b

    }

    printf ("%I64d\n",ans);

    return ;

}

int main()

{

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    while(scanf("%d",&n)!=EOF && n) work();

    return ;

}

巴特西

HDU 5792 L - World is Exploding 。容斥原理 + 树状数组 + 离散化

最新文章

热门文章