Triple HDU - 5517

http://acm.hdu.edu.cn/showproblem.php?pid=5517

全是細節。。

如果直接合并AB 得到的C會非常大 這時發現可以對A去重 當b相等時隻保留a最大的一個 因為其他a較小的二進制組會被目前這個覆寫

合并後就是一個三維偏序問題 可以用CDQ分治搞 但是這裡cd都很小 最大1e3 二維樹狀數組或線段樹就足夠

#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;

struct node1
{
    int a,b,cnt;
};

struct node2
{
    int c,d,e;
};

struct node3
{
    int a,c,d,cnt1,cnt2;
};

node1 ary1[maxn];
node2 ary2[maxn];
node3 pre[maxn];
int maxx[1010][1010];
int book[100010];
int n,m,tot;

bool cmpI(node1 n1,node1 n2)
{
    if(n1.b==n2.b) return n1.a<n2.a;
    else return n1.b<n2.b;
}

bool cmpII(node3 n1,node3 n2)
{
    if(n1.c==n2.c)
    {
        if(n1.d==n2.d) return n1.a>n2.a;
        else return n1.d>n2.d;
    }
    else return n1.c>n2.c;
}

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

int query(int x,int y)
{
    int res,tmp;
    res=0,tmp=y;
    while(x<=1000)
    {
        y=tmp;
        while(y<=1000) res=max(res,maxx[x][y]),y+=lowbit(y);
        x+=lowbit(x);
    }
    return res;
}

void update(int x,int y,int val)
{
    int tmp=y;
    while(x)
    {
        y=tmp;
        while(y) maxx[x][y]=max(maxx[x][y],val),y-=lowbit(y);
        x-=lowbit(x);
    }
}

int main()
{
    int t,cas,i,j,ans,l,r,mid,p;
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) scanf("%d%d",&ary1[i].a,&ary1[i].b);
        for(i=1;i<=m;i++) scanf("%d%d%d",&ary2[i].c,&ary2[i].d,&ary2[i].e);
        sort(ary1+1,ary1+n+1,cmpI);
        for(i=1,j=0;i<=n;i++)
        {
            if(j==0||ary1[j].b<ary1[i].b) ary1[++j]=ary1[i],ary1[j].cnt=1;
            else if(ary1[j].b==ary1[i].b&&ary1[j].a<ary1[i].a) ary1[j]=ary1[i],ary1[j].cnt=1;
            else ary1[j].cnt++;
        }
        n=j;

        tot=0;
        for(i=1;i<=m;i++)
        {
            l=1,r=n,p=-1;
            while(l<=r)
            {
                mid=(l+r)/2;
                if(ary1[mid].b<ary2[i].e) l=mid+1;
                else if(ary1[mid].b>ary2[i].e) r=mid-1;
                else
                {
                    p=mid;
                    break;
                }
            }
            if(p!=-1)
            {
                tot++;
                pre[tot].a=ary1[p].a,pre[tot].c=ary2[i].c,pre[tot].d=ary2[i].d,pre[tot].cnt1=ary1[p].cnt;
            }
        }
        sort(pre+1,pre+tot+1,cmpII);

        memset(book,0,sizeof(book));
        for(i=1;i<=tot;i++)
        {
            if(!book[i])
            {
                pre[i].cnt2=1;
                j=i+1;
                while(j<=tot&&pre[i].a==pre[j].a&&pre[i].c==pre[j].c&&pre[i].d==pre[j].d) pre[i].cnt2++,book[j]=1,j++;
            }
        }

        memset(maxx,0,sizeof(maxx));
        ans=0;
        for(i=1;i<=tot;i++)
        {
            if(!book[i])
            {
                p=query(pre[i].c,pre[i].d);
                if(p<pre[i].a) ans+=pre[i].cnt1*pre[i].cnt2;
            }
            update(pre[i].c,pre[i].d,pre[i].a);
        }
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}