HDU - 5517 Triple(二维树状数组)

电玩女神 2022-06-06 23:46 189阅读 0赞

原文:http://blog.csdn.net/beihai2013/article/details/49588259

[点我看题][Link 1]

题意：   
有二元组(a,b),三元组(c,d,e)。当b == e时它们能构成(a,c,d)。   
然后，当不存在(u,v,w)!=(a,b,c)且u>=a,v>=b,w>=c时，则是一个better集合里的元素。   
问这个better集合有几个元素。   
思路：   
自己写的时候完全没有思路啊~   
参考了[http://async.icpc-camp.org/d/227-shenyang-2015-i][http_async.icpc-camp.org_d_227-shenyang-2015-i]  
和[http://blog.csdn.net/keshuai19940722/article/details/49583149][http_blog.csdn.net_keshuai19940722_article_details_49583149]  
首先基本思路是对于(a1,b1),(a2,b2)，当b1==b2时，只留a最大的那个。   
同理(c,d,e),当c、e相同时只留d最大的那个。   
因为e必须要和b相同才能拼接成三元组，所以遍历输入(c,d,e)时就能把有效的(c,d,e)记录下来形成(a,d,e).   
然后要去重和不合法的(a,d,e)。按a从大到小排序，用二位树状数组统计在平面直角坐标上x >= d和y>=e的地方是否出现过(a,d,e)，没出现过即合法。   
源码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define LL long long
    const int MAXN = 1e5+10;
    const int MAXM = 1e3+10;
    int n,m;
    int id[MAXN],cnt[MAXN];
    struct P{
        int a,c,d;
        LL v;
        P(){}
        P( int aa, int cc, int dd, LL vv)
        {
            a = aa, c = cc, d = dd, v = vv;
        }
        bool operator == ( const P &p)const
        {
            if( a != p.a || c != p.c || d != p.d)
                return false;
            return true;
        }
    };
    P p[MAXN];
    int tree[MAXM][MAXM];
    
    bool cmp( P u, P v)
    {
        if( u.a != v.a)
            return u.a < v.a;
        if( u.c != v.c)
            return u.c < v.c;
        return u.d < v.d;
    }
    
    inline int lowbit( int x)
    {
        return x&(-x);
    }
    
    void Add( int x, int y, int val)
    {
        for( int i = x; i <= 1000; i += lowbit(i))
        {
            for( int j = y; j <= 1000; j += lowbit(j))
                tree[i][j] += val;
        }
    }
    
    LL Sum( int x, int y)
    {
        LL ans = 0;
        for( int i = x; i > 0; i -= lowbit(i))
        {
            for( int j = y; j > 0; j -= lowbit(j))
                ans += tree[i][j];
        }
        return ans;
    }
    
    LL Query( int x1, int y1, int x2, int y2)
    {
        return Sum(x2,y2)-Sum(x2,y1-1)-Sum(x1-1,y2)+Sum(x1-1,y1-1);
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            scanf("%d%d",&n,&m);
            mem(id,-1);
            int a,b;
            for( int i = 1; i <= n; i++)
            {
                scanf("%d%d",&a,&b);
                if( id[b] < a)
                {
                    id[b] = a;
                    cnt[b] = 1;
                }
                else if( id[b] == a)
                    cnt[b]++;
            }
            int c,d,e,num = 0;
            for( int i = 1; i <= m; i++)
            {
                scanf("%d%d%d",&c,&d,&e);
                if( id[e] != -1)
                    p[num++] = P(id[e],c,d,cnt[e]);
            }
    
            sort(p,p+num,cmp);
    
            //去重
            n = 0;
            for( int i = 1; i < num; i++)
            {
                if( p[n] == p[i])
                    p[n].v += p[i].v;
                else
                    p[++n] = p[i];
            }
    
            mem(tree,0);
            LL ans = 0;
            for( int i = n; i >= 0; i--)
            {
                if( !Query(p[i].c,p[i].d,1000,1000))
                    ans += p[i].v;
                Add(p[i].c,p[i].d,1);
            }
    
            static int cas = 1;
            printf("Case #%d: %lld\n",cas++,ans);
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5517
[http_async.icpc-camp.org_d_227-shenyang-2015-i]: http://async.icpc-camp.org/d/227-shenyang-2015-i
[http_blog.csdn.net_keshuai19940722_article_details_49583149]: http://blog.csdn.net/keshuai19940722/article/details/49583149