呜呜呜谁来救救这个小阔爱啊qwq
查看原帖
呜呜呜谁来救救这个小阔爱啊qwq
950268
Luban_No_7楼主2023/3/17 14:38

我真的受不了了,明明和我之前写的代码一模一样为什么过不去呢?样例没问题啊

救救这个蒟蒻吧呜呜呜

#include <bits/stdc++.h>
using namespace std;
int n, k;
struct node{
    int a, b, c;
    int count;
    int answer;
    bool operator<(const node a) const {
        if(this->a == a.a){
            if(this->b == a.b)
                return this->c < a.c;
            return this->b < a.b;
        }
        return this->a < a.a;
    }
    bool operator==(node a) {return this->a == a.a && this->b == a.b && this->c == a.c;}
};
struct TreeArray{
    int tree[200005];
    static inline int lowbit(int x){return x & (-x);}
    void add(int p, int x){
        for(; p <= k; p += lowbit(p))
            tree[p] += x;
    }
    int query(int p){
        int ret = 0;
        for(; p > 0; p -= lowbit(p))
            ret += tree[p];
        return ret;
    }
}tree;
vector<node> arr, input;
vector<int> output;
void CDQ(int l, int r){
    if(l == r) return;
    int mid = (l + r) / 2;
    CDQ(l, mid), CDQ(mid + 1, r);
    sort(arr.begin() + l, arr.begin() + mid + 1, [](node a, node b)->bool{
        if(a.b == b.b) return a.c < b.c; 
        return a.b < b.b;
    });
    sort(arr.begin() + mid + 1, arr.begin() + r + 1, [](node a, node b)->bool{
        if(a.b == b.b) return a.c < b.c; 
        return a.b < b.b;
    });
    int j = l, i = mid + 1;
    while(i <= r){
        while(arr[i].b >= arr[j].b && j <= mid){
            tree.add(arr[j].c, arr[j].count);
            j++;
        }
        arr[i].answer += tree.query(arr[i].c);
        i++;
    }
    for(int i = l; i < j; i++)
        tree.add(arr[i].c, -arr[i].count);
}
int main(){
    scanf("%d %d", &n, &k);
    arr.push_back(node()), input.resize(n + 1);
    for(int i = 1; i <= n; i++)
        scanf("%d %d %d", &input[i].a, &input[i].b, &input[i].c);
    sort(input.begin() + 1, input.end());
    for(int i = 1; i <= n; i++){
        if(!(input[i] == input[i - 1]))
            arr.push_back(input[i]);
        arr.back().count++;
    }
    CDQ(1, arr.size() - 1);
    output.resize(arr.size());
    for(int i = 1; i < arr.size(); i++)
        output[arr[i].answer + arr[i].count - 1] += arr[i].count;
    for(int i = 0; i < n; i++)
        printf("%d\n", output[i]);
    return 0;
}
2023/3/17 14:38
加载中...