陌上花开

bzoj 3262

Luogu 3810

思路

简单的三维偏序问题,可以先按$a$排序,按$b$归并,再将$c$扔进BIT维护

请忽略我压行压得巨丑的BIT

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
struct Data{
    int a, b, c, ans, num;
    Data():ans(0), num(1){}
    bool friend operator <(const Data &_, const Data &__){
        return _.b!=__.b ? _.b<__.b : (_.a!=__.a ? _.a<__.a : _.c<__.c);
    }
}a[100010];
int N, K, cnt=1, ans[100010];
Data tmp[100010];
 
bool cmp1(const Data &_, const Data &__){
    return _.a!=__.a ? _.a<__.a : (_.c!=__.c ? _.c<__.c : _.b<__.b);
}
 
class BIT{
private:int a[200010];int lowbit(int x){return x&(-x);}
public: BIT(){memset(a, 0, sizeof(a));}
void add(int x, int y){for(; x<=K; x+=lowbit(x))a[x]+=y;}
int query(int x){int s=0;for(; x; x-=lowbit(x))s+=a[x];return s;}
void clear(int x){for(; x<=K; x+=lowbit(x))a[x]=0;}
}T;
 
void divide(int l, int r){
    if(l==r)    return;
    int mid=(l+r)/2;
    divide(l, mid); divide(mid+1, r);
    int L=l, R=mid+1, p=l;
    while(L<=mid && R<=r)
        if(a[L]<a[R]){
            T.add(a[L].c, a[L].num);
            tmp[p++]=a[L++];
        }else{
            a[R].ans+=T.query(a[R].c);
            tmp[p++]=a[R++];
        }
    while(L<=mid)    tmp[p++]=a[L++];
    while(R<=r){
        a[R].ans+=T.query(a[R].c);
        tmp[p++]=a[R++];
    }
    for(int i=l; i<=r; i++)  T.clear(a[i].c);
    for(int i=l; i<=r; i++)  a[i]=tmp[i];
}
 
int main(){
    scanf("%d%d", &N, &K);
    for(int i=1; i<=N; i++)
        scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
    std::sort(a+1, a+N+1, cmp1);
    for(int i=2; i<=N; i++)
        if(a[i].a==a[i-1].a && a[i].b==a[i-1].b && a[i].c==a[i-1].c)    a[cnt].num++;
        else    a[++cnt]=a[i];
    divide(1, cnt);
    for(int i=1; i<=cnt; i++)    ans[a[i].ans+a[i].num-1]+=a[i].num;
    for(int i=0; i<N; i++)   printf("%d\n", ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注