[Ynoi2016]掉进兔子洞题解

﹏ヽ暗。殇╰゛Y 2021-12-03 07:51 144阅读 0赞

题面传送门：[https://www.luogu.org/problemnew/show/P4688][https_www.luogu.org_problemnew_show_P4688]  
（温馨提示，请直接翻至题目描述部分）

1e5的数据范围，以及对区间每个权值出现次数取min此类主席树才能解决的操作会让我们想到莫队；  
三个区间取交集的操作会让我们想到bitset。  
然而同个数值在多个位置出现需要分别计算，这点让我们对于使用bitset产生了怀疑。  
但实际上我们可以利用一个小trick来解决这个问题，那就是利用不寻常的离散化，就是sort之后不用unique，让bitset每一位不只代表数值，还代表这个数值出现的次数。  
这样我们莫队的时候，对于当前区间维护一个桶cnt，记录每个离散化后的权值在此区间出现的次数，和一个bitset，维护权值及权值出现的次数信息。然后三个区间的bitset取交，再用三个区间的长度和减去交集1的个数就是答案。  
具体实现请看代码：

#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(register int i=(a);i<=(b);++i) const int N =100505; const int M =33350; int n,m,blo[N],K,a[N],R; struct la{int l,r,id;}ask[N]; bitset<N> ans[M],now; int cnt[N],p[N],tot; bool cmp(la x,la y){ return blo[x.l]==blo[y.l]?x.r<y.r:blo[x.l]<blo[y.l]; } inline void del(int x){cnt[x]--;now[x-cnt[x]]=0;} inline void add(int x){now[x-cnt[x]]=1;cnt[x]++;} void doit(int y){ tot=0; rep(i,1,y)p[i]=0; rep(i,1,y){ ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1; ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1; ++tot;scanf("%d%d",&ask[tot].l,&ask[tot].r);p[i]+=ask[tot].r-ask[tot].l+1; ask[tot].id=ask[tot-1].id=ask[tot-2].id=i; } sort(ask+1,ask+tot+1,cmp); int l=1,r=0; rep(i,1,y)ans[i].set();//不用带参，直接全置为 1 rep(i,1,tot){ while(ask[i].l<l)add(a[--l]); while(ask[i].r>r)add(a[++r]); while(ask[i].l>l)del(a[l++]); while(ask[i].r<r)del(a[r--]); ans[ask[i].id]&=now; } while(l<=r)del(a[l++]); rep(i,1,y)printf("%d\n",p[i]-3*(int)ans[i].count()); } int main(){ scanf("%d%d",&n,&m);K=sqrt(n)+1; rep(i,1,n)scanf("%d",&a[i]),p[i]=a[i],blo[i]=(i-1)/K+1; sort(p+1,p+n+1); rep(i,1,n)a[i]=upper_bound(p+1,p+n+1,a[i])-p-1; R=m/3; if(R)doit(R); if(R)doit(R); doit(m-2*R); return 0; }

转载于:https://www.cnblogs.com/Sinuok/p/11003961.html

[https_www.luogu.org_problemnew_show_P4688]: https://www.luogu.org/problemnew/show/P4688