ZOJ 3998 Yet Another Data Structure Problem（线段树）

    有三种操作，区间内每个数数乘一个数，区间内每个数成为他的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;
}