~~不要在意网址...打错了qwq~~

题目大意

Informatik verbindet dich und mich.
信息将你我连结。

维护一个数列A，支持两种操作：

0 l r ：表示将A[l..r]这个区间的每个数\(A_i\)变成\(c^{A_i}\)（c是输入给定的常量）
1 l r : 表示求\(A[l..r]\)的和，结果对p（输入给定的常量）取模。

数据范围与约定

对于 100% 的测试点， \(1 \leq n \leq 50000; 1 \leq m \leq 50000; 1 \leq p \leq 100000000; 0 < c <p; 0 \leq ai < p\)。

解法

观察数据范围，\(n,m\leq 50000\)。这个~~不伦不类的~~范围应该是\(O(n \log n \log C)\)之类的吧？
还有区间求和...?线段树？
不知道大家有没有做过线段树区间取模和区间开方之类维护奇怪运算的题？它们有一个共同点：暴力递归到叶子节点修改，因为运算的特殊性质决定了修改次数不超过\(O(n\log C)\)，所以复杂度正确。考虑这个奇怪的运算。现在我们要解决的问题就是如何快速（\(O(\log\ n)\)以内）求这个： \[\LARGE{c^{c^{c^{c^{...a_i}}}}}\] 不知道您有没有做过这个题，如果没有可以去做一下qwq.
做完了吧？那现在您一定会了欧拉定理： \[ a^b \bmod p=\left \{ \begin{aligned} &a^{b \bmod \phi (p) +\phi (p)} &b\geq \phi (p)\\\\ &a^b &b<\phi (p) \end{aligned} \right. \] > 引理：对于一个数\(n\in \mathbb N^*\)，一直取\(\phi (n)\),最多取\(O(\log n)\)次就会变成\(1\).
> 简要证明：对于偶数，所有偶数都与它不互质。取\(\phi (n)\)至少会除以2.对于奇数，考虑定义式，它一定会变成偶数。所以最多\(2\log n\)次会变成\(1\).

所以当修改次数太大的时候，从某一层开始，模数都是1.这就没必要算了。所以用区间开方的思路，线段树记录区间和、区间修改次数。修改次数超过最大值时忽略修改。否则继续递归。每递归到叶子节点时，暴力修改叶子的值。顺便维护区间和。这时，总复杂度是\(O(n \log^2 n\log C)\)的。不太能承受。但是我们发现计算过程中模数只有\(O(\log n)\)种取值，所以光速幂预处理一下，就可以少掉一个log啦。然后就可以愉快地通过本题啦。好像还要wys~~或者mcfx~~一下代码

代码：

#pragma GCC optimize("-Ofast")
#pragma GCC optimize(3)
#include <cstdio>
#include <cctype>
#include <cmath>
#include <utility>
#define ls l,mid,o<<1
#define rs mid+1,r,o<<1|1

using std::pair;
using std::make_pair;

typedef long long ll;

const int maxn=(5e4+100)*2;

int a[maxn<<2],count[maxn<<2],P,c,maxlim;
ll sumv[maxn<<2];
int phi[maxn],Sqrt[maxn];

char buf[1<<24],*fs;
ll c_sqrt[150][maxn],c_x[150][maxn];
bool is_greater[100][maxn],is_greater_sqrt[100][maxn];

// #define gc() getchar()
#define gc() (*fs++)

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

inline int read()
{
    char ch;
    while (!isdigit(ch=gc()));
    int x=ch^48;
    while (isdigit(ch=gc())) x=x*10+ch-48;
    return x;
}

inline pair<ll,bool> qpow(ll a,ll b,ll P)
{
    ll ans=1%P;
    bool gr=false;
    for (;b;b>>=1)
    {
        if (b&1) ans=ans*a;
        if (ans>=P) ans%=P,gr=true;
        a=a*a%P;
    }
    return make_pair(ans,gr);
}

inline void CalcPower(int x,int now)
{
    int T=Sqrt[now]=sqrt(x);
    c_x[now][0]=1;c_x[now][1]=c;
    c_sqrt[now][0]=1;pair<ll,bool> pr=qpow(c,T,x);c_sqrt[now][1]=pr.first;
    if (c_x[now][1]>=x) is_greater[now][1]=true,c_x[now][1]%=x;
    if (pr.second) is_greater_sqrt[now][1]=true;
    if (c_x[now][0]>=x) is_greater[now][0]=true,c_x[now][0]%=x;
    if (c_sqrt[now][0]>=x) is_greater_sqrt[now][0]=true,c_sqrt[now][0]%=x;
    for (int i=2;i<=T*2;++i)
    {
        c_x[now][i]=c_x[now][i-1]*c;
        c_sqrt[now][i]=c_sqrt[now][i-1]*c_sqrt[now][1];
        if (c_x[now][i]>=x) is_greater[now][i]=true,c_x[now][i]%=x;
        if (c_sqrt[now][i]>=x) is_greater_sqrt[now][i]=true,c_sqrt[now][i]%=x;
    }
}

inline pair<ll,bool> Fastpow(int b,int now)
{
    ll t=c_x[now][b%Sqrt[now]]*c_sqrt[now][b/Sqrt[now]];
    bool flag=is_greater[now][b%Sqrt[now]]|is_greater_sqrt[now][b/Sqrt[now]];
    if (t>=phi[now]) flag=true,t%=phi[now];
    return make_pair(t,flag);
}

inline int Getphi(int x)
{
    int ret=x;
    for (int i=2;i<=x;++i)
    {
        if (x%i==0)
        {
            while (x%i==0) x/=i;
            ret=ret/i*(i-1);
        }
    }
    if (x>1) ret=ret/x*(x-1);
    return ret;
}

inline void Prework(int P,int i=1)
{
    ++maxlim;
    if (P==1) phi[i]=1;
    CalcPower(phi[i]=Getphi(P),i);
    if (P==1) return;
    Prework(phi[i],i+1);
}

inline ll CalcNumber(int expo,int depth,int limit)
{
    // if (phi[depth-1]==1) return 0;
    if (depth==limit+1) return expo>phi[limit]?expo%phi[limit]+phi[limit]:expo;
    int t=CalcNumber(expo,depth+1,limit);
    pair<ll,bool> pr=Fastpow(t,depth-1);
    // printf("depth=%d ,exp=%d\n",depth,pr.second?pr.first+phi[depth-1]:pr.first);
    if (pr.second==1) return pr.first+phi[depth-1];
    return pr.first;
}

inline void Pushup(int o)
{
    sumv[o]=sumv[o<<1]+sumv[o<<1|1];
    if (sumv[o]>=P) sumv[o]-=P;
}

inline void BuildSeg(int l,int r,int o)
{
    if (l==r) return void(sumv[o]=a[l]);
    int mid=(l+r)>>1;
    BuildSeg(ls);BuildSeg(rs);
    Pushup(o);
}

inline void Modify(int L,int R,int l,int r,int o)
{
    if (count[o]>=maxlim) return;
    if (l==r)
    {
        ++count[o];
        sumv[o]=CalcNumber(a[l],1,count[o])%P;
        // printf("pos=%d num=%d\n",l,sumv[o]);
        return;
    }
    int mid=(l+r)>>1;
    if (L<=mid) Modify(L,R,ls);
    if (R> mid) Modify(L,R,rs);
    Pushup(o);
    count[o]=min(count[o<<1],count[o<<1|1]);
}

inline int Query(int L,int R,int l,int r,int o)
{
    if (L<=l && R>=r) return sumv[o];
    int mid=(l+r)>>1;
    int tot=0;
    if (L<=mid) tot+=Query(L,R,ls);
    if (R> mid) tot+=Query(L,R,rs);
    if (tot>=P) tot-=P;
    return tot;
}

int main()
{
    fread(fs=buf,1,1<<24,stdin);
    int n=read(),m=read();phi[0]=P=read(),c=read();Sqrt[0]=sqrt(P);
    CalcPower(P,0);
    for (int i=1;i<=n;++i) a[i]=read();
    Prework(P);BuildSeg(1,n,1);
    for (int i=1,opt,l,r;i<=m;++i)
    {
        opt=read();l=read();r=read();
        if (opt) printf("%d\n",Query(l,r,1,n,1));
        else Modify(l,r,1,n,1);
    }
}

_WA自动机的blog

[六省联考2017]相逢是问候

题目大意

数据范围与约定

解法

代码：