我真的写不来cdq啊……
树套树卡常丧心病狂（作死套了fhqTreap……）
注意最后对于完全一样的点， 要在这些点的贡献都添加完了之后一起算答案Code：
// luogu-judger-enable-o2#include#include #include using namespace std;const int N = 2e5 + 5;const int M = N * 21;int n, m, ans[N];struct Node { int ai, bi, ci;} a[N];inline bool cmp(const Node &x, const Node &y) { if(x.ai != y.ai) return x.ai < y.ai; if(x.bi != y.bi) return x.bi < y.bi; return x.ci < y.ci;}inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}namespace FhqTreap { int root[M], cnt, ch[M][2], key[M], pri[M], siz[M]; #define lc ch[p][0] #define rc ch[p][1] inline void init() { cnt = 0; } inline void up(int p) { siz[p] = siz[lc] + siz[rc] + 1; } inline int newnode(int val) { ++cnt; siz[cnt] = 1; pri[cnt] = rand(); key[cnt] = val; return cnt; } void split(int p, int v, int &x, int &y) { if(!p) x = y = 0; else { if(v < key[p]) y = p, split(lc, v, x, lc); else x = p, split(rc, v, rc, y); up(p); } } int merge(int x, int y) { if(!x || !y) return x + y; else { if(pri[x] < pri[y]) { ch[x][1] = merge(ch[x][1], y); up(x); return x; } else { ch[y][0] = merge(x, ch[y][0]); up(y); return y; } } } inline void insert(int R, int val) { if(!root[R]) { root[R] = newnode(val); return; } int r1, r2; split(root[R], val, r1, r2); root[R] = merge(r1, merge(newnode(val), r2)); } inline int getRank(int R, int val) { int r1, r2, res; split(root[R], val - 1, r1, r2); res = siz[r1]; root[R] = merge(r1, r2); return res; } }using namespace FhqTreap;struct BinaryIndexTree { inline int lowbit(int x) { return x & -x; } inline void modify(int x, int val) { for(; x <= m; x += lowbit(x)) insert(x, val); } inline int getsum(int x, int val) { int res = 0; for(; x > 0; x -= lowbit(x)) res += getRank(x, val + 1); return res; } } bit;int main() { srand(19260817); read(n), read(m); init(); for(int i = 1; i <= n; i++) read(a[i].ai), read(a[i].bi), read(a[i].ci);// bit.modify(a[i].bi, a[i].ci); sort(a + 1, a + 1 + n, cmp); for(int sum = 0, i = 1; i <= n; i++) {/* for(ed = i; a[ed].ai == a[i].ai; ed++); for(int j = i; j < ed; j++) ans[bit.getsum(a[j].bi, a[j].ci)]++; for(int j = i; j < ed; j++) bit.modify(a[j].bi, a[j].ci); */ if(a[i].ai == a[i + 1].ai && a[i].bi == a[i + 1].bi && a[i].ci == a[i + 1].ci) sum++; else { int res = bit.getsum(a[i].bi, a[i].ci); ans[res] += sum + 1; sum = 0; } bit.modify(a[i].bi, a[i].ci); } for(int i = 0; i < n; i++) printf("%d\n", ans[i]); return 0;}