出题人应该才是真正的机房语文竞赛冠军。
好厉害的数据结构。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]);
}