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

文章插图
#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;}完整代码
时间复杂度为m*n1/2，即n3/2，可以通过本题。
很多oier提到Ynoi都只知道充斥着acg的冗长题目背景和严苛的卡常，但是事实上这些题有很多都是很有研究价值的。