陌 上 花 开 陌上花开 陌上花开

题目描述见链接 .

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

这是一道三维偏序模板题 .

流 程 流程 流程
  1. 开始时以 x x x 为第一关键字排序, y y y 为第二关键字, z z z 为第三关键字排序 .
  2. 以 y y y 为关键字进行归并 .
  3. 假设现在归并的指针为 t 1 , t 2 t1, t2 t1,t2, 分别指向左区间和右区间, 当 A [ t 1 ] . y ≤ A [ t 2 ] . y A[t1].y \le A[t2].y A[t1].y≤A[t2].y 时, 不断将 t 1 t1 t1 往后移动, 且将 A [ t 1 ] A[t1] A[t1] 加入以 z z z 为下标的 树状数组 中 .
    否则统计 A [ t 2 ] A[t2] A[t2] 的答案, 直接在 树状数组 中查询小于等于 A [ t 2 ] . z A[t2].z A[t2].z 的个数即可 .

排序解决 x x x 偏序, 归并解决 y y y 偏序, 树状数组解决 z z z 偏序 .

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

  • 每次归并都要撤销树状数组的操作来清空树状数组 .
  • 当两个花一模一样时需要统一取其中较大的答案 (前提是刚开始的排序要保证三个关键字都得到照顾) . 
#include<bits/stdc++.h>
#define reg register

const int maxn = 100005;

int N;
int K;
int Ans[maxn];
int cnt[maxn];

struct Node{ int x, y, z, res; } A[maxn], tmp[maxn];

bool cmp(Node a, Node b){ if(a.x == b.x){ if(a.y == b.y) return a.z < b.z; return a.y < b.y; } return a.x < b.x; }

struct Bit_t{
        int v[maxn<<1];
        void Add(int k, int x){ while(k<=K)v[k]+=x,k+=k&-k; }
        int Query(int k){ int s=0; while(k)s+=v[k],k-=k&-k; return s; }
} bit_t;

void merge_sort(int l, int r){
        if(l >= r) return ;
        int mid = l+r >> 1;
        merge_sort(l, mid), merge_sort(mid+1, r);
        int t1 = l, t2 = mid+1, t3 = l;
        while(t1 <= mid && t2 <= r)
                if(A[t1].y <= A[t2].y) bit_t.Add(A[t1].z, 1), tmp[t3 ++] = A[t1 ++];
                else A[t2].res += bit_t.Query(A[t2].z), tmp[t3 ++] = A[t2 ++];
        while(t2 <= r) A[t2].res += bit_t.Query(A[t2].z), tmp[t3 ++] = A[t2 ++];
        for(reg int i = l; i < t1; i ++) bit_t.Add(A[i].z, -1);
        while(t1 <= mid) tmp[t3 ++] = A[t1 ++];
        for(reg int i = l; i <= r; i ++) A[i] = tmp[i];
}

int main(){
        scanf("%d%d", &N, &K);
        for(reg int i = 1; i <= N; i ++) scanf("%d%d%d", &A[i].x, &A[i].y, &A[i].z);
        std::sort(A+1, A+N+1, cmp);
        merge_sort(1, N);
        for(reg int i = N; i >= 1; i --){
                if(A[i].x == A[i+1].x && A[i].y == A[i+1].y && A[i].z == A[i+1].z) A[i].res = A[i+1].res;
                cnt[A[i].res] ++;
        }
        for(reg int i = 0; i < N; i ++) printf("%d\n", cnt[i]);
        return 0;
}