首页 > 其他 > 详细

BZOJ 4722 由乃

时间:2020-01-21 21:04:32      阅读:59      评论:0      收藏:0      [点我收藏+]

标签:using   ==   修改   ems   std   getch   

Link
思博题。
根据鸽巢原理,当区间长度\(\ge14\)时一定有解。
因此对于查询操作,我们可以用bitset优化暴力背包做到单次\(O(\frac{13*v}{\omega})\)
对于修改操作,容易发现一定存在一个\(\le p\)的循环节,和Pollard-Rho中的\(\rho\)型结构很相似。
那么我们\(O(v^2)\)预处理出每个数的循环节,何时进入循环节,以及进行\(x\)次立方之后的值,然后用树状数组维护每个位置进行过多少次操作即可。

#include<cstdio>
#include<cctype>
#include<bitset>
#include<cstring>
using std::bitset;
const int N=100007,M=1007;
int n,m,p,a[N],t[N],vis[M],f[M][M],st[M],len[M];bitset<13007>s;
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
void add(int p,int v){for(;p<=n;p+=p&-p)t[p]+=v;}
int ask(int p){int r=0;for(;p;p^=p&-p)r+=t[p];return r;}
int get(int x,int t){return t<=st[x]? f[x][t]:f[x][(t-st[x])%len[x]+st[x]];}
int main()
{
    n=read(),m=read(),p=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=0;i<p;++i)
    {
    memset(vis,0,sizeof vis),vis[f[i][0]=i]=1;
    for(int j=1,k=i;!st[i];vis[f[i][j]=k]=j+1,++j) if(vis[k=k*k*k%p]) len[i]=j+1-vis[k],st[i]=vis[k];
    }
    for(int i=1;i<=m;++i)
    if(read()==1)
    {
        int l=read(),r=read();
        if(r-l+1>13) {printf("Yuno\n");continue;}
        s.reset(),s[0]=1;
        for(int j=l;j<=r;++j) s|=s<<1+get(a[j],ask(j));
        printf("%s\n",s.count()>>(r-l+1)? "Yuki":"Yuno");
    }
    else add(read(),1),add(read()+1,-1);
    return 0;
}

BZOJ 4722 由乃

标签:using   ==   修改   ems   std   getch   

原文:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12222945.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号