嘟嘟嘟
很显然我开始学\(CDQ\)分治了。
我刚开始学的时候看了一篇博客，上面全是一些抽象的概念，看完后真是一头雾水，最后还不得不抄了这题的代码。
但这样可不行呀……
于是我就不打算再扣那篇博客，而是自己想，最后真的自己想明白了。
（个人感觉这道题跟\(CDQ\)分治关系不大）
首先想一下二维偏序：我们先按第一维排序，然后第二维动态的用树状数组维护。也就是说，得保证前几维都有序的前提下，才可以用数据结构维护最后一维。
现在换到了三维：所以我们必须保证在前两维有序的前提下，才能维护第三维。
首先都能想到，按第一维排序，这样就保证第一维有序了。
如何保证第二维\(y\)有序？如果硬排序，又会导致第一维\(x\)乱序。但是排序还是要排的。有没有一种排序方法能使第一维“不太乱”呢？
答案是有的：归并排序！对于区间\([L, R]\)，虽然\([L, mid]\)和\([mid + 1, R]\)中的\(y\)有序，\(x\)乱序，但是\([mid + 1, R]\)中的任何一个元素的\(x\)仍是比\([L, mid]\)中的任何一个都大的！因此右区间相对于左区间保证了前两维有序，所以此时我们就能用树状数组维护第三维了！
这大概就是\(CDQ\)分治中的左修改只会对右询问造成影响的意思吧。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, k;
struct Node
{
int x, y, z, cnt, sum;
bool operator < (const Node& oth)const
{
if (x != oth.x) return x < oth.x;
if (y != oth.y) return y < oth.y;
return z < oth.z;
}
bool operator != (const Node& oth)const
{
return x != oth.x || y != oth.y || z != oth.z;
}
bool operator > (const Node& oth)const
{
if(y != oth.y) return y < oth.y;
return z <= oth.z;
}
}a[maxn], t[maxn];
int c[maxm];
int lowbit(int x)
{
return x & -x;
}
void init(int pos)
{
for(; pos <= k; pos += lowbit(pos))
if(c[pos] != 0) c[pos] = 0;
else break;
}
void add(int pos, int d)
{
for(; pos <= k; pos += lowbit(pos)) c[pos] += d;
}
int query(int pos)
{
int ret = 0;
for(; pos; pos -= lowbit(pos)) ret += c[pos];
return ret;
}
void cdqSolve(int L, int R)
{
if(L == R) return;
int mid = (L + R) >> 1, id1 = L, id2 = mid + 1;
cdqSolve(L, mid); cdqSolve(mid + 1, R);
for(int i = L; i <= R; ++i)
{
if(id2 > R || (id1 <= mid && a[id1] > a[id2])) //这个大于号是比较第二维的,不是真正的大于号
{
t[i] = a[id1++];
add(t[i].z, t[i].cnt);
}
else
{
t[i] = a[id2++];
t[i].sum += query(t[i].z);
}
}
for(int i = L; i <= R; ++i) a[i] = t[i], init(a[i].z);//分治的每一层，别忘了清空树状数组
}
int ans[maxn];
int main()
{
m = read(); k = read();
for(int i = 1; i <= m; ++i) t[i].x = read(), t[i].y = read(), t[i].z = read();
sort(t + 1, t + m + 1);
for(int i = 2, j = 1; i <= m + 1; ++i)
if(t[j] != t[i] || i == m + 1) a[++n] = t[j], a[n].cnt = i - j, j = i;
cdqSolve(1, n);
for(int i = 1; i <= n; ++i) ans[a[i].sum + a[i].cnt - 1] += a[i].cnt;
for(int i = 0; i < m; ++i) write(ans[i]), enter;
return 0;
}