Ball – CodeForces 12D – 树状数组

来源： Ball – CodeForces 12D – Virtual Judge

解题思路：首先按照b的顺序进行排序，然后离散化b，再按照i的顺序排序，去查找已经在树状数组里的大于b的（b+1）的里面最大的r，若查找到的r大于当前r则ans++；然后再将当前i的所有元素加入到树状数组里。
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int b,i,r;
    int id;
}a[500050];

int c[500050];
int cnt;

bool cmp(node aa,node bb)
{
    if(aa.b==bb.b)
    {
        if(aa.i==bb.i)
            return aa.r<bb.r;
        else
            return aa.i<bb.i;
    }
    return aa.b<bb.b;
}

bool cmpp(node aa,node bb)
{
    return aa.i>bb.i;
}

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

void add(int x,int d)
{
    while(x>0)
    {
        if(c[x]<d)
            c[x]=d;
        x-=lowbit(x);
    }
}

int getmax(int x)
{
    int s=-1;
    for(int i=x;i<=cnt;i+=lowbit(i))
    {
        if(s<c[i])
            s=c[i];
    }
    return s;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].b;
    }
    for(int i=0;i<n;i++)
    {
        cin>>a[i].i;
    }
    for(int i=0;i<n;i++)
    {
        cin>>a[i].r;
    }
    sort(a,a+n,cmp);//b<
    cnt=1;
    a[0].id=1;
    for(int i=1;i<n;i++)
    {
        if(a[i].b==a[i-1].b)
            a[i].id=cnt;
        else a[i].id=++cnt;
    }
    sort(a,a+n,cmpp);//i>//保证i
    memset(c,-1,sizeof(c));
    int ans=0;
    for(int i=0;i<n;)
    {
        int j;
        for(j=i;j<n&&a[i].i==a[j].i;j++)//防止i相等
        {
            if(getmax(a[j].id+1)>a[j].r)//+1保证b，>保证r
                ans++;
        }
        for(j=i;j<n&&a[i].i==a[j].i;j++)
        {
            add(a[j].id,a[j].r);
        }
        i=j;
    }
    cout<<ans<<endl;
    return 0;
}