来!大家找错误
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
inline ll read()
{
ll x = 0; bool op = 0;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar() ;
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 100010;
const int MAXN = 200010;
int n, cnt, m;
int tree[MAXN], ans[N];
struct node
{
int x, y, z;
int s, res;
}A[N];
node tmp[N];
bool cmp(node a, node b)
{
if(a.x != b.x)
return a.x < b.x;
if(a.y != b.y)
return a.y < b.y;
return a.x < b.z;//这里
}
void In()
{
n = read(); m = read();
for(int i = 1; i <= n; i++)
{
A[i].x = read(); A[i].y = read(); A[i].z = read();
A[i].res = 0; A[i].s = 1;
}
return ;
}
void Unique()
{
sort(A + 1, A + 1 + n, cmp);
cnt = 1;
for(int i = 2; i <= n; i++)
{
if(A[cnt].x == A[i].x && A[cnt].y == A[i].y && A[cnt].z == A[i].z)
A[cnt].s++;
else A[++cnt] = A[i];
}
return ;
}
int lowbit(int x)
{
return x & -x;
}
void update(int x, int val)
{
while(x <= m)
{
tree[x] += val;
x += lowbit(x);
}
return ;
}
int query(int x)
{
int res = 0;
while(x > 0)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}
void CDQ(int l, int r)
{
if(l == r)
return ;
int mid = l + r >> 1;
CDQ(l, mid); CDQ(mid + 1, r);
int p = l, q = mid + 1, tot = l;
while(p <= mid && q <= r)
{
if(A[p].y <= A[q].y)
{
update(A[p].z, A[p].s);
tmp[tot++] = A[p++];
}
else
{
A[q].res += query(A[q].z);
tmp[tot++] = A[q++];
}
}
while(p <= mid)
{
update(A[p].z, A[p].s);
tmp[tot++] = A[p++];
}
while(q <= mid)//这里
{
A[q].res += query(A[q].z);
tmp[tot++] = A[q++];
}
for(int i = l; i <= mid; i++)
{
update(A[i].z, -A[i].s);
}
for(int i = l; i <= r; i++)
{
A[i] = tmp[i];
}
return ;
}
void Solve()
{
CDQ(1, cnt);
for(int i = 1; i <= cnt; i++)
{
ans[A[i].res + A[i].s - 1] += A[i].s;
}
for(int i = 0; i < n; i++)
{
printf("%d\n", ans[i]);
}
return ;
}
int main()
{
In();
Unique();
Solve();
return 0;
}
就这两个扇贝错误调了我两个小时……
所以怎么减少低级错误