找不同

rt，看了很久不知道两份代码有啥不同

WA：

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
const int M=200005;

int n,k,m;

struct node {
    int a,b,c,cnt,ans;
    friend bool operator < (const node& a,const node& b) {
        if (a.a!=b.a) return a.a<b.a;
        if (a.b!=b.b) return a.b<b.b;
        return a.c<b.c;
    }
    friend bool operator == (const node& a,const node& b) {
        return a.a==b.a && a.b==b.b && a.c==b.c;
    }
} in[N],arr[N],st[N];

int tr[M];
int res[M];

int lowbit(int x) {
    return x&-x;
}

void modify(int u,int k) {
    for (int i=u;i<M;i+=lowbit(i)) tr[i]+=k;
}

int query(int u) {
    int ans=0;
    for (int i=u;i;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

void merge(int l,int r) {
    if (l>=r) return;
    int mid=l+r>>1;
    merge(l,mid); merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    while (i<=mid && j<=r) {
        if (arr[i].b<=arr[j].b) modify(arr[i].c,arr[i].cnt),st[k++]=arr[i++];
        else arr[j].ans=query(arr[j].c),st[k++]=arr[j++];
    }
    while (i<=mid) modify(arr[i].c,arr[i].cnt),st[k++]=arr[i++];
    while (j<=r) arr[j].ans=query(arr[j].c),st[k++]=arr[j++];
    for (int i=l;i<=mid;++i) modify(arr[i].c,-arr[i].cnt);
    for (int i=l;i<=r;++i) arr[i]=st[i];
}

int main() {
    scanf("%d %d",&n,&k);
    for (int i=1;i<=n;++i) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        in[i]={a,b,c,1};
    }
    sort(in+1,in+1+n);
    arr[++m]=in[1];
    for (int i=2;i<=n;++i) {
        if (in[i]==arr[m]) arr[m].cnt++;
        else arr[++m]=in[i];
    }
//    for (int i=1;i<=m;++i) {
//        printf("test: %d %d %d %d\n",arr[i].a,arr[i].b,arr[i].c,arr[i].cnt);
//    }
    merge(1,m);
    for (int i=1;i<=m;++i) {
        res[arr[i].ans+arr[i].cnt-1]+=arr[i].cnt;
    }
//    for (int i=1;i<=m;++i) {
//        printf("test2: %d %d %d %d\n",arr[i].a,arr[i].b,arr[i].c,arr[i].ans);
//    }
    for (int i=0;i<n;++i) {
        printf("%d\n",res[i]);
    }
    return 0;
}

AC:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    int a, b, c, s, res;

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].s ++ ;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

    return 0;
}