简单莫队模板求助

苍穹一粟 · 2025 年2 月 10 日 05:11

#include <bits/stdc++.h>
using lint = long long;
const int N = 1e5 + 10;

std::vector<lint> tmp;
lint now, a[N], cnt[N], ans[N];
std::unordered_map<lint, int> mp;
int n, q, tot, len, id[N], L[N], R[N];

struct Range {
	int l, r, p;
	
	bool operator<(Range x) const {
		return (id[l] ^ id[x.l]) ? id[l] < id[x.l] : r < x.r;
	}
} b[N];

void input() {
	std::cin >> n >> q, len = sqrt(n), tot = n / len;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i], tmp.push_back(a[i]);
	for (int i = 1; i <= q; ++i)
		std::cin >> b[i].l >> b[i].r, b[i].p = i;
	std::sort(b + 1, b + q + 1);
	for (int i = 1; i <= tot; ++i) {
		L[i] = len * (i - 1) + 1;
		R[i] = len * i;
	}
	if (R[tot] < n) {
		++tot;
		L[tot] = R[tot - 1] + 1;
		R[tot] = n;
	}
}

void discrete() {
	std::sort(tmp.begin(), tmp.end());
	for (size_t i = 0; i < tmp.size(); ++i)
		mp[tmp[i]] = i + 1;
}

void add(lint x, lint &u) {
	u = std::max(u, x * ++cnt[mp[x]]);
}

void del(lint x) {
	--cnt[x];
}

void work() {
	lint nnow;
	for (int i = 1, l = 1, r = 0, lst = 0, _l; i <= q; ++i) {
		int ql = b[i].l, qr = b[i].r;
		if (id[ql] == id[qr]) {
			for (int u = ql; u <= qr; ++u) ++cnt[mp[a[u]]];
			for (int u = ql; u <= qr; ++u)
				ans[b[i].p] = std::max(ans[b[i].p], a[u] * cnt[mp[a[u]]]);
			for (int u = ql; u <= qr; ++u) --cnt[mp[a[u]]];
			continue;
		}
		
		if (id[ql] != lst) {
			while (r > R[id[ql]]) del(mp[a[r--]]);
			while (l < R[id[ql]] + 1) del(mp[a[l++]]);
			now = 0, lst = id[ql];
		}
		
		while (r < qr) add(a[++r], now);
		nnow = now, _l = l;
		
		while (_l > ql) add(a[--_l], nnow);
		ans[b[i].p] = nnow;
		
		while (_l < l) del(mp[a[_l++]]);
	}
}

void output() {
	for (int i = 1; i <= q; ++i)
		std::cout << ans[i] << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	input();
	discrete();
	work();
	output();
	std::cout.flush();
	return 0;
}

TLE 了

提交记录：
https://loj.ac/s/2262737

苍穹一粟 · 2025 年2 月 10 日 05:20

离散化忘记去重了，但还是 TLE

#include <bits/stdc++.h>
using lint = long long;
const int N = 1e5 + 10;

std::vector<lint> tmp;
lint now, a[N], cnt[N], ans[N];
std::unordered_map<lint, int> mp;
int n, q, tot, len, id[N], L[N], R[N];

struct Range {
	int l, r, p;
	
	bool operator<(Range x) const {
		return (id[l] ^ id[x.l]) ? id[l] < id[x.l] : r < x.r;
	}
} b[N];

void input() {
	std::cin >> n >> q, len = sqrt(n), tot = n / len;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i], tmp.push_back(a[i]);
	for (int i = 1; i <= q; ++i)
		std::cin >> b[i].l >> b[i].r, b[i].p = i;
	std::sort(b + 1, b + q + 1);
	for (int i = 1; i <= tot; ++i) {
		L[i] = len * (i - 1) + 1;
		R[i] = len * i;
	}
	if (R[tot] < n) {
		++tot;
		L[tot] = R[tot - 1] + 1;
		R[tot] = n;
	}
}

void discrete() {
	std::sort(tmp.begin(), tmp.end());
	tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
	for (size_t i = 0; i < tmp.size(); ++i)
		mp[tmp[i]] = i + 1;
}

void add(lint x, lint &u) {
	u = std::max(u, x * ++cnt[mp[x]]);
}

void del(lint x) {
	--cnt[x];
}

void work() {
	lint nnow;
	for (int i = 1, l = 1, r = 0, lst = 0, _l; i <= q; ++i) {
		int ql = b[i].l, qr = b[i].r;
		if (id[ql] == id[qr]) {
			for (int u = ql; u <= qr; ++u) ++cnt[mp[a[u]]];
			for (int u = ql; u <= qr; ++u)
				ans[b[i].p] = std::max(ans[b[i].p], a[u] * cnt[mp[a[u]]]);
			for (int u = ql; u <= qr; ++u) --cnt[mp[a[u]]];
			continue;
		}
		
		if (id[ql] != lst) {
			while (r > R[id[ql]]) del(mp[a[r--]]);
			while (l < R[id[ql]] + 1) del(mp[a[l++]]);
			now = 0, lst = id[ql];
		}
		
		while (r < qr) add(a[++r], now);
		nnow = now, _l = l;
		
		while (_l > ql) add(a[--_l], nnow);
		ans[b[i].p] = nnow;
		
		while (_l < l) del(mp[a[_l++]]);
	}
}

void output() {
	for (int i = 1; i <= q; ++i)
		std::cout << ans[i] << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	input();
	discrete();
	work();
	output();
	std::cout.flush();
	return 0;
}

苍穹一粟 · 2025 年2 月 10 日 08:30

破案了，炸了一堆细节。

#include <bits/stdc++.h>
using lint = long long;
const int N = 1e5 + 10;

lint ans[N];
int siz, tot, id[N], L[N], R[N];
int n, m, q, x[N], y[N], cnt[N], _cnt[N];

struct Query {
	int l, r, pos;
	
	bool operator<(Query t) const {
		return (id[l] ^ id[t.l]) ? id[l] < id[t.l] : r < t.r;
	}
} a[N];

void build() {
	siz = sqrt(n), tot = n / siz;
	for (int i = 1; i <= tot; ++i) {
		L[i] = siz * (i - 1) + 1;
		R[i] = siz * i;
	}
	if (R[tot] < n) {
		++tot;
		L[tot] = R[tot - 1] + 1;
		R[tot] = n;
	}
	
	for (int i = 1; i <= tot; ++i)
		for (int j = L[i]; j <= R[i]; ++j)
			id[j] = i;
}

void add(int x, lint &u) {
	++cnt[x];
	u = std::max(u, 1ll * y[x] * cnt[x]);
}

void del(int x) {
	--cnt[x];
}

int main() {
	freopen("data.in", "r", stdin);
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> n >> q;
	for (int i = 1; i <= n; ++i) std::cin >> x[i], y[++m] = x[i];
	for (int i = 1; i <= q; ++i) std::cin >> a[i].l >> a[i].r, a[i].pos = i;
	build(); // 分块
	std::sort(a + 1, a + q + 1);
	std::sort(y + 1, y + m + 1);
	m = std::unique(y + 1, y + m + 1) - y - 1;
	for (int i = 1; i <= n; ++i)
		x[i] = std::lower_bound(y + 1, y + m + 1, x[i]) - y;
	
	lint Ans = 0, tmp;
	for (int i = 1, l = 1, r = 0, lst = 0, _l; i <= q; ++i) {
		int ql = a[i].l, qr = a[i].r;
		
		if (id[ql] == id[qr]) {
			for (int u = ql; u <= qr; ++u) ++_cnt[x[u]];
			for (int u = ql; u <= qr; ++u)
				ans[a[i].pos] = std::max(ans[a[i].pos], 1ll * y[x[u]] * _cnt[x[u]]);
			for (int u = ql; u <= qr; ++u) --_cnt[x[u]];
			continue;
		}
		
		if (id[ql] != lst) {
			while (r > R[id[ql]]) del(x[r--]);
			while (l < R[id[ql]] + 1) del(x[l++]);
			lst = id[ql], Ans = 0;
		}
		
		while (r < qr) add(x[++r], Ans);
		_l = l, tmp = Ans;
		
		while (_l > ql) add(x[--_l], tmp);
		ans[a[i].pos] = tmp;
		
		while (_l < l) del(x[_l++]);
	}
	
	for (int i = 1; i <= q; ++i) std::cout << ans[i] << "\n";
	std::cout.flush();
	return 0;
}