Skip to content

11553: 【原1553】square

题目

题目描述

author: THOI 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1553

Description

小H是一位勤奋的中学生,他的理想是进入自己心仪的蓝翔学习理论计算机科学。为了实现这一目标,他从小就开始认真学习搬砖的基础知识。

今天,小H学习了平方运算。为了检验自己是否熟练掌握了平方运算,小H决定给自己出一道题。小H有一个长度为\(N\)的序列\({X_1,X_2,…,X_N}\)。小H会时不时地取出序列中的一段连续区间\([l,r]\) ,并将其中的每一个数改为原数值的平方对\(p\)取模的结果,即 \[\forall i \in [l,r], X_i \leftarrow (X_i \times X_i) mod p \]

其中, \(p\) 为某个给定的数。为了检验自己的运算是否正确,小H还会时不时地想要知道序列中某一段连续区间 \([l,r]\) 内所有数的和是多少。

但是,小H现在并没有标准答案。所以,他向你求助,希望你编写一个程序,帮他计算出每次想要知道的区间内的数的总和。

Input Format

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

接下来一行 \(N\) 个数代表一开始的序列\( {X_1,X_2,…,X_N}\)。

接下来 \(M\) 行,每行三个整数 \(op,l,r\)。其中 \(op\) 代表本次操作的类型。若 \(op=0\),代表这是一次平方操作,平方的区间为 \([l,r]\);如果 \(op=1\),代表这是一次询问操作,询问的区间为 \([l,r]\)。

Output Format

对于每次的询问操作,输出一行代表这段区间内数的总和。

注意:答案没有对任何数取模

Sample Input

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

Sample Output

6
14

Sample Input

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

Sample Output

3
2

Limits

对于\(100\%\)的数据,\(\forall i, X_i\in [0,p),l,r\in [1,N]\)。

\(N,M,p\)的范围见下表:

| 编号 | \(N\) | \(M\) | \(p\) | |------|----------------|---------|---------| | 1 | \(\leq1000\) |\(\leq1000\) |233 | | 2 | \(\leq1000\) |\(\leq1000\) |2332 | | 3 | \(\leq100000\) |\(\leq100000\) |\(5\) | | 4 | \(\leq100000\) |\(\leq100000\) |\(8192\) | | 5 | \(\leq1000000\) |\(\leq1000000\) |\(23\) | | 6 | \(\leq1000000\) |\(\leq1000000\) |\(45\) | | 7 | \(\leq1000000\) |\(\leq1000000\) |\(37\) | | 8 | \(\leq55000\) |\(\leq55000\) |\(4185\) | | 9 | \(\leq55000\) |\(\leq55000\) |\(5850\) | | 10 | \(\leq55000\) |\(\leq55000\) |\(2975\) | | 11 | \(\leq55000\) |\(\leq55000\) |\(2542\) | | 12 | \(\leq55000\) |\(\leq55000\) |\(2015\) | | 13 | \(\leq60000\) |\(\leq60000\) |\(2003\) | | 14 | \(\leq65000\) |\(\leq65000\) |\(2010\) | | 15 | \(\leq70000\) |\(\leq70000\) |\(4593\) | | 16 | \(\leq75000\) |\(\leq75000\) |\(4562\) | | 17 | \(\leq80000\) |\(\leq80000\) |\(1034\) | | 18 | \(\leq85000\) |\(\leq85000\) |\(5831\) | | 19 | \(\leq90000\) |\(\leq95000\) |\(9905\) | | 20 | \(\leq100000\) |\(\leq100000\) |\(9977\) |

yyong119's solution

#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);

}