CDQ分治或树套树可以切掉
CDQ框架：- 先分
- 计算左边对右边的贡献
- 再和
所以这个题可以一维排序，二维CDQ，三维树状数组统计
CDQ代码# include# include # include # include # include # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}const int MAXN(100010), MAXK(200010);int n, k, t[MAXK], m;struct Point{ int a, b, c, cnt, id, ans; IL bool operator ==(RG Point B) const{ return a == B.a && b == B.b && c == B.c; }} p[MAXN], q[MAXN];IL bool Cmp1(RG Point x, RG Point y){ return x.a < y.a || (x.a == y.a && (x.b < y.b || (x.b == y.b && x.c < y.c))); }IL bool Cmp2(RG Point x, RG Point y){ return x.b < y.b || (x.b == y.b && (x.c < y.c || (x.c == y.c && x.a < y.a))); }IL void Add(RG int x, RG int d){ for(; x <= k; x += x & -x) t[x] += d; }IL int Query(RG int x){ RG int cnt = 0; for(; x; x -= x & -x) cnt += t[x]; return cnt; }IL void CDQ(RG int l, RG int r){ if(l == r) return; RG int mid = (l + r) >> 1; CDQ(l, mid); CDQ(mid + 1, r); sort(p + l, p + r + 1, Cmp2);//可以归并排序 for(RG int i = l; i <= r; i++) if(p[i].id <= mid) Add(p[i].c, p[i].cnt); else p[i].ans += Query(p[i].c); for(RG int i = l; i <= r; i++) if(p[i].id <= mid) Add(p[i].c, -p[i].cnt);}int main(RG int argc, RG char* argv[]){ n = Read(); k = Read(); for(RG int i = 1; i <= n; i++) q[i] = (Point){Read(), Read(), Read()}; sort(q + 1, q + n + 1, Cmp1); for(RG int i = 1; i <= n; i++) if(q[i] == p[m]) p[m].cnt++; else p[++m] = q[i], p[m].cnt = 1, p[m].id = m; CDQ(1, m); sort(p + 1, p + m + 1, Cmp1); for(RG int i = 1; i <= m; i++) t[p[i].ans + p[i].cnt - 1] += p[i].cnt; for(RG int i = 0; i < n; i++) printf("%d\n", t[i]); return 0;}
附上树套树
# include# include # include # include # include # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c > '9' || c < '0'; c = getchar()) z = c == '-' ? -1 : 1;; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}const int MAXN(100010);int n, k, ans[MAXN], NOW;struct YYB{ int a, b, c; IL bool operator <(RG YYB B) const{ if(a != B.a) return a < B.a; if(b != B.b) return b < B.b; return c < B.c; } IL bool operator ==(RG YYB B) const{ return a == B.a && b == B.b && c == B.c; }} yyb[MAXN];struct SBT{ SBT *ch[2], *fa; int size, val, cnt; IL SBT(RG SBT *f, RG int v, RG int d){ cnt = size = d; val = v; fa = f; }} *rt[MAXN << 1];IL int Son(RG SBT *x){ return x -> fa -> ch[1] == x; }IL int Size(RG SBT *x){ return x == NULL ? 0 : x -> size; }IL void Updata(RG SBT *x){ x -> size = Size(x -> ch[0]) + Size(x -> ch[1]) + x -> cnt; }IL void Rot(RG SBT *x){ RG int c = !Son(x); RG SBT *y = x -> fa; y -> ch[!c] = x -> ch[c]; if(x -> ch[c] != NULL) x -> ch[c] -> fa = y; x -> fa = y -> fa; if(y -> fa != NULL) y -> fa -> ch[Son(y)] = x; x -> ch[c] = y; y -> fa = x; Updata(y);}IL void Splay(RG SBT *x, RG SBT *f){ while(x -> fa != f){ RG SBT *y = x -> fa; if(y -> fa != f) Son(x) ^ Son(y) ? Rot(x) : Rot(y); Rot(x); } Updata(x); rt[NOW] = x;}IL void Insert(RG SBT *x, RG int v, RG int d){ if(rt[NOW] == NULL){ rt[NOW] = new SBT(NULL, v, d); return; } while(2333){ RG int id = v > x -> val; if(v == x -> val){ x -> size += d; x -> cnt += d; break; } if(x -> ch[id] == NULL){ x -> ch[id] = new SBT(x, v, d); x = x -> ch[id]; break; } x = x -> ch[id]; } Splay(x, NULL);}IL int Calc(RG SBT *x, RG int v){ RG int cnt = 0; while(x != NULL){ if(v >= x -> val) cnt += Size(x -> ch[0]) + x -> cnt; if(v == x -> val) break; x = x -> ch[v > x -> val]; } return cnt;}IL void Modify(RG int id, RG int d){ for(NOW = yyb[id].b; NOW <= k; NOW += NOW & -NOW) Insert(rt[NOW], yyb[id].c, d);}IL int Query(RG int id){ RG int cnt = 0; for(RG int i = yyb[id].b; i; i -= i & -i) cnt += Calc(rt[i], yyb[id].c); return cnt;}int main(){ n = Read(); k = Read(); for(RG int i = 1; i <= n; i++) yyb[i] = (YYB){Read(), Read(), Read()}; sort(yyb + 1, yyb + n + 1); for(RG int i = 1, sum = 0; i <= n; i++){ sum++; if(yyb[i] == yyb[i + 1]) continue; ans[Query(i) + sum - 1] += sum; Modify(i, sum); sum = 0; } for(RG int i = 0; i < n; i++) printf("%d\n", ans[i]); return 0;}