分析
$[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;
}