P4688 [Ynoi Easy Round 2016] 掉进兔子洞 题解

前言

• wang79：你快去做那个 Ynoi
• msjing：行
• 原题
• oiwiki

solve

• 我们看题，让维护三个区间，删除并集，算剩余
• 我们考虑模拟，这个复杂度飞起来，我们不考虑
• 我们发现这个东西可以转化，我们不再删除并集，而是求出并集，再利用三个区间长度减去三倍的并集长度就是答案，e，这个比较显然
• 那我们考虑如何维护
• 我们发现维护的实际上是一个数在区间的出现情况，这个东西可以用莫队维护，好多的这类题都是莫队维护
• 其实普通莫队就行，msjing当时想的回滚
• 我们已经解决了统计区间数的统计，考虑求并集
• 我们假设已经求出了三个区间的数，考虑如何快速表示它们的并集，注意，我们并不需要找出具体的值，仅求出有几个即可，我们把每个数都设为互不相同，可以发现，如果我们用二进制位表示一个数有没有出现，我们仅需要对这仨进行与运算
• 这个与的实现就可以用 \(bitset\) 搞一下
• 我们发现一个集合的元素有重，我们可以转化一下，先做离散化（数太大了 \(bitset\) 开不下），然后我们把这个数离散化后的权值加上它在区间出现的次数就行
• 莫队操作时，我们在加入操作时向 \(bitset\) 中加入这个数离散化后的权值加上它在区间出现的次数，删除操作相反
• 注意莫队的顺序，先加后删
• 然后你就可以愉快的 A 掉被卡了
• 你发现 \(bitset\) 在 \(n = 10^5\) 的情况下开不了 \(n^2\)，所以我们可以直接把询问分三块干，就是每次要记得清
• 实现还好，就是msjing块分假了

快速看出解法的方法

1. 这是 Ynoi
2. 数据 \(10^5\)
3. 可离线

• 结论 \(1\)：这是莫队

1. \(n^2 = 10^10\) 接近 \(10^9\)
2. \(bitset\) 可以创 \(64\) 常数

• 结论 \(2\)：\(bitset\) 优化一下

• 代码参考 \(oiwiki\)，可能有大量调试没删导致看起开很长，不太卡常，大概跑 \(400MB\)

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define chk cerr << "------------------" << endl;
constexpr int maxn=1e5+10,maxm=maxn/3+10;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch == '-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
int n,m;
int a[maxn],b[maxn],col[maxn];
int cnt,L[maxn],R[maxn],pos[maxn];
bitset<maxn> s[maxm],nw;
struct _ {int l,r,id;}q[maxn];
int ans[maxn];
void add(int x)
{nw.set(x+col[x]);col[x]++;
}void del(int x)
{col[x]--;nw.reset(x+col[x]);
}
void inpt()
{n=read(),m=read();for (int i=1;i<=n;i++)a[i]=b[i]=read();sort(b+1,b+1+n);for (int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+n,a[i])-b;// for (int i=1;i<=n;i++) cerr << a[i] << " ";// cerr << endl;
}
void init()
{int b=n/sqrt(m)+1;cnt=n/b;for (int i=1;i<=cnt;i++){L[i]=b*(i-1)+1;R[i]=b*i;}if (R[cnt]<n){cnt++;L[cnt]=R[cnt-1]+1;R[cnt]=n;}for (int i=1;i<=cnt;i++)for (int j=L[i];j<=R[i];j++)pos[j]=i;
}
void sol()
{memset(col,0,sizeof(col));nw.reset();int t=0,tot=0;// cerr << m << endl;// for (int i=0;i<=3;i++) cerr << ans[i] << endl;for (t=0;t<maxm-10 && m;t++){m--;ans[t]=0,s[t].set();for (int j=1;j<=3;j++){int l=read(),r=read();// cerr << endl;// cerr << l << " " << r<< endl;q[++tot]={l,r,t};ans[t]+=r-l+1;}// cerr << m << endl;}// for (int i=0;i<t;i++) cerr << ans[i] << " ";// cerr << endl;// cerr << "t:" << t << endl;sort(q+1,q+1+tot,[](_ &a,_ &b){int p=pos[a.l],q=pos[b.l];if (p!=q) return p<q;if ((p&1) == 1) return a.r<b.r;else return a.r>b.r;});// for (int i=1;i<=tot;i++)//     cerr << q[i].l << " " << q[i].r << " " << q[i].id << endl;int l=1,r=0;for (int i=1;i<=tot;i++){// cerr << l << " " << r << endl;while (l>q[i].l) add(a[--l]);while (r<q[i].r) add(a[++r]);while (l<q[i].l) del(a[l++]);while (r>q[i].r) del(a[r--]);s[q[i].id]&=nw;}for (int i=0;i<t;i++) printf("%d\n",ans[i]-(int)s[i].count()*3);
}
int main()
{// freopen("xp1.in","r",stdin);// freopen("787878.out","w",stdout);inpt(),init();sol(),sol(),sol();return 0;
}

后话

• wang79 快来看！