WA on #19 to #33 求调
查看原帖
WA on #19 to #33 求调
765958
lottle1212楼主2024/6/10 22:31

照着 @jr_zch 的题解写的,为了调试几乎快改得一模一样了,求大佬帮助

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define int long long
#define db double
#define ls p << 1
#define rs p << 1 | 1
#define L(i, j, k) for (int i = (j); i <= (k); ++ i)
#define R(i, j, k) for (int i = (j); i >= (k); -- i)
#define mp(x, y) make_pair(x, y)
#define pii pair <int, int>
#define vi vector <int>
#define eb emplace_back
#define pb push_back
#define sz(v) ((int) v.size())
#define mem(f, x) memset(f, x, sizeof (f))
using namespace std;
template <typename INT> void rd(INT &res) {
	res = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	res = (f ? -res : res);
}
template <typename INT, typename ...Args>
void rd(INT &res, Args &..._res) { rd(res), rd(_res...); }
void get_ch(char &ch) {
	ch = getchar();
	while (ch == ' ' || ch == '\n') ch = getchar();
}
int get_ca(char *s) {
	int len = 0; char ch = getchar();
	while (ch == ' ' || ch == '\n') ch = getchar();
	while (ch != ' ' && ch != '\n') s[len ++] = ch, ch = getchar();
	return len;
}
void get_str(string &s) {
	s.clear(); char ch = getchar();
	while (ch == ' ' || ch == '\n') ch = getchar();
	while (ch != ' ' && ch != '\n') s.pb(ch), ch = getchar();
}
template <typename DB> void rd_db(DB &res) {
	res = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') res = res * 10 + (ch ^ 48), ch = getchar();
	if (ch == '.') {
		db mul = 1e-1; ch = getchar();
		while (ch >= '0' && ch <= '9') res = res + mul * (ch ^ 48), ch = getchar(), mul /= 10;
	}
	res = (f ? -res : res);
}
template <typename DB, typename ...Args>
void rd_db(DB &res, Args &..._res) { rd_db(res), rd_db(_res...); }
//xyy
const int maxn = 2e5;
const int N = maxn + 10;
set <int> del, now; map <int, int> id, vis; vi a[N];
int f[N], h[N], top, n, k, sz[N], tot;
struct SegmentTree { int l, r; vi t; } t[N << 2];
struct Merge_Info { int x, y, h; } stk[N << 1];
//myj
vi Em;
void build(int p, int l, int r) {
	t[p] = {l, r, Em};
	if (l == r) return ;
	int mid = l + r >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
}
void insert(int p, int l, int r, int x) {
	if (l <= t[p].l && t[p].r <= r) { t[p].t.eb(x); return ; }
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) insert(ls, l, r, x);
	if (r > mid) insert(rs, l, r, x);
}
int get_fa(int x) { return x == f[x] ? x : get_fa(f[x]); }
void merge(int x, int y) {
	int fx = get_fa(x), fy = get_fa(y);
	if (h[fx] > h[fy]) swap(fx, fy);
	stk[++ top] = {fx, fy, h[fy]};
	f[fx] = fy, h[fy] += (h[fx] == h[fy]), sz[fy] += sz[fx];
}
void solve(int p) {
	int pre = top;
	for (int i : t[p].t) {
		auto it = now.upper_bound(i);
		if (it != now.end() && abs(*it - i) <= k) merge(id[*it], id[i]);
		if (it != now.begin()) {
			-- it;
			if (abs(*it - i) <= k) merge(id[*it], id[i]);
		}
		now.insert(i);
	}
	if (t[p].l == t[p].r) for (int i : a[t[p].l]) printf("%lld\n", sz[get_fa(id[i])]);
	else solve(ls), solve(rs);
	for (int i : t[p].t) now.erase(i);
	while (top > pre) h[stk[top].y] = stk[top].h, f[stk[top].x] = stk[top].x, sz[stk[top].y] -= sz[stk[top].x], -- top;
}
signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	rd(n, k);
	build(1, 1, n);
	L(i, 1, n) {
		int opt, x;
		rd(opt, x);
		if (opt == 1) {
			if (!id[x]) id[x] = ++ tot;
			if (vis[x]) insert(1, vis[x], i, x), vis[x] = 0, del.erase(x);
			else vis[x] = i, del.insert(x);
		} else a[i].eb(x);
	}
	for (int i : del) insert(1, vis[i], n, i);
	L(i, 1, tot) f[i] = i, sz[i] = 1;
	solve(1);
	return 0;
}
2024/6/10 22:31
加载中...