BZOJ 4722 由乃

给n个数字，保证每个数小于v。有m个操作

操作1.将区间l~r的数字从a[i]变成a[i]a[i]a[i] % v

操作2.每次询问一个区间中是否可以选出两个下标的集合X，Y，满足：

1.X和Y没有交集

2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献
相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki

对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度

考虑操作1，三次方不能直接维护，考虑log的或者O(1)的复杂度

O(1)，找循环节？不太靠谱，不保证每个数字都有循环节

O(log),快速幂？因为是指数相乘，一个数经过三次这样的运算就变成它的27次方了

O(log),倍增，F[i][j]表示数字i的3的2^j次方的答案啊哈，于是线段树维护区间加

对于询问2，对于一个区间长度位len的区间，它的子集数量时2^{len}-1,它可能的元素个数是1000*len.

所以当len>13时，2^{len}-1>1000*len，必然有两个子集之和相同哈

所以对len<=13的，我们搜索。复杂度是3^{len}，每个数有3个情况，在X中，在Y中，两个都不在。复杂度仍然爆炸。

考虑双向搜索，3^{len/2}*log(3^{len})，复杂度还行

CODE

#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
#define mem(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
const int N = 1e6+1e2;
int v;
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
int n,m,F[1010][20];
int a[N],sum[N<<2],lazy[N<<2],cov[N<<2];
inline int pushdown(int cur,int x){
    if(cov[cur]){
        cov[cur<<1|1]+=cov[cur];
        cov[cur<<1]+=cov[cur];
        cov[cur]=0;
    }
    return 0;
}
int sss=0;
inline int change(int l,int r,int L,int R,int cur){
    if(L<=l&&r<=R) {
        sum[cur]++;
        return 0;
    }
    int mid=l+r>>1;
    if(L<=mid) change(l,mid,L,R,cur<<1);
    if(R>mid) change(mid+1,r,L,R,cur<<1|1);
    return 0;
}
inline int ask(int l,int r,int x,int cur){
    if(l==r){
        return sum[cur];
    }
    int mid=l+r>>1;
    if(x<=mid) return ask(l,mid,x,cur<<1)+sum[cur];
    else return ask(mid+1,r,x,cur<<1|1)+sum[cur];
}
int s[20],cnt,tot,MID,flag;
int b[N<<2],p[N<<2];
inline int dfs(int pos,int sum,int cnt){
    if(flag) return flag;
    if(pos>MID){
        if(!cnt) return 0;
        b[++tot]=sum;
        p[sum+(N<<1)]=1;
        if(sum==0&&cnt) flag=1;
        return 0;
    }
    dfs(pos+1,sum+s[pos]+1,cnt+1);
    if(flag) return flag;
    dfs(pos+1,sum-s[pos]-1,cnt+1);
    dfs(pos+1,sum,cnt);
    if(flag) return flag;

    return flag;
}
inline int check(int sum){
    if(p[sum+(N<<1)]) return 1;
    return 0;
}
inline int dfs2(int pos,int sum,int cnt,int r){
    sss++;
    if(flag) return flag;
    if(pos>r){
        if(!cnt) return 0;
        if(sum==0&&cnt) 
            flag=1;
        if(p[sum+(N<<1)])  
             return flag=1;
        return 0;
    }
    dfs2(pos+1,sum+s[pos]+1,cnt+1,r);
    if(flag) return flag;
    dfs2(pos+1,sum-s[pos]-1,cnt+1,r);
    if(flag) return flag;
    dfs2(pos+1,sum,cnt,r);
    return flag;
}
inline int get(int x){
    int s=ask(1,n,x,1);
    int ans=a[x];
    for(int i=16;i+1;--i){
        if(s&(1<<i))
            ans=F[ans][i];
    }
    return ans;
}
inline int query(int l,int r){
    cnt=flag=tot=0;
    for(int i=l;i<=r;++i){
        s[++cnt]=get(i);
    }
    std::sort(s+1,s+1+cnt);
    MID=(r-l+1)>>1;
    dfs(1,0,0);
    std::sort(b+1,b+1+tot);
    dfs2(MID+1,0,0,r-l+1);
    for(int i=1;i<=tot;++i) p[b[i]+(N<<1)]=0;
    return flag;
}
int main() {
    n=read(),m=read(),v=read();
    for(int i=1;i<=1000;++i) F[i][0]=(i*i%v*i)%v; 
    for(int i=1;i<=19;++i){
        for(int j=1;j<=1000;++j){
            F[j][i]=F[F[j][i-1]][i-1];
            F[j][i]%=v;
        }
    }
    for(int i=1;i<=n;++i)
        a[i]=read();
    while(m--){
        int od=read(),l=read(),r=read();
        if(od==2){
            change(1,n,l,r,1);
        }
        if(od==1){
            if(r-l+1>13){
                printf("Yuno\n");
                continue;
            } 
            else{
                int x=query(l,r);
                if(x)printf("Yuno\n");
                else printf("Yuki\n");
            }
        }
    }
    return 0;
}