萌新求助CDQ分治,奇怪RE+TLE
查看原帖
萌新求助CDQ分治,奇怪RE+TLE
413065
xiezheyuan楼主2022/7/20 19:49

就这份代码,将 N 设为 1e5+5 80分,剩下的RE。

改为 2e5+5 60分,剩下的TLE。

怎么奇怪的TLE了,不会和数组大小有关系吧。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;

int n, k, kkk;
bool flag;
const int N = 2e5 + 5;
struct node {
    int a, b, c, ans, cnt;
    bool operator<(const node& y) const {
        if (!flag) {
            if (a == y.a) {
                if (b == y.b)return c < y.c;
                else return b < y.b;
            } else return a < y.a;
        } else {
            if (b == y.b) {
                return c < y.c;
            } else return b < y.b;
        }
    }
} s1[N], s2[N];

int top,m;

namespace BIT{
	int t[N];
	inline int lowbit(int x){
		return x&(-x);
	}
	int query(int p){
		int ret=0;
		while(p){
			ret+=t[p];
			p-=lowbit(p);
		}
		return ret;
	}
	void update(int p,int v){
		while(p<=kkk){
			t[p]+=v;
			p+=lowbit(p);
		}
	}
	inline void clear(){
		memset(t,0,sizeof(t));
	}
}

void cdq(int l,int r){
	if(l==r){
		return;
	}
	cdq(l,mid);
	cdq(mid+1,r);
	sort(s2+l,s2+mid+1);
	sort(s2+mid+1,s2+r+1);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(s2[i].b>=s2[j].b&&j<=mid){
			BIT::update(s2[j].c,s2[j].cnt);
			j++;
		}
		s2[i].ans+=BIT::query((s2[i].c));
	}
	BIT::clear();
}

int ans[N];

int main() {
    cin >> n >> k;
    kkk = k;
    for (int i = 1, a, b, c; i <= n; i++) {
        cin >> a >> b >> c;
        s1[i].a = a;
        s1[i].b = b;
        s1[i].c = c;
    }
    sort(s1 + 1, s1 + n + 1);
    for(int i = 1; i <= n; ++i) {
        top++;
        if (s1[i].a != s1[i + 1].a || s1[i].b != s1[i + 1].b || s1[i].c != s1[i + 1].c) {
            m++;
            s2[m].a = s1[i].a;
            s2[m].b = s1[i].b;
            s2[m].c = s1[i].c;
            s2[m].cnt = top;
            top = 0;
        }
    }
	flag=1;
	cdq(1,m);
	for(int i=1;i<=m;i++){
		ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]<<'\n';
	}
    return 0;
}
2022/7/20 19:49
加载中...