test20231104

标签：test20231104 int lim sum tr read tag

T4

以 T4 的水准来说应该算是一道简单题，思维并不复杂。

重点：抽屉原理，一个区间不会长度超过 \(14\)。

每次操作等于是把幂次乘上 \(3\)。

由于 \(a_i\) 到最后一定是为 \(a_i^{3^k}\)，所以我们可以直接暴力倍增，然后分解 \(k\) 就行了。

int n,m,v,phi;
int a[N];
int dp[N][22];
inline void init(){
    up(i,0,v-1)dp[i][0]=i*i*i%v;
    up(j,1,20){
        up(i,0,v-1){
           dp[i][j]=dp[dp[i][j-1]][j-1];
        }    
    }
}
struct SegmentTree{
    struct node{
        int l,r,tag;
    }tr[N<<2];
    inline void build(int k,int l,int r){
        tr[k].l=l;tr[k].r=r;tr[k].tag=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
    }
    inline void push_down(int k){
        if(tr[k].tag!=0){
            tr[lc].tag=tr[k].tag+tr[lc].tag;
            tr[rc].tag=tr[rc].tag+tr[k].tag;
            tr[k].tag=0;
        }
    }
    
    inline void plus(int k,int l,int r){
        if(tr[k].l>=l&&tr[k].r<=r){
            tr[k].tag++;
            return;
        }
        int mid=(tr[k].l+tr[k].r)>>1;
        push_down(k);
        if(mid>=l)plus(lc,l,r);
        if(mid<r)plus(rc,l,r);
    }
    inline void clac(int&ans,int&r){
        int j=20;
        while(j>=0){
            if(r>=(1<<j)){
                ans=dp[ans][j];
                r-=(1<<j);
                if(r==0)break;
            }
            j--;
        }
        return;
    }
    inline void ask(int k,int l,int r){
        if(tr[k].l==tr[k].r){
            clac(a[tr[k].l],tr[k].tag);
            return;
        }
        int mid=(tr[k].l+tr[k].r)>>1;
        push_down(k);
        if(mid>=l)ask(lc,l,r);
        if(mid<r)ask(rc,l,r);
    }
}T;
inline int getphi(int x){
    int t=x,ans=x;
    up(i,2,sqrt(x)){
        if(t%i==0){
            ans=ans/i*(i-1);
            while(t%i==0)t/=i;
        }
    }
    if(t>1)ans=ans/t*(t-1);
    return ans;
}
bool flag;
bool vis[N];
int sta[N],cnt;
inline void dfs1(int u,int lim,int sum,bool lead){
    if(flag)return;
    if(u==lim+1){
        if(lead==1){
            if(sum==0)flag=1;
            else if(sum>0&&!vis[sum]){
                vis[sum]=1;
                sta[++cnt]=sum;
            }
        }
        return;
    }
    dfs1(u+1,lim,sum+a[u]+1,1);
    dfs1(u+1,lim,sum-a[u]-1,1);
    dfs1(u+1,lim,sum,lead);
}
inline void dfs2(int u,int lim,int sum,bool lead){
    if(flag)return;
    if(u==lim+1){
        if(lead==1){
            if(sum==0)flag=1;
            else if(sum>0&&vis[sum])flag=1;
        }
        return;
    }
    dfs2(u+1,lim,sum,lead);
    dfs2(u+1,lim,sum+a[u]+1,1);
    dfs2(u+1,lim,sum-a[u]-1,1);
}
signed main(){
	n=read();m=read();v=read();
    init();
    up(i,1,n)a[i]=read();
    T.build(1,1,n);
    int l,r,op;
    while(m--){
        op=read();
        if(op==1){
            l=read();r=read();
            if(r-l+1>=14)puts("Yes");
            else{
                T.ask(1,l,r);
                flag=0;cnt=0;
                int mid=(l+r)>>1;
                dfs1(l,mid,0,0);
                dfs2(mid+1,r,0,0);
                if(flag)puts("Yes");
                else puts("No");
                up(i,1,cnt)vis[sta[i]]=0;
            }
        }
        else{
            l=read(),r=read();
            T.plus(1,l,r);
        }
    }
    return 0;
}

标签：test20231104,int,lim,sum,tr,read,tag
From： https://www.cnblogs.com/LiQXing/p/17810267.html