题解 [email protected]洛谷 【[Ynoi2016]掉进兔子洞】

题意已经足够清楚了,我们直接说思路:


前置知识:

  • 分块、莫队
  • 离散化
  • 一些奇奇怪怪的技巧

根据题意三段区间的数的总和为 i=13(rili+1)3×k\sum_{i=1}^3(r_i-l_i+1)-3\times k,其中 kk 为三段区间内共有的数的个数。问题转化为求这个 kk 的值。

容易想到,我们使用莫队维护查询的区间内每个数的个数。对于一次询问,我们将其拆成传统莫队的三个询问:(l1,r1),(l2,r2),(l3,r3)(l_1,r_1),(l_2,r_2),(l_3,r_3),分别进行处理。我们要得到 kk,需要得到这三个询问中有哪些数、分别几个,然后取它们的交集即可。

那么问题来了,这个交集(或三次询问)怎么求呢?注意一个数可能重复出现多次。我们考虑先将初始 aa 数组进行离散化,只记录 aa 数组每一个值对应排序好的数组的编号即可。这样,若干个相同的数便会留出若干个空着的编号,它们代表同一个值。然后使用这个离散化的对应关系用 bitset 存即可。

完结撒花!

等等,Ynoi 可不是这么简单就过去的。看一眼数据范围,1n,m1051\le n,m\le 10^5。bitset 存不下!(笑容逐渐凝固)

没关系,我们可以把输入的查询分为若干组,每组 2×1042\times 10^4 个数(当然更大也可以,不炸空间就没事),对于每一组分别进行处理即可。

小细节:莫队必须先进队再出队! 我因为一开始顺序搞混一直 RE,被卡了 1.5h!

真·完结撒花!


主要代码:

const ll N = 1e5+5, M = 2e4, K = M+5, SIZE = 320;
ll n, m, a[N], b[N], s[N];
ll vis[N], len[N];
bitset<N> cnts[K], u;
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Node {
	ll l, r, id;
	friend bool operator < (const Node &a, const Node &b) {
		ll x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];

void discretization() {
	for(ll i=1;i<=n;i++) {
		scanf("%lld", &a[i]);
		b[i] = a[i];
	}
	sort(b+1, b+1+n);
	for(ll i=1;i<=n;i++) a[i] = ll(lower_bound(b+1, b+1+n, a[i]) - b);
}
void modify(ll x, ll y) {
	ll z = a[x];
	if(y == -1) u[z+(--s[z])] = 0;
	else u[z+(s[z]++)] = 1;
}
void solve(ll op) {
	assert(op > 0);
	ll tot = 0;
	memset(s, 0, sizeof(s));
	for(ll i=1;i<=op;i++) {
		vis[i] = len[i] = 0;
		for(ll j=1;j<=3;j++) {
			q[++tot].id = i;
			scanf("%lld%lld", &q[tot].l, &q[tot].r);
			len[i] += q[tot].r - q[tot].l + 1;
		}
	}
	sort(q+1, q+1+tot);
	ll l = 1, r = 0;
	u.reset();
	for(ll i=1;i<=tot;i++) {
		while(l > q[i].l) modify(--l, 1);
		while(r < q[i].r) modify(++r, 1);
		while(l < q[i].l) modify(l++, -1);
		while(r > q[i].r) modify(r--, -1);
		if(vis[q[i].id]) cnts[q[i].id] &= u;
		else cnts[q[i].id] = u;
		vis[q[i].id] = 1;
	}
	for(ll i=1;i<=op;i++) printf("%lld\n", len[i]-3*(ll)cnts[i].count());
}