带修莫队 90pts WA on #3 求条玄关
查看原帖
带修莫队 90pts WA on #3 求条玄关
1436256
Zyhx楼主2025/8/2 10:47

WA on Test3,提交记录,报错信息为 Too short on line 676,马蜂清奇,见谅

#include<bits/stdc++.h>
using namespace std;
static int T;
#define reg register
#define _ 7
#define __ 2000007
#define ___ 0x3f3f3f3f
#define pb emplace_back
#define sz(x) ((int)(x.size()))
#define mem(a,x) memset(a,x,sizeof(a))
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define endl '\n'
#define debug cerr<<"LINE:          "<<__LINE__<<endl
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
#define int long long
const int M = 998244353, M1 = 1e9 + 7, M2 = 1e9 + 9, N = (1 << 21) + 7, inf = 0x3f3f3f3f;
using ll = long long;
using ull = unsigned long long;
using vt = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tll = __int128_t;
using db = double;
struct dat {
	int l, r, val, id, t;
} q[__], qr[__];
int n, m, bl[__], siz, tot[__], pos[__], curq, curr, nx, ans[__];
unordered_map<int, int>mp;
inline bool cmp(dat a, dat b) {
	return (bl[a.l] == bl[b.l] ? (bl[a.r] == bl[b.r] ? (bl[a.r] & 1 ? a.t > b.t : a.t < b.t) : (bl[a.l] & 1 ? bl[a.r] > bl[b.r] : bl[a.r] < bl[b.r])) : a.l < b.l);
}
inline void update(int x, int y) {
	if (q[x].l <= qr[y].l && qr[y].l <= q[x].r) ++tot[qr[y].r], --tot[pos[qr[y].l]];
	swap(pos[qr[y].l], qr[y].r);
}
signed main() {
#ifdef Zyhx
	freopen("hack.in", "r", stdin);
#endif
	ios::sync_with_stdio(0), cin.tie(0);
	int i, j, k, l, r, x, y, z, t;
	cin >> n >> m;
	siz = pow(n, 0.666666);
	for (i = 1; i <= n; ++i) {
		cin >> pos[i];
		if (!mp[pos[i]]) mp[pos[i]] = ++nx;
		pos[i] = mp[pos[i]], bl[i] = (i - 1) / siz + 1;
	}
	for (i = 1; i <= n; ++i) {
		char opt;
		cin >> opt;
		if (opt == 'Q') {
			cin >> x >> y >> z;
			if (!mp[z]) mp[z] = ++nx;
			q[++curq].l = x, q[curq].r = y, q[curq].val = mp[z], q[curq].id = curq, q[curq].t = curr;
		} else {
			cin >> x >> y;
			if (!mp[y]) mp[y] = ++nx;
			qr[++curr].l = x, qr[curr].r = mp[y];
		}
	}
	stable_sort(q + 1, q + curq + 1, cmp);
	for (i = l = 1, r = t = 0; i <= curq; ++i) {
		for (; r < q[i].r; tot[pos[++r]]++);
		for (; r > q[i].r; --tot[pos[r--]]);
		for (; l < q[i].l; --tot[pos[l++]]);
		for (; l > q[i].l; tot[pos[--l]]++);
		for (; t < q[i].t; update(i, ++t));
		for (; t > q[i].t; update(i, t--));
		ans[q[i].id] = tot[q[i].val];
	}
	for (i = 1; i <= curq; ++i) cout << ans[i] << endl;
	return 0;
}

2025/8/2 10:47
加载中...