[Ynoi2016] 掉进兔子洞

\(\text{Solution}\)

莫队配合 \(\text{bitset}\)

发现答案困难的部分在于同一个数在三个区间出现次数的最小值

考虑强行拆开看，用莫队处理出每个区间每个数的出现次数，这个可以用 \(\text{bitset}\)

然后取 \(\min\) 相当于每个询问涉及的三个区间的 \(\text{bitset}\) 并起来

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <bitset>

#define IN inline

using namespace std;

template <typename T>

IN void read(T &x) {

	x = 0; char ch = getchar(); int f = 0;

	for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());

	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

	if (f) x = ~x + 1;

}

typedef long long LL;

const int N = 1e5 + 3;

int a[N], n, m, B, cnt[N], ans[N], num, now, b[N];

struct Que{int l, r, id;}Q[N];

IN bool cmp(Que a, Que b){return (a.l / B ^ b.l / B) ? (a.l < b.l) : ((a.l / B & 1) ? a.r < b.r : a.r > b.r);}

bitset<N> S[N / 3 + 2], cur;

IN void add(int x){cur.set(a[x] + cnt[a[x]]), ++cnt[a[x]];}

IN void del(int x){--cnt[a[x]], cur.reset(a[x] + cnt[a[x]]);}

IN void solve() {

	B = n / sqrt(2.0 * num / 3) + 1, cur.reset();

	for(int i = 1; i <= n; i++) cnt[i] = 0;

	for(int i = 1; i <= now; i++) S[i].set();

	sort(Q + 1, Q + num + 1, cmp);

	for(int i = 1, l = 1, r = 0; i <= num; i++) {

		while (l > Q[i].l) add(--l);

		while (r < Q[i].r) add(++r);

		while (l < Q[i].l) del(l++);

		while (r > Q[i].r) del(r--);

		S[Q[i].id] &= cur;

	}

	for(int i = 1; i <= now; i++) printf("%d\n", ans[i] - (int)S[i].count() * 3);

}

int main() {

	read(n), read(m);

	for(int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];

	sort(b + 1, b + n + 1);

	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;

	num = now = 0;

	for(int i = 1; i <= m; i++) {

		ans[++now] = 0;

		for(int j = 0; j < 3; j++)

			++num, read(Q[num].l), read(Q[num].r), ans[Q[num].id = now] += Q[num].r - Q[num].l + 1;

		if (now == m / 3 || i == m) solve(), num = now = 0;

	}

}

巴特西

[Ynoi2016] 掉进兔子洞

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章