带权bitset?/bitset优化莫队模板洛谷P4135 Ynoi2016 掉进兔子洞题解 _生活百科

题面。

看到这道题，我第一反应就是莫队。
我甚至也猜出了把所有询问的三个区间压到一起处理然后分别计算对应询问答案。
但是，这么复杂的贡献用什么东西存？难道要开一个数组 query_appear_time[ 100000 ][ 100000 ]?
于是我打消了这个念头，最后还是看题解做的。

简化题意：给一个序列，给一些询问，每个询问包含三个区间代表序列的三个子序列，要求出这三个对应子序列去掉三个子序列都具有的公共数字后剩下的数字个数。
令三个区间为a1,a2,a3 。
要求的答案就是a1数字个数-公共数字个数+a2数字个数-公共数字个数+a3数字个数-公共数字个数。
即a1，a2，a3数字个数之和-公共数字个数*3 。
数字个数之和就是区间长度，那么问题就转化为了求三个区间的公共数字个数。
对序列进行离散化，原本的1e9值域就变成了1e5值域。
然后读入所有的询问区间按标准莫队进行排序，处理每个区间并且将其所有的数字出现个数转移到对应询问中。接下来合并。
到这一步其实并不难想，关键在于怎么求公共数字个数。
前面我提到显然存不了一个query_appear_time[ 100000 ][ 100000 ]，但是有一个数据结构叫bitset 。
bitset的一位只占一个比特，相当于一个二进制数，可以进行位运算。
我们可以用bitset一位代表一个数字存储区间内值域，这在洛谷3674小清新人渣的本愿中十分有用。
但是这题要存储区间每个数字个数。
做法：
我们令p[i]为整个序列内小于等于i的数字的个数，cnt[i]为数字i在当前区间中出现的次数，建一个bitset<1e5>range 。
每当读入一个数字x我们令range[p[x]-cnt[x]]为1并令cnt[x]++ ，每当查询完一个区间我们用这样一个bitset记录这个区间。
代表两个区间的bitset与（&）一下然后用range.count()求出新bitset的1个数，就是这两个区间的公共数字个数。
原理：
如下图
对于一个区间，对于数字i，这个区间的bitset第p[ i ]位到第p[ i ]-cnt[ i ]位为1 ，公共数字个数就是min(cnt[i])
那么对于两个数的min(cnt[i]) ， p[i]~p[i]-min(cnt[i])+这个范围肯定全是1.
取与之后，p[ i ]~p[i-1]+1位的1的数量就是公共的i的出现次数。

带权bitset?/bitset优化莫队模板洛谷P4135 Ynoi2016 掉进兔子洞题解

文章插图
至于计算每个区间的bitset，这么一大堆区间放在一起，显然可以莫队。
然后分别计算每个区间的bitset ，再对每个询问，将其三个区间的bitset与起来求1的个数，就是这个询问所要求的三个区间的公共元素数量。
莫队操作，tmp为当前区间状态。
for(int i=2;i<=m;i++){while(l>q[i].l)l--,tmp[p[a[l]]-tim[a[l]]]=1,tim[a[l]]++;while(r<q[i].r)r++,tmp[p[a[r]]-tim[a[r]]]=1,tim[a[r]]++;while(l<q[i].l)tim[a[l]]--,tmp[p[a[l]]-tim[a[l]]]=0,l++;while(r>q[i].r)tim[a[r]]--,tmp[p[a[r]]-tim[a[r]]]=0,r--;if(!vis[(q[i].pos-1)/3+1])res[(q[i].pos-1)/3+1]=tmp,vis[(q[i].pos-1)/3+1]=1;//神奇的O(1)复制elseres[(q[i].pos-1)/3+1]&=tmp;}合并答案
for(int i=1;i<=m;i++){int pub=res[i].count();printf("%d\n",cnt[i]-pub*3);}至此，我们已经得到了一个时间复杂度n3/2的莫队算法。
但是还有一个问题。
bitset虽然小，但是一个bitset要开1e5位。这样的bitset开不了题目要求的1e5个（每个询问要存三个区间）。
那么就只开询问数量的一部分（我开的1/4）的bitset，然后一次处理问题的一小部分就可以了。

文章插图

文章插图
#include<bits/stdc++.h>using namespace std;const int h=100070;int n,m;int a[h],line[h];int p[h];map<int,int>rk;int ntot=0;bool vis[h/4+10];bitset<100010>res[h/4+10];bitset<100010>tmp;int len;int get_pos(int x){return (x-1)/len+1;}struct node{int l,r;int pos;}q[h];bool cmp(node x,node y){if(get_pos(x.l)==get_pos(y.l))return x.r<y.r;return x.l<y.l;}int tim[h];int ans;int part;int cnt[h];void solve(){if(!part)return;tmp.reset();for(int i=1;i<=part;i++)cnt[i]=0,res[i].reset(),vis[i]=0;len=sqrt(part);for(int i=1;i<=part*3;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].pos=i,cnt[(i-1)/3+1]+=q[i].r-q[i].l+1;sort(q+1,q+part*3,cmp);int l=q[1].l,r=q[1].r;for(int i=l;i<=r;i++)tmp[p[a[i]]-tim[a[i]]]=1,tim[a[i]]++;vis[(q[1].pos-1)/3+1]=1,res[(q[1].pos-1)/3+1]=tmp;for(int i=2;i<=part*3;i++){while(l>q[i].l)l--,tmp[p[a[l]]-tim[a[l]]]=1,tim[a[l]]++;while(r<q[i].r)r++,tmp[p[a[r]]-tim[a[r]]]=1,tim[a[r]]++;while(l<q[i].l)tim[a[l]]--,tmp[p[a[l]]-tim[a[l]]]=0,l++;while(r>q[i].r)tim[a[r]]--,tmp[p[a[r]]-tim[a[r]]]=0,r--;if(!vis[(q[i].pos-1)/3+1])res[(q[i].pos-1)/3+1]=tmp,vis[(q[i].pos-1)/3+1]=1;elseres[(q[i].pos-1)/3+1]&=tmp;}for(int i=1;i<=part;i++){int pub=res[i].count();printf("%d\n",cnt[i]-pub*3);}for(int i=1;i<=ntot;i++)tim[i]=0;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),line[i]=a[i];sort(line+1,line+1+n);for(int i=1;i<=n;i++)if(line[i]!=line[i-1])rk[line[i]]=++ntot,p[ntot-1]=i-1;p[ntot]=n;for(int i=1;i<=n;i++)a[i]=rk[a[i]];part=h/4;while(m)part=min(part,m),solve(),m-=part;return 0;}