「YNOI2016」掉进兔子洞

发表于 | 分类于 | | 浏览量： 次

震惊！我妻由乃掉进了兔子洞里…

传送门

洛谷P4688

BZOJ4939

题解

这题再YNOI里应该算简单的吧，毕竟代码挺短的。

根据题意，要求的答案就是三个区间的长度和减去三个区间的交集长度的三倍。

因为要求交集，自然而然想到用bitset。只要上莫队求出每个询问的三个区间的bitset，求交集即可。

但是这个交集还不是那么好求，要拐个弯QwQ。

先对原序列进行离散化，定义离散化之后的$A_i$表示原序列中有多少个数小于原$A_i$。

然后考虑一个区间，现在加入一个元素，怎么维护bitset。由于存在相同元素，所以bitset上可能有好多位都是留给与当前元素相同的元素的，那么就需要从第$A_i$个位置从左往右找到第一个空位把新元素按上去，这样进行&运算的时候就没有问题了，找位置的时候事先记一下当前区间每个值已经出现多少次了，就能O(1)找到。

这样进行&运算就没有什么问题了。

还有就是由于直接开$10^5$个长度为$10^5$的bitset会MLE，所以把所有询问分三次处理就好了。

感觉莫队+bitset的题常数都不小，蒟蒻我一般不吸氧过不了QwQ。

代码

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
#include<map>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005,maxm=34005;
int n,tot,m,A[maxn],B[maxn],sum,S,Area[maxn],ans[maxn],cnt[maxn];map<int,int> C;bitset<maxn> col[maxm],tep;bool vis[maxm];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Interval
{
	int L,R,id;
	bool operator < (const Interval& b)const{return Area[L]<Area[b.L]||(Area[L]==Area[b.L]&&((Area[L]&1)?Area[R]<Area[b.R]:Area[R]>Area[b.R]));}
}Q[maxm*3];
inline void inc(int x){tep[x+cnt[x]]=1;cnt[x]++;}
inline void dec(int x){cnt[x]--;tep[x+cnt[x]]=0;}
inline void Solve()
{
	int num=0,L=1,R=1;tep[A[1]]=1;cnt[A[1]]++;
	for(int i=1;i<=m&&i<=34000;i++)
	{
		num++;Q[num].L=read();Q[num].R=read();Q[num].id=i;ans[i]+=Q[num].R-Q[num].L+1;
		num++;Q[num].L=read();Q[num].R=read();Q[num].id=i;ans[i]+=Q[num].R-Q[num].L+1;
		num++;Q[num].L=read();Q[num].R=read();Q[num].id=i;ans[i]+=Q[num].R-Q[num].L+1;
	}
	sort(Q+1,Q+1+num);
	for(int i=1;i<=num;i++)
	{
		while(L>Q[i].L) inc(A[--L]);
		while(R<Q[i].R) inc(A[++R]);
		while(L<Q[i].L) dec(A[L++]);
		while(R>Q[i].R) dec(A[R--]);
		if(vis[Q[i].id]) col[Q[i].id]&=tep;
		else{col[Q[i].id]=tep;vis[Q[i].id]=true;}
	}
	for(int i=1;i<=m&&i<=34000;i++)
	{
		ans[i]-=col[i].count()*3;
		printf("%d\n",ans[i]);
	}
	m-=34000;memset(ans,0,sizeof(ans));memset(cnt,0,sizeof(cnt));memset(vis,0,sizeof(vis));tep.reset();
}
int main()
{
	n=read();m=read();S=sqrt(n)+1e-10;
	for(int i=1;i<=n;i++) A[i]=B[i]=read();
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	sort(B+1,B+1+n);
	for(int i=1,j;i<=n;i=j+1)
	{
		j=i;
		while(j<n&&B[j+1]==B[i]) j++;
		C[B[i]]=sum;sum+=j-i+1;
	}
	for(int i=1;i<=n;i++) A[i]=C[A[i]];
	while(m>0) Solve();
	return 0;
}