BZOJ

分析

$[l,r]$ 的非空子集数为 $2^{r-l+1}-1$，而子集贡献数至多为 $1000(r-l+1)$。

当 $2^{r-l+1}-1>1000(r-l+1)$ 即 $r-l+1>13$ 时，根据抽屉原理显然有解，因此直接输出 Yuno 即可。

先考虑操作 $1$ 怎么做。用树状数组维护每个点被修改的次数，然后倍增即可求出答案。

再考虑操作 $2$。设 $dp_{i,j}$ 表示前 $i$ 个数能否凑出 $j$，那么如果在某时 $dp_{i-1,j}$ 和 $dp_{i-1,j-a_i-1}$ 同时为 $1$ 就说明有解。用 bitset 维护 $dp$ 数组即可做到 $\mathcal{O}\left(\frac{(r-l+1)^2V}{\omega}\right)$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,P=1000+10;

int n,Q,mod;
int a[N],f[17][P];
bitset<P*13> dp;

int c[N];
inline void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    n=read(),Q=read(),mod=read();
    for (re int i=1;i<=n;++i) a[i]=read();

    for (re int i=0;i<mod;++i) f[0][i]=i*i*i%mod;
    for (re int i=1;i<17;++i)
        for (re int j=0;j<mod;++j)
            f[i][j]=f[i-1][f[i-1][j]];

    while (Q--) {
        int op=read(),l=read(),r=read();
        if (op==2) add(l,1),add(r+1,-1);
        else {
            if (r-l+1>13) { puts("Yuno"); continue; }
            int flag=0; dp.reset(); dp[0]=1;
            for (re int i=l;i<=r;++i) {
                int x=a[i],t=sum(i);
                for (re int i=16;~i;--i)
                    if (t&(1<<i)) x=f[i][x];
                ++x;
                if ((dp&(dp<<x)).any()) flag=1;
                dp|=dp<<x;
            }
            puts(flag?"Yuno":"Yuki");
        }
    }
    return 0;
}