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

填坑

我不知道怎么算的，但是所有环的LCM数不会超过60

然后用线段树维护这个东西，每个节点记录子树内的循环节

没到循环节的暴力枚举

复杂度是nlogn再乘以循环节长度

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#define lc (now<<1)

#define rc (now<<1|1)

#define mid (ql+qr)/2

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=1e5+_;

const int maxp=1e4+_;

const int maxh=+;

const int mbit=(<<)+_;

int gcd(int a,int b){if(a==)return b;return gcd(b%a,a);}

int lcm(int a,int b){return a/gcd(a,b)*b;}

int nxt[maxp];bool inh[maxp];int tim,v[maxp];

void init(int p)

{

    for(int i=;i<p;i++)nxt[i]=i*i%p;

    tim=;

    for(int i=;i<p;i++)

        if(v[i]==)

        {

            v[i]=++tim;

            for(int k=nxt[i];;k=nxt[k])

            {

                if(v[k]==tim)

                {

                    inh[k]=true;

                    for(int u=nxt[k];u!=k;u=nxt[u])inh[u]=true;

                    break;

                }

                if(v[k]>)break;

                v[k]=tim;

            }

        }

}

//--------------------------------------yu---------------------------------------------------

struct hh

{

    int len,pos,h[maxh];

    hh(){}

    int insert(int d)

    {

        if(inh[d])

        {

            len=;pos=;h[++len]=d;

            for(int k=nxt[d];k!=d;k=nxt[k])h[++len]=k;

            return ;

        }

        return -;

    }

    void merge(hh h1,hh h2)

    {

        len=lcm(h1.len,h2.len);pos=;

        for(int k=,i=h1.pos,j=h2.pos;k<=len;k++,i=i%h1.len+,j=j%h2.len+)

            h[k]=h1.h[i]+h2.h[j];

    }

    int ad(int b){pos=(pos+b-)%len+;return h[pos];}

};

struct trnode{int sum,la;hh h;};int w[maxn];

struct Segtree

{

    trnode tr[*mbit];

    Segtree(){}

    void update(int now)

    {

        tr[now].sum=tr[lc].sum+tr[rc].sum;

        if(tr[lc].la!=-&&tr[rc].la!=-)

        {

            tr[now].la=;

            tr[now].h.merge(tr[lc].h,tr[rc].h);

        }

        else tr[now].la=-;

    }

    void pushdown(int now)

    {

        if(tr[now].la<=)return ;

        tr[lc].sum=tr[lc].h.ad(tr[now].la),tr[lc].la=(tr[lc].la+tr[now].la-)%tr[lc].h.len+;

        tr[rc].sum=tr[rc].h.ad(tr[now].la),tr[rc].la=(tr[rc].la+tr[now].la-)%tr[rc].h.len+;

        tr[now].la=;

    }

    void bt(int now,int ql,int qr)

    {

        if(ql==qr){tr[now].sum=w[ql],tr[now].la=tr[now].h.insert(w[ql]);return ;}

        bt(lc,ql,mid),bt(rc,mid+,qr),update(now);

    }

    void change(int now,int ql,int qr,int l,int r)

    {

        if(ql==l&&qr==r&&tr[now].la!=-){tr[now].sum=tr[now].h.ad();tr[now].la++;return ;}

        if(ql==qr){tr[now].la=tr[now].h.insert(nxt[tr[now].sum]),tr[now].sum=nxt[tr[now].sum];return ;}

        pushdown(now);

             if(r<=mid)  change(lc,ql,mid,l,r);

        else if(mid+<=l)change(rc,mid+,qr,l,r);

        else change(lc,ql,mid,l,mid),change(rc,mid+,qr,mid+,r);

        update(now);

    }

    int getsum(int now,int ql,int qr,int l,int r)

    {

        if(ql==l&&qr==r)return tr[now].sum;

        pushdown(now);

             if(r<=mid)  return getsum(lc,ql,mid,l,r);

        else if(mid+<=l)return getsum(rc,mid+,qr,l,r);

        else return getsum(lc,ql,mid,l,mid)+getsum(rc,mid+,qr,mid+,r);

    }

}S;

//---------------------------------data structure---------------------------------------------

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    int n,Q,p;

    scanf("%d%d%d",&n,&Q,&p);

    init(p);

    for(int i=;i<=n;i++)scanf("%d",&w[i]);

    S.bt(,,n);

    int op,x,y;

    while(Q--)

    {

        scanf("%d%d%d",&op,&x,&y);

        if(op==)S.change(,,n,x,y);

        else printf("%d\n",S.getsum(,,n,x,y));

    }

    return ;

}