bzoj3262陌上花開 cdq分治 三維偏序

cdq分治的入門題目，學習一下這個很實用的玩意兒。

大概思想就是把線上變為離線，去掉時間的限制，然後每次對于詢問區間分治處理，塊内之間的影響可以遞歸處理，然後剩下的就是塊與塊之間的影響，這個其實就很簡單了，随便搞搞就好，反正是靜态查詢，雙指針啊啥的随便上。。

這題的話第一維排序，第二維cdq，第三維樹狀數組。

直接做就好啦。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=+;
int m;
typedef long long ll;
struct node
{
    int a,b,c,cnt,ans;
    bool operator < (const node &x) const 
    {
        if (x.a!=a)return a<x.a;
        if (x.b!=b)return b<x.b;
        return c<x.c;
    }
}a[N],tmp[N];
bool cmp(const node &x,const node &y)
{
    if (x.b!=y.b)return x.b<y.b;
    if (x.c!=y.c)return x.c<y.c;
    return x.a<y.a;
}
int n,K,tot,c[N+],tim[N],cnt[N],T;
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,int val)
{
    while (x<=K)
    {
        if (tim[x]!=T)c[x]=;
        tim[x]=T;
        c[x]+=val;
        x+=lowbit(x);
    }
}
inline int query(int x)
{
    int ret=;
    while (x>)
    {
        if (tim[x]==T)
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
inline void cdq(int l,int r)
{
    if (l==r)
    {
        a[l].ans+=a[l].cnt-;
        return;
    }
    int mid=(l+r)>>;
    int l1,l2;
    l1=l,l2=mid+;
    fo(i,l,r)
    {
        if (a[i].a<=mid)tmp[l1++]=a[i];
        else tmp[l2++]=a[i];
    }
    fo(i,l,r)a[i]=tmp[i];
    cdq(l,mid);
    int j=l;T++;
    fo(i,mid+,r)
    {
        for(;j<=mid&&a[j].b<=a[i].b;j++)add(a[j].c,a[j].cnt);
        a[i].ans+=query(a[i].c);
    }
    cdq(mid+,r);
    l1=l,l2=mid+;
    fo(i,l,r)
    if (l1<=mid&&(l2>r||cmp(a[l1],a[l2])))tmp[i]=a[l1++];
    else tmp[i]=a[l2++];
    fo(i,l,r)a[i]=tmp[i];
} 
int main()
{
    scanf("%d%d",&n,&K);
    fo(i,,n)
    {
        scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
        a[i].cnt++;
    }
    sort(a+,a++n);
    fo(i,,n)
    {
        if (i==||a[i-]<a[i])a[++tot]=a[i];
        else a[tot].cnt++;
    }
    fo(i,,tot)a[i].a=i;
    sort(a+,a++tot,cmp);
    cdq(,tot);
    fo(i,,tot)cnt[a[i].ans]+=a[i].cnt;
    fo(i,,n-)printf("%d\n",cnt[i]);
}