P4688 [Ynoi2016] 掉进兔子洞

, ,

Description

https://www.luogu.com.cn/problem/P4688

Solution

警戒！！！

观察到我们只需要对每个值统计三个区间中出现的最小值之和。

考虑 bitset。我们把每个值变成为这个值在这个区间中出现了多少次，如果出现了 $p$ 次，则 $[x,x+p-1]$ 都为 $1$。最后与起来就可以了。

也就是说我们要离散化（我们本来也要离散化），把每个数变成前面有多少个数小于它 $+1$，这样每个数也不会冲突。

赋值的话就莫对搞一搞。但是这题卡空间，所以把询问拆成 $3$ 遍做。

时间复杂度 $O(n\sqrt m+\dfrac{nm}{w})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,times=1,bm=33335,block;
int a[maxn],t[maxn];
struct yyy {
	int l,r,id;
}q[maxn*2];
int ansnums[maxn];
map<int,int>mp;
bitset<maxn>Ans[35005],s;
bool cmp(yyy x,yyy y) {return (x.l/block)!=(y.l/block)?x.l<y.l:x.r<y.r;}
void add(int x) {s[a[x]-t[a[x]]]=1,t[a[x]]++;}
void del(int x) {t[a[x]]--;s[a[x]-t[a[x]]]=0;}
void solve(void) {
	int i,tot=0,rr=0;
	for (i=1;i<=bm&&times<=m;i++,times++) {
		ansnums[i]=0;
		++tot;read(q[tot].l),read(q[tot].r),q[tot].id=i;ansnums[i]+=q[tot].r-q[tot].l+1;
		++tot;read(q[tot].l),read(q[tot].r),q[tot].id=i;ansnums[i]+=q[tot].r-q[tot].l+1;
		++tot;read(q[tot].l),read(q[tot].r),q[tot].id=i;ansnums[i]+=q[tot].r-q[tot].l+1;
		Ans[i].set();
		rr=i;
	} 
	if (!tot) return ;
	sort(q+1,q+1+tot,cmp);
	memset(t,0,sizeof(t));s.reset();
	int l=1,r=0,ql,qr;
	for (i=1;i<=tot;i++) {
		ql=q[i].l,qr=q[i].r;
		while (r<qr) r++,add(r);
		while (l>ql) l--,add(l);
		while (r>qr) del(r),r--;
		while (l<ql) del(l),l++;
		Ans[q[i].id]&=s;
	} 
	for (i=1;i<=rr;i++) printf("%d\n",ansnums[i]-3*(int)Ans[i].count());
}
signed main(void){
	int i;
	read(n);read(m);block=min((int)(n/sqrt(m))+5,300);
	for (i=1;i<=n;i++) read(a[i]),mp[a[i]]++;
	auto it=mp.begin(),it2=mp.begin();
	for (it2++;it2!=mp.end();it2++,it++) it2->se+=it->se;
	for (i=1;i<=n;i++) a[i]=mp[a[i]]; 
	solve();solve();solve();
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i