QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163518#7108. CouleurluanmengleiRE 2ms5464kbC++173.3kb2023-09-04 09:58:582023-09-04 09:58:58

Judging History

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

  • [2023-09-04 09:58:58]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:5464kb
  • [2023-09-04 09:58:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void debug(const char *msg, ...) {
#ifdef CLESIP
	va_list args;
	va_start(args, msg);
	static char res[512];
	vsprintf(res, msg, args);
	cerr << "[DEBUG] " << res << "\n";
	va_end(args);
#endif
}

using i64 = long long;
const int N = 1e5 + 10;
const int SEG_SIZE = N * 80;
int n, a[N], cnt, rt[N], p[N];
map<int, int> seg;
multiset<i64> ans;

struct Node {
	int cnt, tag, lc, rc, min, max;
	i64 sum;
} t[SEG_SIZE];

void pull(int x) {
	t[x].sum = 0, t[x].cnt = 0, t[x].min = n + 1, t[x].max = 0;
	if (t[x].lc) t[x].sum += t[t[x].lc].sum, t[x].cnt += t[t[x].lc].cnt, t[x].min = min(t[t[x].lc].min, t[x].min), t[x].max = max(t[t[x].lc].max, t[x].max);
	if (t[x].rc) t[x].sum += t[t[x].rc].sum, t[x].cnt += t[t[x].rc].cnt, t[x].min = min(t[t[x].rc].min, t[x].min), t[x].max = max(t[t[x].rc].max, t[x].max);
}

void apply(int x, int k) { t[x].sum += 1LL * t[x].cnt * k, t[x].tag += k; }

void push(int x) {
	if (t[x].tag) {
		if (t[x].lc) apply(t[x].lc, t[x].tag);
		if (t[x].rc) apply(t[x].rc, t[x].tag);
		t[x].tag = 0;
	}
}

void add(int &x, int l, int r, int v, int p, int sum) {
	if (!x) t[x = ++ cnt] = { 0, 0, 0, 0, n + 1, 0, 0 };
	if (l == r) {
		t[x] = { 1, 0, 0, 0, p, p, sum };
		return;
	}
	int mid = (l + r) >> 1;
	if (v <= mid) add(t[x].lc, l, mid, v, p, (t[x].rc ? t[t[x].rc].cnt : 0) + sum);
	else add(t[x].rc, mid + 1, r, v, p, sum);
	pull(x);
}

void extract(int &x, int &y, int k) {
	if (!y) return;
	// debug("min: %d max: %d cnt: %d", t[y].min, t[y].max, t[y].cnt);
	if (t[y].max <= k) {
		x = y;
		y = 0;
		return;
	}
	if (t[y].min > k) {
		x = 0;
		return;
	}
	push(y);
	t[x = ++ cnt] = { 0, 0, 0, 0, n + 1, 0, 0 };
	extract(t[x].lc, t[y].lc, k);
	extract(t[x].rc, t[y].rc, k);
	apply(t[y].lc, -t[t[x].rc].cnt);
	pull(x), pull(y);
}

void solve() {
	// debug("new test case");
	seg.clear(), ans.clear(), cnt = 0;

	cin >> n;
	for (int i = 1; i <= n; i ++) rt[i] = 0;
	for (int i = 1; i <= n; i ++) cin >> a[i], p[i] = i;
	sort(p + 1, p + 1 + n, [&](int x, int y) { return a[x] == a[y] ? x < y : a[x] < a[y]; });
	for (int i = 1; i <= n; i ++) a[p[i]] = i;

	// for (int i = 1; i <= n; i ++) debug("a[%d] = %d", i, a[i]);

	for (int i = 1; i <= n; i ++)
		add(rt[1], 1, n, a[i], i, 0);
	seg[1] = n, ans.insert(t[rt[1]].sum);

	// debug("sum: %d", t[rt[1]].sum);
	cout << t[rt[1]].sum << " ";
	int q = n, lst = t[rt[1]].sum;
	for (int i = 1; i <= q; i ++) {
		int p; cin >> p;
		p ^= lst;
		if (i == q) break;
		auto iter = prev(seg.upper_bound(p));
		auto [l, r] = *iter;
		seg.erase(iter);
		r += l - 1;
		// debug("p: %d l: %d r: %d", p, l, r);

		int rtl = 0, rtr = rt[l], tmp;
		ans.extract(t[rt[l]].sum);
		// debug("ans size: %d", ans.size());
		rt[l] = 0;
		extract(rtl, rtr, p - 1);
		extract(tmp, rtr, p);
		
		if (l <= p - 1) {
			// debug("left cnt: %d", t[rt[l]].cnt);
			rt[l] = rtl;
			seg[l] = p;
			ans.insert(t[rt[l]].sum);
		}
		if (p + 1 <= r) {
			// debug("right cnt: %d", t[rt[p + 1]].cnt);
			rt[p + 1] = rtr;
			seg[p + 1] = r;
			ans.insert(t[rt[p + 1]].sum);
		}
		cout << (lst = *prev(ans.end())) << " \n"[i + 1 == q];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
	while (tt --) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5464kb

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

11116
10
10 5 10 3 6 4 8 5 9 8
31 27 24 11 12 3 0 2 3 1
10
8 2 7 2 8 10 1 10 9 10
6 5 2 13 2 1 0 1 3 1
10
7 10 7 6 1 3 10 6 7 9
21 18 10 1 6 5 4 8 9 10
10
2 10 4 8 8 5 7 2 6 7
20 10 9 1 15 0 4 2 9 7
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
6 3 5 2 7 10 9 1 4 8
10
1 10 1 3...

output:

21 18 16 12 10 6 4 1 1 0
12 12 10 10 4 4 4 2 1 0
20 16 9 5 3 3 3 0 0 0
22 14 8 8 5 5 2 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
19 12 7 4 4 2 2 1 0 0
20 18 8 3 1 1 0 0 0 0
45 21 21 10 3 3 3 0 0 0
17 11 8 2 1 1 1 0 0 0
13 4 1 0 0 0 0 0 0 0
29 27 22 15 9 7 4 3 1 0
26 16 9 2 1 1 1 1 1 0
0 0 0 0 0 ...

result: