萌新求助分块水题
  • 板块P4135 作诗
  • 楼主SIXIANG32
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/15 17:36
  • 上次更新2023/10/28 03:41:55
查看原帖
萌新求助分块水题
298549
SIXIANG32楼主2022/4/15 17:36

如题,全 WA,真的调不出来了嗷嗷嗷嗷嗷啊

也不知道哪里犯了弱智错误,但是真的调不出来。

码风清新(?),希望巨佬能帮个忙 awa

#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 125000
#define QWQ cout << "qwq" << endl;
using namespace std;
int n, m, CCC, cnt;
int a[MAXN + 10];
int pl[MAXN + 10], pr[MAXN + 10], cl[MAXN + 10], len;
int c[1000 + 10][MAXN + 10];
int f[1000 + 10][1000 + 10];
int ans;
void qwq(int l, int r, int num) {
	if((c[r][num] - c[l - 1][num]) == 0) {c[r][num]++; return ;}
	else if((c[r][num] - c[l - 1][num]) % 2 == 0) ans--;
	else ans++;
	c[r][num]++;
}
int solve(int l, int r) {
	int L = cl[l], R = cl[r];
	int x = 0, y = 0;
	if(L + 1 <= R - 1) x = L + 1, y = R - 1;
	ans = f[x][y];
//	cout << ans << endl;
	if(L == R) {
		for(int p = l; p <= r; p++) qwq(x, y, a[p]);
		for(int p = l; p <= r; p++) c[y][a[p]]--;
	}
	else {
		for(int p = l; p <= pr[L]; p++) qwq(x, y, a[p]);
		for(int p = pl[R]; p <= r; p++) qwq(x, y, a[p]);
		for(int p = l; p <= pr[L]; p++) c[y][a[p]]--;
		for(int p = pl[R]; p <= r; p++) c[y][a[p]]--;
	}
	return ans;
}
void block() {
	len = sqrt(n);
	for(int p = 1; p <= ceil(n * 1.0 / len); p++) {
		pl[p] = (p - 1) * len + 1;
		pr[p] = p * len;
	}
	for(int p = 1; p <= n; p++)
		cl[p] = (p - 1) / len + 1;
	for(int p = 1; p <= ceil(n * 1.0 / len); p++) {
		int t = 0;
		for(int i = pl[p]; i <= n; i++) {
			c[p][a[i]]++;
			
			if(c[p][a[i]] > 1)
				if(c[p][a[i]] % 2 == 0) t++;
				else t--;
			
			if(cl[i] != cl[i + 1])
			f[p][cl[i]] = t;
		} 
	}
}
int main() {
	//freopen("test.txt", "r", stdin);
	//freopen("taxt.txt", "w", stdout);
	cin >> n >> CCC >> m;
	for(int p = 1; p <= n; p++) cin >> a[p];
	block();
	int last = 0;
	while(m--) {
		int x, y;
		cin >> x >> y;
		x = (x + last) % n + 1, y = (y + last) % n + 1;
		if(x > y) swap(x, y);
		last = solve(x, y);
		cout << last << endl;
	}
}
2022/4/15 17:36
加载中...