HDU 5101 Select --离散化+树状数组

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：n 组，每组有一些值，求在不同的两组中每组选一个使值的和大于k的方法数。

解法：n * Cnt[n] <= 1000*100 = 100000，即最多10^5个人，所以枚举每个值x，求他的后面那些组中有多少数大于 k-x即可，求有多少数大于k-x可以先求有多少数小于等于k-x，然后总数减一下即可。可以用树状数组求。

先把所有数离散地存入一个树状数组中，然后每次枚举完一组的数后，将这组的数去掉。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define lll __int64

using namespace std;

#define N 101107

int c[N],num[][],b[*N],T[];

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

void modify(int x,int val)

{

    while(x <= N-)

    {

        c[x] += val;

        x += lowbit(x);

    }

}

int getsum(int x)

{

    int res = ;

    while(x > )

    {

        res += c[x];

        x -= lowbit(x);

    }

    return res;

}

int main()

{

    int t,n,k,m,i,j;

    cin>>t;

    while(t--)

    {

        scanf("%d%d",&n,&k);

        int cnt = ;

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

        {

            scanf("%d",&num[i][]);

            for(j=;j<=num[i][];j++)

                scanf("%d",&num[i][j]), b[++cnt] = num[i][j];

            sort(num[i]+,num[i]+num[i][]+);

        }

        T[n+] = ;

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

            T[i] = T[i+] + num[i][];

        sort(b+,b+cnt+);

        memset(c,,sizeof(c));

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

        {

            for(j=;j<=num[i][];j++)

            {

                int id = lower_bound(b+,b+cnt+,num[i][j])-b;

                modify(id,);

            }

        }

        lll sum = ;

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

        {

            for(j=;j<=num[i][];j++)

            {

                int id = lower_bound(b+,b+cnt+,num[i][j])-b;

                modify(id,-);

            }

            for(j=;j<=num[i][];j++)

            {

                int now = num[i][j],id;

                if(k-now < )  id = ;

                else

                {

                    id = lower_bound(b+,b+cnt+,k-now)-b;

                    if(b[id] != k-now) id--;

                }

                sum += T[i+]-getsum(id);

            }

        }

        cout<<sum<<endl;

    }

    return ;

}