meaning of the title

P4688 [Ynoi2016] falls into a rabbit hole

Given a sequence with a length of \ (n \) and \ (m \) queries, each query gives \ (3 \) intervals \ ([l_1, r_1], [l_2, r_2], [l_3, r_3] \). Delete a common number in three intervals each time, and try to find the sum of the numbers in the final three intervals. Inquiries are independent of each other.

Note that only one common number is deleted at a time, not all such numbers. For example, the three intervals are \ ([1, 2, 2, 3, 3, 3, 3], [1, 2, 2, 3, 3, 3], [1, 1, 2, 3, 3] \), and only \ (1 \), \ (1 \) and \ (2 \) will be deleted in the end.

\(1 \leq n, m \leq 10^5, 1 \leq a_i \leq 10^9\)

thinking

Convert to: Mo team + bitset.

It is difficult to maintain three intervals with Mo team at the same time. Consider transforming them into three intervals with Mo team, and finally merge the answers.

Suppose that the number of \ (k \) will be deleted in the end. Obviously, the answer is \ ((r_1 - l_1 + 1) + (r_2 - l_2 + 1) + (r_3 - l_3 + 1) - 3k \), and the problem is transformed into finding the number of deleted numbers in the end.

It is found that the above problem is actually to find the minimum number of times a specific value appears in multiple intervals, which is difficult to maintain directly with Mo team. The observation data range, \ (a_i \leq 10^9 \), obviously needs to be discretized. The breakthrough of the whole problem lies in the special treatment of discretization, which is transformed into bitset optimization team.

It is advisable to discretize \ (a_i \) into the number of values less than or equal to \ (a_i \) in the whole sequence, so bitset can be used to optimize the Mo team for maintenance.

Practice:

Split each operation into three queries.

Let \ (c_p \) indicate the number of occurrences of the median value \ (P \) in the current interval. You can maintain a bitset for each operation and a bitset for the current interval to indicate whether each value has occurred. When the endpoint moves, if a new number \ (x \) is added, make \ (x + c_x \) appear, and then \ (c_x + 1 \); On the contrary, \ (c_x - 1 \) and let \ (x + c_x \) be absent.

Finally, make the bitset of the current interval intersect with the bitset of the current operation. The number of \ (1 \) in the final bitset is the number of the final deleted number.

Principle:

The original same value is discretized to get different values, that is, the same value is represented by a continuous subscript. Now the discretized season \ (a_i \) is the number of numbers less than or equal to \ (a_i \) in the sequence. In fact, the index used is initialized as the starting index, and \ (x + c_x \) is the index used now. When the subscript in bitset is \ (x + c_x \), it is \ (1 \), which is equivalent to that the value corresponding to order \ (x \) appears \ (1 \) more times. In this way, the final bitset crossing is to take the minimum number of occurrences for each value, and the number of \ (1 \) is the number of deleted values. On the contrary, the same is true.

Due to space constraints, the query needs to be divided into multiple segments.

code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 2.5e4 + 5;

int n, m;
int tot, cur;
int a[maxn], b[maxn];
int bel[maxn], cnt[maxn], ans[maxm];
bool flag[maxn];
bitset<maxn> res[maxm], vis;

struct node {
	int l, r, id;
	
	bool operator < (const node& rhs) const {
		if (bel[l] ^ bel[rhs.l]) {
			return bel[l] < bel[rhs.l];
		}
		return (bel[l] & 1 ? r < rhs.r : r > rhs.r);
	}
} q[maxn];

namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}

using IO::read;
using IO::write;
using IO::flush;
using IO::putc;

inline void work(int tot) {
	int l = 1, r = 0, len = 0;
	vis.reset();
	memset(ans, 0, (tot + 1) * sizeof(int));
	memset(cnt, 0, (n + 1) * sizeof(int));
	memset(flag, false, (n + 1) * sizeof(bool));
	for (int i = 1; i <= tot; i++) {
		for (int j = 1; j <= 3; j++) {
			len++;
			q[len].l = read(), q[len].r = read();
			q[len].id = i;
			ans[i] += (q[len].r - q[len].l + 1);
		}
	}
	sort(q + 1, q + len + 1);
	for (int i = 1; i <= len; i++) {
		while (l > q[i].l) {
			l--;
			vis[a[l] + cnt[a[l]]] = true;
			cnt[a[l]]++;
		}
		while (r < q[i].r) {
			r++;
			vis[a[r] + cnt[a[r]]] = true;
			cnt[a[r]]++;
		}
		while (l < q[i].l) {
			cnt[a[l]]--;
			vis[a[l] + cnt[a[l]]] = false;
			l++;
		}
		while (r > q[i].r) {
			cnt[a[r]]--;
			vis[a[r] + cnt[a[r]]] = false;
			r--;
		}
		if (!flag[q[i].id]) {
			res[q[i].id] = vis;
			flag[q[i].id] = true;
		} else {
			res[q[i].id] &= vis;
		}
	}
	for (int i = 1; i <= tot; i++) {
		ans[i] -= res[i].count() * 3;
		write(ans[i]);
		putc('\n');
	}
}

int main() {
	n = read(), m = read();
	int block = sqrt(n);
	for (int i = 1; i <= n; i++) {
		a[i] = read();
		b[i] = a[i];
		bel[i] = (i - 1) / block + 1;
	}
	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;
	}
	while (m) {
		if (m < (maxm - 5)) {
			work(m);
			break;
		}
		work(maxm - 5);
		m -= (maxm - 5);
	}
	flush();
	return 0;
}