求助,孩子调 cdq 分治调傻了
查看原帖
求助,孩子调 cdq 分治调傻了
112917
Eason_AC楼主2021/3/15 14:47

RT,对着题解调死活都是全部 TLE,弄了大半天了都不知道问题出在哪里,还请各位大佬帮忙看看kl

// Version 2.2.5 by Eason_AC
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <ctime>
#include <set>
#include <queue>
#define F(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define R(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define E for(int i = h[x]; i; i = e[i].nxt)
#define str(s, l) cin >> (s); int (l) = (s).size()
#define crstr(s, l) string (s); cin >> (s); int (l) = (s).size()
#define crstrline(s, l) string (s); getline(cin, (s)); int (l) = (s).size()
#define ll long long //No long long see your ancestor!!!
#define ull unsigned long long //Have long long see your ancestor!!!
#define lll __int128 //Have unsigned long long see your ancestor!!!
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define yes puts("yes")
#define no puts("no")
#define iv inline void
#define ii inline int
#define ill inline ll
#define iull inline ull
#define i128 inline lll
#define ib inline bool

namespace fastIO {
	template<typename T>
	inline T read() {
		T f = 1, x = 0; char c = getchar();
		while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
		while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
		return x * f;
	}
#define Rint fastIO :: read<int>()
#define Rll fastIO :: read<ll>()
#define Rull fastIO :: read<ull>()
#define R128 fastIO :: read<lll>()

	template<typename T>
	inline void write(T x) {
		if(!x) {putchar('0'); return;}
		if(x < 0) {putchar('-'); x = -x;}
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
#define write(x) fastIO :: write((x))
}
using namespace std;
#define MT int t = Rint; while(t--)

const int N = 2e5 + 7;
int n, k, cnt, c[N], ans[N];
struct node {
	int a, b, c, val, ans;
}s[N], s2[N];

ib cmp1(const node& tmp1, const node& tmp2) {
	if(tmp1.a != tmp2.a) return tmp1.a < tmp2.a;
	if(tmp1.b != tmp2.b) return tmp1.b < tmp2.b;
	return tmp1.c < tmp2.c;
}
ib cmp2(const node& tmp1, const node& tmp2) {
	if(tmp1.b != tmp2.b) return tmp1.b < tmp2.b;
	return tmp1.c < tmp2.c;
}
ii lowbit(int x) {return x & (-x);}
iv update(int x, int v) {for(; x <= k; x += lowbit(x)) c[x] += v;}
ii sum(int x) {int res = 0; for(; x; x -= lowbit(x)) res += c[x]; return res;}
iv cdq(int l, int r) {
	if(l == r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid); cdq(mid + 1, r);
	sort(s2 + l, s2 + mid + 1, cmp2);
	sort(s2 + mid + 1, s2 + r + 1, cmp2);
	int i = mid + 1, j = l;
	for(; i <= r; ++i) {
		while(s2[j].b <= s2[i].b && j <= mid) update(s2[j].c, s2[j].val), ++j;
		s2[i].ans += sum(s2[i].c);
	}
	for(i = l; i < j; ++i) update(s2[i].c, -s2[i].val);
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = Rint, k = Rint;
	F(i, 1, n) s[i].a = Rint, s[i].b = Rint, s[i].c = Rint;
	sort(s + 1, s + n + 1, cmp1);
	int tmp = 0;
	F(i, 1, n) {
		tmp++;
		if(s[i].a != s[i + 1].a || s[i].b != s[i + 1].b || s[i].c != s[i + 1].c)
			s2[++cnt] = s[i], s2[cnt].val = tmp, tmp = 0;
	}
	cdq(1, n);
	F(i, 1, cnt) ans[s2[i].ans + s2[i].val - 1] += s2[i].val;
	F(i, 0, n - 1) write(ans[i]), puts("");
	return 0;
}
2021/3/15 14:47
加载中...