QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#497802#6533. Traveling in CellsAndycraftWA 206ms4072kbC++144.6kb2024-07-29 18:10:452024-07-29 18:10:45

Judging History

你现在查看的是最新测评结果

  • [2024-07-29 18:10:45]
  • 评测
  • 测评结果:WA
  • 用时:206ms
  • 内存:4072kb
  • [2024-07-29 18:10:45]
  • 提交

answer

#define DEBUG 1
#define MULTI_TEST 1
#include <cassert>
#include <array>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
typedef long long LL;
typedef long double LF;
template <class T> using Arr = std::vector<T>;
template <class T> using Ptn = std::pair<T, T>;
const int MOD = 998244353;
const int INF = 0x3F3F3F3F;
#define MUL(u, v) (int)((LL)(u) * (v) % MOD)
inline int Pow(int a, int b) { int r = 1; for (; b > 0; b >>= 1, a = MUL(a, a)) if (b & 1) r = MUL(r, a); return r; }
inline int &Norm(int &x) { return x %= MOD; }
#define RNG(v) (v).begin(), (v).end()
#define FOR(i, s, t) for (int i = (s), i##_end = (t); i < i##_end; ++i)
#define ROF(i, s, t) for (int i = (s) - 1, i##_end = (t); i >= i##_end; --i)

template <class T>
void read(T &n) {
	n = 0;
	char ch;
	bool flag = false;
	do if ((ch = getchar()) == '-') flag = true;
	while (ch < '0' || ch > '9');
	for (; '0' <= ch && ch <= '9'; ch = getchar())
		n = (n << 1) + (n << 3) + ch - '0';
	if (flag)
		n = -n;
}

int rand() {
	static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
	int r = (int)rng();
	return r < 0 ? -r : r;
}
int rand(int l, int r) { return l + rand() % (r - l + 1); }

struct sum_seg_t {
	int n;
	Arr<LL> tr;
	sum_seg_t(Arr<int> a) : n(a.size()), tr(2 * n) {
		FOR(i, 0, n)
			tr[n + i] = a[i];
		for (int i = n - 1; i > 0; --i)
			tr[i] = tr[i << 1] + tr[i << 1 | 1];
	}
	void modify(int p, int v) {
		tr[p += n] = v;
		for (p >>= 1; p > 0; p >>= 1)
			tr[p] = tr[p << 1] + tr[p << 1 | 1];
	}
	LL sum(int l, int r) {
		LL ans = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) ans += tr[l++];
			if (r & 1) ans += tr[--r];
		}
		return ans;
	}
};

// 线段树上倍增这么难写 ()
struct map_seg_t {
	int n, sz;
	typedef std::unordered_map<int, int> htable;
	Arr<htable> tr;
	htable merge(const htable &u, const htable &v) {
		auto rt = u;
		for (auto [x, c] : v)
			rt[x] += c;
		return rt;
	}
	map_seg_t(Arr<int> c) : n(c.size()) {
		for (sz = 1; sz < n; sz <<= 1)
			;
		tr.resize(sz << 1);
		FOR(i, 0, n)
			tr[sz + i][c[i]] = 1;
		ROF(i, sz, 1)
			tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
	}
	void modify(int p, int c) {
		auto it = tr[p += sz].begin();
		int oldc = it->second;
		tr[p].erase(it);
		assert(tr[p].size() == 0);
		tr[p][c] = 1;
		for (p >>= 1; p > 0; p >>= 1) {
			--tr[p][oldc];
			++tr[p][c];
		}
	}
	static int count_cell(const htable &map, const Arr<int> &v) {
		int ans = 0;
		for (auto c : v)
			if (map.count(c))
				ans += map.at(c);
		return ans;
	}
	static inline int LB(int x) { return x & -x; }
	static inline bool leftmost(int x) { return x == LB(x); }
	static inline int prev_fa(int x) { return (x >> 1) - (~x & 1); }
	static inline int prev_son(int x) { return (x << 1) - 1; }
	static inline bool rightmost(int x) { return leftmost(x + 1); }
	static inline int next_fa(int x) { return (x >> 1) + (x & 1); }
	static inline int next_son(int x) { return (x << 1) + 2; }
	int findl(int p, const Arr<int> &v) {
		p += sz;
		int h = 1;
		do {
			for (; p % 2 == 1 && p > 1; p >>= 1)
				h <<= 1;
			if (count_cell(tr[p], v) != h) {
				while (p < sz) {
					p = p * 2 + 1;
					h >>= 1;
					if (count_cell(tr[p], v) == h)
						--p;
				}
				return p + 1 - sz;
			}
			--p;
		} while (!rightmost(p));
		return 0;
	}
	int findr(int p, const Arr<int> &v) {
		p += sz;
		int h = 1;
		do {
			for (; p % 2 == 0; p >>= 1)
				h <<= 1;
			if (count_cell(tr[p], v) != h) {
				while (p < sz) {
					p <<= 1;
					h >>= 1;
					if (count_cell(tr[p], v) == h)
						++p;
				}
				return p - 1 - sz;
			}
			++p;
		} while(p != (p & -p));
		return n - 1;
	}
};

void Solve() {
	int n, q;
	read(n); read(q);
	Arr<int> c(n), v(n);
	FOR(i, 0, n)
		read(c[i]);
	FOR(i, 0, n)
		read(v[i]);

	sum_seg_t sum_seg(v);
	map_seg_t map_seg(c);

	FOR(qq, 0, q) {
		int op;
		read(op);
		if (op == 1) {
			int p, x;
			read(p); read(x);
			map_seg.modify(p - 1, x);
		} else if (op == 2) {
			int p, x;
			read(p); read(x);
			sum_seg.modify(p - 1, x);
		} else {
			int x, k;
			read(x); read(k);
			--x;
			Arr<int> v(k);
			for (auto &x : v)
				read(x);
			int l = map_seg.findl(x, v);
			int r = map_seg.findr(x, v);
			// printf("[%d, %d] => %lld\n", l + 1, r + 1, sum_seg.sum(l, r + 1));
			printf("%lld\n", sum_seg.sum(l, r + 1));
		}
	}
}

int main() {
	int T;
#if MULTI_TEST
	scanf("%d", &T);
#else
	T = 1;
#endif
	while (T--)
		Solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4068kb

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:

100
110
1200
21211
100010
4000000

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 206ms
memory: 4072kb

input:

20000
15 15
1 1 3 3 2 3 3 3 3 3 2 3 2 3 3
634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831
3 6 4 1 3 5 10
3 5 7 1 2 3 4 5 9 10
3 4 3 3 8 9
2 13 608033129
3 15 2 3 5
1 9 3
3 8 4 1 3 7 10
2 6 727472865
3...

output:

2689089686
8377825475
1706073651
1439027604
2689089686
792730352
8904867081
8904867081
8270273108
831633445
692051585
2782432626
697783016
883944422
184057757
696388752
184057757
287523250
184057757
3240862145
2667693025
2614711258
4006992373
1767091974
5348541057
5348541057
390631780
2290216252
942...

result:

wrong answer 16th numbers differ - expected: '287523250', found: '696388752'