CW高中-C443D
维护下列操作：
- \(\forall i \in [l,r]:a_i \leftarrow x^{a_i}\)。
- 求 \(\sum_{i=l}^ra_i \mod M\)。
\(n,q,M,a_i \le 10^5\)。
显然要欧拉定理降幂。（结果考场上别的都想出来了，但不知道不互质的情况解决办法，真的菜死了）
不互质的情况：
\[\begin{aligned} & a^q \equiv a^{q \; \mathrm{mod} \; \varphi (p) + \varphi (p)} \mod p & q\ge \varphi (p) \end{aligned} \]考虑到每次 \(x \leftarrow \varphi (x)\)。这样的操作到 \(x=1\) 只需要 \(O(\log_2 M)\) 次。
所以会发现一段区间如果被同样的修改操作执行 \(O(\log_2 M)\) 次就会全部相同。
那么考虑相同的区间一起处理。
再势能分析一下，考虑每次修改操作会使得区间内部每个位置的势能 \(-1\)，然后使区间两端的势能 \(\leftarrow \log_2M\)。
这样总共是 \(O(n\log_2M+q\log_2M)\)。
所以可以用一个数据结构维护区间，同时维护一颗线段树支持区间赋值和以及区间和查询。
但是每次遍历区间内的幂塔还要快速幂会花掉一个 \(\log_2 M\) 级别的时间，很亏。
所以考虑 \(O(M\sqrt{M})\) 预处理幂。注意应该同时记录取模之前的值是否大于等于当前考虑的模数。
总的时间复杂度为 \(O((n+q)\log_2^2M+M\sqrt{M})\)。实测常数很大。
#include <bits/stdc++.h>
using namespace std;
inline int read (){
int p = 0;
char c = getchar ();
while (c < '0' || c > '9')
c = getchar ();
while (c >= '0' && c <= '9'){
p = (p << 1) + (p << 3) + (c - '0');
c = getchar ();
}
return p;
}
inline void Write (int x){
if (x > 9)
Write (x / 10);
putchar (x % 10 + '0');
}
const int N = 1e5 + 5;
int n, m, mod[25];
int len, T[25];
vector < vector < int > > pw[25], ppw[25];
// because ex-euler theory , have to do a special mul in power-init time.
// Node-Init ---------- start
inline int mul (int a, int b, int d){
long long res = 1ll * (a >> 1) * (b >> 1);
return ((res % mod[d]) << 1) | (a & 1) | (b & 1) | (res >= mod[d]);
}
inline int Phi (int x){
int res = x;
for (int i = 2;i * i <= x;++ i)
if (x % i == 0){
res = res / i * (i - 1);
while (x % i == 0)
x /= i;
}
if (x > 1)
res = res / x * (x - 1);
return res;
}
inline void Init (int p, int u){
if (p == 1)
return ;
len = u;
mod[u] = p;
int nex = Phi (p);
T[u] = sqrt (p);
while (T[u] * T[u] <= (nex << 1))
++ T[u];
pw[u].resize (p);
ppw[u].resize (p);
for (int i = 0;i < p;++ i){
vector < int > &op = pw[u][i], &opp = ppw[u][i];
op.resize (T[u] + 1);
opp.resize (T[u] + 1);
op[0] = opp[0] = 2;
for (int j = 1;j <= T[u];++ j)
op[j] = mul (op[j - 1], i << 1, u);
for (int j = 1;j <= T[u];++ j)
opp[j] = mul (opp[j - 1], op[T[u]], u);
}
Init (nex, u + 1);
}
inline int Qpow (int a, int p, int d){
return mul (ppw[d][a][p / T[d]], pw[d][a][p % T[d]], d);
}
struct node {
int v[25], cnt;
node (int X = 0, int ap = 0){
v[0] = X;
for (int i = 1;i <= len;++ i)
v[i] = 1;
cnt = ap;
}
void Update (int x){
for (int i = len;i >= 1;-- i)
v[i] = v[i - 1];
v[0] = x;
}
int Query (){
int res = 1;
for (int i = len;i >= 0;-- i){
int u = Qpow (v[i] % mod[i], res, i);
if ((u & 1) || (v[i] >= mod[i] && res != 0))
res = (u >> 1) + mod[i];
else
res = u >> 1;
}
return res % mod[0];
}
};
// Node-Init ---------- end
// Segment_Tree-Init ---------- start
#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)
struct Segment_tree {
int l, r;
long long res;
int tag;
bool flg;
Segment_tree (int L = 0, int R = 0, long long RES = 0, int TAG = 0, bool FLG = false){
l = L;
r = R;
res = RES;
tag = TAG;
flg = FLG;
}
} tr[N << 2];
inline void put_tag (int p, int x){
tr[p].res = 1ll * (tr[p].r - tr[p].l + 1) * x;
tr[p].tag = x;
tr[p].flg = true;
}
inline void push_down (int p){
if (tr[p].flg){
tr[p].flg = false;
put_tag (lson (p), tr[p].tag);
put_tag (rson (p), tr[p].tag);
}
}
inline void push_up (int p){
tr[p].res = tr[lson (p)].res + tr[rson (p)].res;
}
inline void Build (int p, int l, int r){
tr[p] = Segment_tree (l, r, 0, 0);
if (l == r)
return ;
int mid = (l + r) >> 1;
Build (lson (p), l, mid);
Build (rson (p), mid + 1, r);
}
inline void Update (int p, int l, int r, int x){
if (l <= tr[p].l && tr[p].r <= r){
put_tag (p, x);
return ;
}
push_down (p);
int mid = (tr[p].l + tr[p].r) >> 1;
if (l <= mid)
Update (lson (p), l, r, x);
if (r > mid)
Update (rson (p), l, r, x);
push_up (p);
}
inline long long Query (int p, int l, int r){
if (l <= tr[p].l && tr[p].r <= r)
return tr[p].res;
push_down (p);
int mid = (tr[p].l + tr[p].r) >> 1;
long long sum = 0;
if (l <= mid)
sum += Query (lson (p), l, r);
if (r > mid)
sum += Query (rson (p), l, r);
return sum;
}
// Segment_Tree-Init ---------- end
map < int , node > seq;
signed main (){
// freopen ("research.in", "r", stdin);
// freopen ("research.out", "w", stdout);
n = read ();
m = read ();
mod[0] = read ();
Init (mod[0], 0);
Build (1, 1, n);
seq[0] = node (0, len);
for (int i = 1, x;i <= n;++ i){
x = read ();
seq.insert (make_pair (i, node (x, len)));
Update (1, i, i, x);
}
while (m --){
int opt = read (), l = read (), r = read ();
if (opt == 1){
int x = read ();
if (seq.find (l - 1) == seq.end ())
seq[l - 1] = seq.lower_bound (l)->second;
seq[l - 1].cnt = len;
if (seq.find (r) == seq.end ())
seq[r] = seq.lower_bound (r)->second;
seq[r].cnt = len;
for (auto it = seq.lower_bound (l);it->first < r;){
auto nex = it;
++ nex;
-- it->second.cnt;
if (it->second.cnt < 0)
seq.erase (it);
it = nex;
}
int ll = l;
for (auto it = seq.lower_bound (l);it != seq.end () && it->first <= r;++ it){
it->second.Update (x);
Update (1, ll, it->first, it->second.Query ());
ll = it->first + 1;
}
} else {
Write (Query (1, l, r) % mod[0]);
puts ("");
}
}
return 0;
}