注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4105][ThuSC 2015]平方运算  

2015-06-20 16:05:56|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4105: [Thu Summer Camp 2015]平方运算

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 143  Solved: 64
[Submit][Status][Discuss]

Description

Input

第一行有三个整数N,M,p,分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。

接下来一行N个数代表一开始的序列{X1,X2,...,XN}。
接下来M行,每行三个整数op,l,r。其中op代表本次操作的类型。若op=0,代表这是一次平方操作,平方的区间为[l,r];如果op=1,代表这是一次询问操作,询问的区间为[l,r]。

Output

对于每次的询问操作,输出一行代表这段区间内数的总和。注意:答案没有对任何数取模。

Sample Input

3 3 11 1 2 3 1 1 3 0 1 3 1 1 3

Sample Output

6 14

HINT

 对于100%的数据,?i,Xi∈[0,p),l,r∈[1,n]

N,M,p的范围如下:
编号  N  M  p
1  1000  1000  233
2  1000  1000  2332
3  100000  100000  5
4  100000  100000  8192
5  100000  100000  23
6  100000  100000  45
7  100000  100000  37
8  55000  55000  4185
9  55000  55000  5850
10  55000  55000  2975
11  55000  55000  2542
12  55000  55000  2015
13  60000  60000  2003
14  65000  65000  2010
15  70000  70000  4593
16  75000  75000  4562
17  80000  80000  1034
18  85000  85000  5831
19  90000  90000  9905
20  100000  100000  9977

Source

Solution

首先观察题目中给的模数,经过暴力打表可以得出,在(0,p)范围内的数,经过不超过11步的变换就可以进入一个循环节之中,并且所有整数的循环节长度的最小公倍数不会超过60
于是就可以直接使用线段树来维护。在线段树的每一个节点上记下当前节点的数迭代0~循环节长度次以后的结果的和就可以了
类似区间开根的做法

Code

/**************************************************************
    Problem: 4105
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:17248 ms
    Memory:66284 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char B[1<<15],*S=B,*T=B,ch;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,m,p,x,y,i,vis[N],op,tim,cnt[N],nxt[N],cir[N],maxl,ans;
int t[1<<18][60],tag[1<<18],add[1<<18],tmp[60],mod[N];
void mt(int o){
    t[o][0]=t[o<<1][0]+t[o<<1|1][0];
    if(tag[o]=tag[o<<1]&tag[o<<1|1])
    for(int i=1;i<maxl;i++)t[o][i]=t[o<<1][i]+t[o<<1|1][i];
}
void pd(int o,int l,int r){
    if(!add[o])return;
    if(l==r){
        for(;add[o]--;t[o][0]=nxt[t[o][0]]);add[o]=0;
        if(cir[t[o][0]]){
            tag[o]=1;
            for(int i=1;i<maxl;i++)t[o][i]=nxt[t[o][i-1]];
        }return;
    }
    int mid=l+r>>1;
    add[o<<1]=add[o<<1]+add[o],add[o<<1|1]=add[o<<1|1]+add[o];
    if(tag[o<<1]){
        for(int i=0;i<maxl;i++)tmp[i]=t[o<<1][mod[add[o]+i]];
        memcpy(t[o<<1],tmp,sizeof(tmp));
    }
    else pd(o<<1,l,mid);
    if(tag[o<<1|1]){
        for(int i=0;i<maxl;i++)tmp[i]=t[o<<1|1][mod[add[o]+i]];
        memcpy(t[o<<1|1],tmp,sizeof(tmp));
    }
    else pd(o<<1|1,mid+1,r);
    add[o]=0;mt(o);
}
void bt(int o,int l,int r){
    if(l==r){
        if(cir[t[o][0]=F()]){
            tag[o]=1;
            for(int i=1;i<maxl;i++)t[o][i]=nxt[t[o][i-1]];
        }return;
    }
    int mid=l+r>>1;
    bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);
    mt(o);
}
void upd(int o,int l,int r){
    if(x<=l&&r<=y){
        add[o]++;
        if(tag[o]){
            for(int i=0;i<maxl;i++)tmp[i]=t[o][mod[i+1]];
            memcpy(t[o],tmp,sizeof(tmp));
        }
        else pd(o,l,r);
        return;
    }
    int mid=l+r>>1;pd(o,l,r);
    if(x<=mid)upd(o<<1,l,mid);
    if(mid<y)upd(o<<1|1,mid+1,r);
    mt(o);
}
void query(int o,int l,int r){
    if(x<=l&&r<=y){
        ans+=t[o][0];
        return;
    }
    int mid=l+r>>1;pd(o,l,r);
    if(x<=mid)query(o<<1,l,mid);
    if(mid<y)query(o<<1|1,mid+1,r);
}
int main(){
    for(n=F(),m=F(),p=F();i<p;i++)nxt[i]=i*i%p;
    for(i=0;i<p;i++){
        for(++tim,x=i,y=1;vis[x]!=tim;x=nxt[x])vis[x]=tim,cnt[x]=y++;
        if(maxl<y-cnt[x])maxl=y-cnt[x];
        for(;!cir[x];x=nxt[x])cir[x]=1;
    }
    for(i=0;i<=m;i++)mod[i]=i%maxl;
    for(bt(1,1,n);m--;)
    if(F())ans=0,x=F(),y=F(),query(1,1,n),printf("%d\n",ans);
    else x=F(),y=F(),upd(1,1,n);
}
  评论这张
 
阅读(229)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018