[BZOJ 3262]あぜ道に花が咲く

あぜ道に花が咲く
Descriptionにはn個の花があり、各花には3つの属性がある:花形(s)、色(c)、におい(m)、また3つの整数表現.それぞれの花を評価するには、1つの花のレベルは、その美しさが超える花の数です.一方の花Aが他方の花Bよりも美しいと定義され、Sa>=Sb、Ca>=Cb、Ma>=Mbのみである.明らかに、2つの花には同じ属性がある可能性があります.各等級を評価する花の数を統計する必要がある.Inputの第一挙動N,K(1<=N<=100000,1<=K<=200000)は,それぞれ花の数と最大属性値を表す.以下のN行は、1行あたり3つの整数si,ci,mi(1<=si,ci,mi<=K)であり、i番目の花の属性OutputがN行を含み、それぞれ0...N-1と格付けされた各段の花の数を表す.Sample Input 10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1 Sample Output 3 1 3 0 1 0 1 0 0 1 HINT 1 <= N <= 100,000, 1 <= K <= 200,000
Solution私たちは1次元の要求を時間と見なして、ソートを行って、CDQの分治の思想を運用して、それから私たちは問題を転化することができます:1つの点セットを与えて、1つの点の左下の点の数をクエリーしてこの問題を解決して私たちはただ1次元のソートをして、1次元の木の配列の統計はこのようにソートして1つのlogが多くなることができます私たちは常に秩序テーブルを維持することができて、線形に秩序テーブルを合併する方式でこのlogをカードします.
Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;

struct Pack{
    int a,b,c,cnt,ans;
}lst[N],tmp[N];
int n,m,K,d[N],top;
PII st[N];
int cnt[N];

inline bool cmp(const Pack &a,const Pack &b){return a.a<b.a || a.a==b.a && a.b<b.b || a.a==b.a && a.b==b.b && a.c<b.c;}
inline void mdf(int x,int dt,bool flg=1){if(flg)st[++top]=PII(x,dt);for(;x<=K;x+=x&-x) d[x]+=dt;}
inline int qry(int x){int rs=0;for(;x;x^=x&-x) rs+=d[x];return rs;}
inline void rollback(){for(;top;mdf(st[top].first,-st[top].second,0),top--);}
inline void solve(int l,int r){
    if(l==r) {lst[l].ans+=lst[l].cnt-1;return;}
    int mid=l+r>>1,pl,pr,cp;
    solve(l,mid);solve(mid+1,r);
    for(pl=l,pr=mid+1,cp=l;pl<=mid || pr<=r;)
        if(pl<=mid && (pr>r || lst[pl].b<=lst[pr].b)) mdf(lst[pl].c,lst[pl].cnt),tmp[cp++]=lst[pl++];
        else lst[pr].ans+=qry(lst[pr].c),tmp[cp++]=lst[pr++];
    for(int i=l;i<=r;i++) lst[i]=tmp[i];
    rollback();
}
int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&lst[i].a,&lst[i].b,&lst[i].c),lst[i].cnt=1;
    sort(lst+1,lst+n+1,cmp);m=1;
    for(int i=2;i<=n;i++)
        if(lst[m].a==lst[i].a && lst[m].b==lst[i].b && lst[m].c==lst[i].c) lst[m].cnt++;
        else lst[++m]=lst[i];
    solve(1,m);
    for(int i=1;i<=m;i++) cnt[lst[i].ans]+=lst[i].cnt;
    for(int i=0;i<n;i++) printf("%d
",cnt[i]);
    return 0;
}