首页 > > 程序设计 > C/C++ >

HDU 5517---Triple（二维树状数组）

2018-06-17 22:28:27来源：未知阅读 ()

题目链接

Problem Description

Given the finite multi-set

Input

The input contains several test cases. The first line of the input is a single integer

a 1, b 1, a 2, b 2, ?, a n, b n

c 1, d 1, e 1, c 2, d 2, e 3, ?, c m, d m, e m

Output

For each test case, you should output the size of set

Sample Input

5 9

1 1

2 2

3 3

4 2

1 4 1

2 2 1

4 1 1

1 3 2

3 2 2

4 1 2

2 4 3

3 2 3

4 1 3

3 4

2 7

1 4 7

2 3 7

3 2 7

4 1 7

Sample Output

Case #1: 5

Case #2: 12

题意：每组数据第一行输入n m ，第二行输入a1 b1 a2 b2......an bn,第三行输入c1 d1 e1......cm dm em

现在定义C=A*B 即{<a,c,d>|<a,b>属于A & <c,d,e>属于B & b==e}

然后基于C有这样一个运算TOP（C）={<a,c,d>|<a,c,d>属于C & C中不存在<u,v,w>使得 u>=a,v>=c,w>=d,<u,v,w>!=<a,c,d> }

现在求 TOP(C)中有几个元素？

思路：

上面是从论坛上截图下来的，我觉得优化的时候，只需要用第一条即可，即：对于二元组（a，b），b相同的话只有最大的a值有效，所以对相同的b记录一下最大值的个数

第二条不一定能优化，在极端的数据上，一点都不会优化。经过第一条的优化后，C的大小为1e5,然后用二维树状数组处理O(n)=1e5*log2(1000)*log2(1000)=1e7

实际的数据肯定会比这个复杂度要小。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+5;
int a1[N],cnt[N];
int c[1005][1005];

struct Node
{
    int a,c,d;
    int v;
}tr[N];
int cmp(const Node s1,const Node s2)
{
    if(s1.a!=s2.a) return s1.a<s2.a;
    if(s1.c!=s2.c) return s1.c<s2.c;
    return s1.d<s2.d;
}
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)
{
    int ans=0;
    int i=tr[x].c;
    while(i<1005)
    {
        int j=tr[x].d;
        while(j<1005)
        {
            ans+=c[i][j];
            j+=lowbit(j);
        }
        i+=lowbit(i);
    }
    return ans;
}
void update(int x)
{
    int i=tr[x].c;
    while(i>0)
    {
        int j=tr[x].d;
        while(j>0)
        {
            c[i][j]++;
            j-=lowbit(j);
        }
        i-=lowbit(i);
    }
}
int main()
{
    ///cout << "Hello world!" << endl;
    int t,Case=1;
    cin>>t;
    while(t--)
    {
       int n,m;
       scanf("%d%d",&n,&m);
       memset(a1,-1,sizeof(a1));
       memset(c,0,sizeof(c));
       for(int i=1;i<=n;i++)
      {
          int a,b;
          scanf("%d%d",&a,&b);
          if(a1[b]<a){
             a1[b]=a;
             cnt[b]=1;
          }
          else if(a1[b]==a) cnt[b]++;
      }
      int num=0;
      for(int i=1;i<=m;i++)
      {
          int c,d,e;
          scanf("%d%d%d",&c,&d,&e);
          if(a1[e]==-1) continue;
          tr[num].a=a1[e];
          tr[num].c=c;
          tr[num].d=d;
          tr[num++].v=cnt[e];
      }
      sort(tr,tr+num,cmp);
      int flag=0;
      int k=0;
      for(int i=1;i<num;i++)
      {
          if(tr[i].a==tr[k].a&&tr[i].c==tr[k].c&&tr[i].d==tr[k].d)
          {
              tr[k].v+=tr[i].v;
          }
          else{
             k++;
             flag=1;
             tr[k].a=tr[i].a;
             tr[k].c=tr[i].c;
             tr[k].d=tr[i].d;
             tr[k].v=tr[i].v;
          }
      }
      long long ans=0;
      if(flag)  ///防止 1 1 （1，1） （1，1，2） 这样的数据(但是HDU上没这样的数据);
      for(int i=k;i>=0;i--)
      {
          if(!query(i)) ans+=(long long)tr[i].v;
          update(i);
      }
      printf("Case #%d: %lld\n",Case++,ans);
    }
    return 0;
}