YNOI 的大手

WZH2026-04-292026-04-30

大战 YNOI ——我真的会数据结构吗（一）

YNOI 的题目非常毒瘤……数据结构天花板。

——我。

T1 ：[Ynoi Easy Round 2016] 掉进兔子洞

题目链接： [Ynoi Easy Round 2016] 掉进兔子洞。

题目内容：

给定一个序列，每次给三个区间 $[l_1,r_1],[l_2,r_2],[l_3,r_3]$ ，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。

序列长度 $n \le 10^5$ ，询问次数 $m \le 10^5$ 。

时间限制 $3s$ ，空间限制 $500MB$ 。

第一眼看这个题目就可以感觉到我们之前学的知识，像线段树，是很难发挥作用的。

而这个题目主要是区间问题，那么第一想法自然是使用莫队暴力跑三个区间，复杂度 $O(n^\frac{11}{6})$ ，显然会炸。

那么此时就只能想办法把三个区间拆开了。

首先，原问题等价于求三个区间有多少个公共元素，如果我能求出每个区间每个元素是否出现过，然后再合并就行了。

看到合并，便可直接想到 bitset 维护。

但是这样就有了第一个问题： 如果有多个相同元素， bitset 怎么处理？

这就很考验离散化的基本功了。离散化的时候去重是为了省去重复元素所占空间，那么我只要不去重，就自然可以为某个元素出现一次，出现两次……预留出位置了。

但是还有一个问题，这样做会 MLE 。

为了解决这个问题，我们不妨看一下空间都在哪里消耗了。这自然是对于每个询问，我们为了这个而开的 bitset 。那么如果我能少开一点 bitset ，即，一次莫队少处理几次询问，多跑几次莫队，就可以不 MLE 了。

具体的，若莫队一次处理 $\frac{m}{k}$ 个询问，则一共要跑 $k$ 趟莫队，每趟莫队的时间复杂度为 $n\sqrt{\frac{m}{k}}=\frac{n\sqrt{km}}{k}$ ，空间复杂度为 $\frac{nm}{kw}$ ，那么总时间复杂度就是 $n\sqrt{km}$ ，空间复杂度为 $\frac{nm}{kw}$ 。代入 $n=m=10^5$ 可得 $k=3$ 或左右即可。

见代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100010,B=350;
int n,m,a[N],am[N],book[N],b[N],cnt[N];
int get(int x){
    return lower_bound(am+1,am+1+n,x)-am;
}
struct node{
    int l,r,id;
}q[N];
bool operator<(node x,node y){
    return x.l/B==y.l/B?x.r/B<y.r/B:x.l/B<y.l/B;
}
bitset<N>bt,ans[N/3];
void add(int x){
    bt[x+b[x]]=1;
    b[x]++;
}
void del(int x){
    b[x]--;
    bt[x+b[x]]=0;
}
void solve(int xx){
    int mm=0;
    for(int i=1;i<=xx;i++){
        cnt[i]=0;
        for(int j=1;j<=3;j++){
            mm++;
            cin>>q[mm].l>>q[mm].r;
            q[mm].id=i;
            cnt[i]+=q[mm].r-q[mm].l+1;
        }
    }
    sort(q+1,q+1+mm);
    int l=1,r=0;
    for(int i=1;i<=mm;i++){
        while(l>q[i].l)l--,add(a[l]);
        while(r<q[i].r)r++,add(a[r]);
        while(l<q[i].l)del(a[l]),l++;
        while(r>q[i].r)del(a[r]),r--;
        if(book[q[i].id])ans[q[i].id]&=bt;
        else book[q[i].id]=1,ans[q[i].id]=bt;
    }
    for(int i=1;i<=xx;i++)cout<<cnt[i]-3*(int)(ans[i].count())<<"\n",ans[i].reset(),book[i]=0;
    for(int i=1;i<=n;i++)b[i]=0;bt.reset();
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],am[i]=a[i];
    sort(am+1,am+1+n);
    for(int i=1;i<=n;i++)a[i]=get(a[i]);
    solve(m/3);solve(m/3);solve(m-m/3*2);//拆开询问
    return 0;
}

T2 ： [Ynoi Easy Round 2017] 由乃的玉米田

题目链接： [Ynoi Easy Round 2017] 由乃的玉米田。

题目内容：

给定一个序列，每次判断区间 $[l,r]$ 内是否有存在两个数 $a,b$ 使得 $a+b=x$ 或 $a-b=x$ 或 $ab=x$ 或 $a=bx$ 。

序列长度 $n \le 10^5$ 且对于序列每个元素 $a_i$ 满足 $0 \le a_i \le 10^5$ ，操作次数 $m\le 10^5$ 。

时间限制 $1s$ ，空间限制 $128MB$ 。

~~做完 T1 后来看这题的。~~

这种存在性问题和区间问题自然也是莫队和 bitset 了。

那么自然的，设 bitset 为 $B$ ，那么对于 $ab=x$ 的问题就很简单了，只需要 $O(\sqrt{n})$ 的枚举因数就行了。

对于 $a-b=x$ ，只需要判断 (B&(B<<x)).any() 就行了。

同样的，对于 $a+b=x$ ，只需要判断 (b&(rev>>N-q[i].x)).any() 就行了，其中 $rev$ 为将 $B$ 反过来的结果， $N$ 为 bitset 大小。

好了，现在就已经可以 AC 双倍经验小清新人渣的本愿了。

接下来是最后一个 $a=bx$ 的询问了，如果 $x \ge \sqrt{10^5}$ ，那么完全可以在 $O(\sqrt{n})$ 的时间内处理出来。如果 $x <\sqrt{10^5}$ ，我们考虑把这类询问单独处理（因为这类询问单次 add 和 del 有着非 $O(1)$ 的复杂度）。

不难发现，当 $x=1$ 是一定有解，而当 $x=2$ 的时候最浪费时间。而如果像 $x=2$ 这种询问我们在开一个数组记录，那么在莫队移动是这种东西复杂度却是 $O(x)$ 的。

这种巨大的差异不难让人想到根号分治。

具体的，设一个阈值 $K$ ，当 $x>K$ 时，仍然使用 $x>\sqrt{10^5}$ 的方法；当 $x\le K$ 时，我们单独处理，在莫队中开一个数组记录答案。可以发现，如果 $n,m$ 同阶，这样做复杂度是 $O(n\sqrt{n}+n\times \frac{10^5}{K}+nK\sqrt{n})$ ，设 $n=10^5$ ，那么当 $K=\sqrt[4]{n}$ 时复杂度达到最优，为 $O(n^{\frac{7}{4}})$ 。

然而这是 YNOI ， lxl 是不会让你这么简单就通过的，你会获得 $100 \times \frac{21}{(\sqrt{(2\sqrt{5})^2+(4\sqrt{5})^2})^2}$ 的好成绩。

注意到上述阈值 $K$ 的设定是十分宽泛的，只需要将上述阈值 $K$ 改为 $3$ ，就可以真正的获得 $(\sqrt{(2\sqrt{5})^2+(4\sqrt{5})^2})^2$ 的坏成绩，连 lxl 也无法阻止你。

见代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100010,B=350;
int n,m,a[N],b[N],ans[N],hav[N];
bitset<N>ex,rev;
struct node{
    int l,r,id,x,opt;
}q[N];
vector<int>v;
bool operator<(node x,node y){
    return x.l/B==y.l/B?x.r/B<y.r/B:x.l/B<y.l/B;
}
void add(int x){
    b[x]++;ex[x]=1;rev[N-x]=1;
}
void del(int x){
    b[x]--;if(b[x]==0)ex[x]=0,rev[N-x]=0;
}
void addd(int x){
    b[x]++;
    if(b[x]>1)return ;
    for(int i=1;i<=3;i++){
        if(x%i==0&&b[x/i]){
            hav[i]++;
        }
    }
    for(int i=2;i<=3;i++){//阈值 K=3
        if(x*i<=1e5&&b[x*i]){
            hav[i]++;
        }
    }
}
void dell(int x){
    b[x]--;
    if(!b[x]){
        hav[1]--;
    for(int i=1;i<=3;i++){
        if(x%i==0&&b[x/i]){
            hav[i]--;
        }
    }
    for(int i=1;i<=3;i++){
        if(x*i<=1e5&&b[x*i]){
            hav[i]--;
        }
    }}
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=m;i++){
        int opt,l,r,x;
        scanf("%d%d%d%d",&opt,&l,&r,&x);
        q[i]={l,r,i,x,opt};
    }
    sort(q+1,q+1+m);
    int l=1,r=0,k=0;
    for(int i=1;i<=m;i++){
        if(q[i].opt==4&&q[i].x<=3){//分开处理
            q[++k]=q[i];
            continue;
        }
        while(l>q[i].l)l--,add(a[l]);
        while(r<q[i].r)r++,add(a[r]);
        while(l<q[i].l)del(a[l]),l++;
        while(r>q[i].r)del(a[r]),r--;
        if(q[i].opt==1){
            if((ex&(ex<<q[i].x)).any())ans[q[i].id]=1;
        }
        if(q[i].opt==2){
            if((ex&(rev>>N-q[i].x)).any())ans[q[i].id]=1;
        }
        if(q[i].opt==3){
            for(int j=1;j*j<=q[i].x;j++){
                if(q[i].x%j==0&&ex[j]&&ex[q[i].x/j]){
                    ans[q[i].id]=1;
                    break;
                }
            }
        }
        if(q[i].opt==4){
            if(q[i].x==1){ans[q[i].id]=1;continue;}
            if(q[i].x==0)continue;
            for(int j=1;j*q[i].x<=1e5;j++){
                if(ex[j]&&ex[j*q[i].x]){
                    ans[q[i].id]=1;
                    break;
                }
            }
        }
    }
    memset(b,0,sizeof(b));
    l=1;r=0;
    sort(q+1,q+1+k);
    for(int i=1;i<=k;i++){
        while(l>q[i].l)l--,addd(a[l]);
        while(r<q[i].r)r++,addd(a[r]);
        while(l<q[i].l)dell(a[l]),l++;
        while(r>q[i].r)dell(a[r]),r--;
        ans[q[i].id]=hav[q[i].x];
    }
    for(int i=1;i<=m;i++){
        if(ans[i])printf("yuno\n");
        else printf("yumi\n");
    }
    return 0;
}