有三种操作,区间内每个数数乘一个数,区间内每个数成为他的K次方,求区间内数的乘积。
容易看出这是需要线段树来做的。
我们在这里放置两个lazy数组,用原线段树来维护区间内现在区间乘积是多少。一个lazy数组表示下方未更新的区间需要进行几次方的运算。另一个数组来表示下方为处理区间除了乘方操作外,所有的需要额外的进行乘的数是多少~~。需要注意的是在进行pushdown操作的时候的顺序以及一个地方需要注意~~就是向下更新第一个lazy数组的时候,别忘了先把下方区间的第二个lazy数组先处理了。。
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll sum[maxn * 4], mul[maxn * 4], pf[maxn * 4];
long long quick(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1) {
res = res*a%mod;
}
a = a*a%mod;
b >>= 1;
}
return res;
}
void pushup(int rt) {
sum[rt] = (sum[rt << 1] * sum[rt << 1 | 1]) % mod;
}
void pushdown(int l, int r, int rt) {
long long len = r - l + 1; int m = (l + r) >> 1;
if (pf[rt] != 1) {
mul[rt << 1] = quick(mul[rt << 1], pf[rt]);
mul[rt << 1 | 1] = quick(mul[rt << 1 | 1], pf[rt]);
sum[rt << 1] = quick(sum[rt << 1], pf[rt]);
sum[rt << 1 | 1] = quick(sum[rt << 1 | 1], pf[rt]);
pf[rt << 1] *= pf[rt];
pf[rt << 1] %= mod - 1;
pf[rt << 1 | 1] *= pf[rt];
pf[rt << 1 | 1] %= mod - 1;
pf[rt] = 1;
}
if (mul[rt] != 1) {
sum[rt << 1] = (sum[rt << 1] * quick(mul[rt], (len + 1) / 2)) % mod;
sum[rt << 1 | 1] = (sum[rt << 1 | 1] * quick(mul[rt], len / 2)) % mod;
mul[rt << 1] *= mul[rt]; mul[rt << 1] %= mod;
mul[rt << 1 | 1] *= mul[rt]; mul[rt << 1 | 1] %= mod;
mul[rt] = 1;
}
}
void build(int l, int r, int rt) {
pf[rt] = 1; mul[rt] = 1;
if (l == r) {
scanf("%lld", &sum[rt]);
return;
}
int m = (l + r) >> 1;
build(lson); build(rson);
pushup(rt);
}
void upmul(int L, int R, ll c, int l, int r, int rt) {
if (L <= l&&r <= R) {
mul[rt] *= c; mul[rt] %= mod;
sum[rt] = (sum[rt] * quick(c, 1LL * r - l + 1)) % mod;
return;
}
pushdown(l, r, rt);
int m = (l + r) >> 1;
if (L <= m)
upmul(L, R, c, lson);
if (R > m)
upmul(L, R, c, rson);
pushup(rt);
}
void uppf(int L, int R, ll c, int l, int r, int rt) {
if (L <= l&&r <= R) {
pf[rt] *= c;
pf[rt] %= mod - 1;
sum[rt] = quick(sum[rt], c);
mul[rt] = quick(mul[rt], c);
return;
}
pushdown(l, r, rt);
int m = (l + r) >> 1;
if (L <= m)
uppf(L, R, c, lson);;
if (R > m)
uppf(L, R, c, rson);
pushup(rt);
}
long long query(int L, int R, int l, int r, int rt) {
if (L <= l&&r <= R) {
return sum[rt];
}
long long now = 1;
int m = (l + r) >> 1;
pushdown(l, r, rt);
if (L <= m) {
now = (now*query(L, R, lson)) % mod;
}
if (R > m) {
now = (now*query(L, R, rson)) % mod;
}
return now;
}
int main() {
int te; scanf("%d", &te);
while (te--) {
int n, m;
scanf("%d%d", &n, &m);
build(1, n, 1);
while (m--) {
int a; scanf("%d", &a);
if (a == 1) {
int b, c; ll d; scanf("%d%d%lld", &b, &c, &d);
upmul(b, c, d, 1, n, 1);
}
else if (a == 2) {
int b, c; ll d; scanf("%d%d%lld", &b, &c, &d);
uppf(b, c, d, 1, n, 1);
}
else {
int b, c; scanf("%d%d", &b, &c);
printf("%lld\n", query(b, c, 1, n, 1));
}
// see(1, n, 1);
}
}
return 0;
}