laekov

出题人应该才是真正的机房语文竞赛冠军。

好厉害的数据结构。cdq的不会。

树状数组套平衡树跑得飞快。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

struct flower {

int a, b, c;

};

const int maxn = 100009;

const int maxv = 200009;

const int maxl = 17;

#define update(p) (sz[p]=sz[ls[p]]+sz[rs[p]]+1)

namespace sbt {

const int maxnd = maxn * maxl;

const int balc = 10;

int tn, ls[maxnd], rs[maxnd], sz[maxnd], vl[maxnd];

void init() {

tn = 0;

sz[0] = 0;

}

inline void lRot(int& p) {

int q = rs[p];

rs[p] = ls[q];

ls[q] = p;

update(p);

update(q);

p = q;

}

inline void rRot(int& p) {

int q = ls[p];

ls[p] = rs[q];

rs[q] = p;

update(p);

update(q);

p = q;

}

inline void ins(int& p, int v) {

if (!p) {

p = ++ tn;

ls[p] = 0;

rs[p] = 0;

sz[p] = 1;

vl[p] = v;

}

else {

++ sz[p];

if (v < vl[p]) {

ins(ls[p], v);

if (sz[ls[p]] > sz[rs[p]] + balc)

rRot(p);

}

else {

ins(rs[p], v);

if (sz[ls[p]] + balc < sz[rs[p]])

lRot(p);

}

}

}

int cntLower(int p, int v) {

if (!p)

return 0;

else if (v >= vl[p])

return sz[ls[p]] + 1 + cntLower(rs[p], v);

else

return cntLower(ls[p], v);

}

};

inline bool cmpFlower(const flower& a, const flower& 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 bool equFlower(const flower& a, const flower& b) {

return a. a == b. a && a. b == b. b && a. c == b. c;

}

int n, m, t[maxv], ans[maxn];

flower a[maxn];

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

sbt :: init();

memset(ans, 0, sizeof(ans));

memset(t, 0, sizeof(t));

scanf("%d%d", &n, &m);

for (int i = 0; i < n; ++ i)

scanf("%d%d%d", &a[i]. a, &a[i]. b, &a[i]. c);

sort(a, a + n, cmpFlower);

for (int i = 0, j; i < n; i = j + 1) {

int s = 0;

for (int p = a[i]. b; p; p -= (p & -p))

s += sbt :: cntLower(t[p], a[i]. c);

for (j = i; equFlower(a[i], a[j + 1]) && j < n; ++ j);

for (int k = i; k <= j; ++ k) {

++ ans[s + j - i];

for (int p = a[k]. b; p <= m; p += (p & -p))

sbt :: ins(t[p], a[k]. c);

}

}

for (int i = 0; i < n; ++ i)

printf("%d\n", ans[i]);

}