题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4578
题目：
题意：n个数初始值为0，进行四种操作：1.将区间内的数字加c；2.将区间内的数字乘c；3.将区间内的数字变成c；4.询问区间内的元素的p次方和。
思路：这个题真的肝到死，找bug贼难受。我们用cnt1来记录一次方和，cnt2记录二次方和，cnt3记录三次方和。
代码实现如下：
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
typedef unsigned long long ull; #define lson i<<1
#define rson i<<1|1
#define bug printf("*********\n");
#define FIN freopen("D://code//in.txt", "r", stdin);
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define IO ios::sync_with_stdio(false),cin.tie(0); const double eps = 1e-;
const int mod = ;
const int maxn = 1e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f; inline int read() {//读入挂
int ret = , c, f = ;
for(c = getchar(); !(isdigit(c) || c == '-'); c = getchar());
if(c == '-') f = -, c = getchar();
for(; isdigit(c); c = getchar()) ret = ret * + c - '';
if(f < ) ret = -ret;
return ret;
} int n, q, op, x, y, z; struct node {
int l, r;
ll cnt1, cnt2, cnt3, lazy1, lazy2, lazy3, len; //cnt1=siga(ax+b), cnt2=sigs(ax+b)^2,cnt3=siga(ax+b)^3
//lazy1标记加b，lazy2标记乘a，lazy3标记赋值c
}segtree[maxn*]; void push_up(int i) {
segtree[i].cnt1 = (segtree[lson].cnt1 + segtree[rson].cnt1) % mod;
segtree[i].cnt2 = (segtree[lson].cnt2 + segtree[rson].cnt2) % mod;
segtree[i].cnt3 = (segtree[lson].cnt3 + segtree[rson].cnt3) % mod;
} void push_down(int i){
if(segtree[i].lazy3){
ll tmp = segtree[i].lazy3*segtree[i].lazy3%mod*segtree[i].lazy3%mod;
segtree[lson].lazy1=segtree[rson].lazy1=;
segtree[lson].lazy2=segtree[rson].lazy2=;
segtree[lson].lazy3=segtree[rson].lazy3=segtree[i].lazy3; segtree[lson].cnt3 = (segtree[lson].r - segtree[lson].l + )*tmp%mod;
segtree[rson].cnt3 = (segtree[rson].r - segtree[rson].l + )*tmp%mod; segtree[lson].cnt2 =(segtree[lson].r - segtree[lson].l + )*segtree[i].lazy3%mod*segtree[i].lazy3%mod;
segtree[rson].cnt2 = (segtree[rson].r - segtree[rson].l + )*segtree[i].lazy3%mod*segtree[i].lazy3%mod; segtree[lson].cnt1 =(segtree[lson].r - segtree[lson].l + )*segtree[i].lazy3%mod;
segtree[rson].cnt1 = (segtree[rson].r - segtree[rson].l + )*segtree[i].lazy3%mod; segtree[i].lazy3 = ;
}
if(segtree[i].lazy1!=||segtree[i].lazy2!=){
ll add = segtree[i].lazy1, mul = segtree[i].lazy2;
ll l1=segtree[lson].cnt1,l2=segtree[lson].cnt2,l3=segtree[lson].cnt3;
ll r1=segtree[rson].cnt1,r2=segtree[rson].cnt2,r3=segtree[rson].cnt3;
ll tmp = mul*mul%mod*mul%mod; segtree[lson].lazy1=(segtree[lson].lazy1*mul%mod+add)%mod;
segtree[rson].lazy1=(segtree[rson].lazy1*mul%mod+add)%mod;
segtree[lson].lazy2=segtree[lson].lazy2*mul%mod;
segtree[rson].lazy2=segtree[rson].lazy2*mul%mod; segtree[lson].cnt3=(segtree[lson].cnt3*tmp%mod + add*add%mod*add%mod*(segtree[lson].r - segtree[i].l + )%mod + *segtree[lson].cnt2*mul%mod*mul%mod*add%mod + *segtree[lson].cnt1*mul%mod*add%mod*add%mod)%mod;
segtree[rson].cnt3=(segtree[rson].cnt3*tmp%mod + add*add%mod*add%mod*(segtree[rson].r - segtree[rson].l + )%mod + *segtree[rson].cnt2*mul%mod*mul%mod*add%mod + *segtree[rson].cnt1*mul%mod*add%mod*add%mod)%mod; segtree[lson].cnt2=(segtree[lson].cnt2*mul%mod*mul%mod + add*add%mod*(segtree[lson].r - segtree[i].l + )%mod + *mul*add*segtree[lson].cnt1)%mod;
segtree[rson].cnt2=(segtree[rson].cnt2*mul%mod*mul%mod + add*add%mod*(segtree[rson].r - segtree[rson].l + )%mod + *mul*add*segtree[rson].cnt1)%mod; segtree[lson].cnt1=(segtree[lson].cnt1*mul+add*(segtree[lson].r - segtree[i].l + ))%mod;
segtree[rson].cnt1=(segtree[rson].cnt1*mul+add*(segtree[rson].r - segtree[rson].l + ))%mod; segtree[i].lazy1 = ;segtree[i].lazy2 = ;
}
} void build(int i, int l, int r) {
segtree[i].l = l, segtree[i].r = r;
segtree[i].cnt1 = segtree[i].cnt2 = segtree[i].cnt3 = ;
segtree[i].lazy1 = segtree[i].lazy3 = ;
segtree[i].lazy2 = ;
if(l == r) return;
int mid = (l + r) >> ;
build(lson, l, mid);
build(rson, mid + , r);
push_up(i);
} void update(int i, int l, int r, ll c, int op) {
if(segtree[i].l == l && segtree[i].r == r) {
if(op == ) {
segtree[i].cnt1 = c % mod * (segtree[i].r - segtree[i].l + ) % mod;
segtree[i].cnt2 = c * c % mod * (segtree[i].r - segtree[i].l + ) % mod;
segtree[i].cnt3 = c * c % mod * c % mod * (segtree[i].r - segtree[i].l + ) % mod;
segtree[i].lazy3 = c;
segtree[i].lazy2 = ;
segtree[i].lazy1 = ;
return;
} else if(op == ) {
segtree[i].cnt1 = c * segtree[i].cnt1 % mod;
segtree[i].cnt2 = c * c % mod * segtree[i].cnt2 % mod;
segtree[i].cnt3 = c * c % mod * c %mod * segtree[i].cnt3 % mod;
segtree[i].lazy2 = segtree[i].lazy2 * c % mod;
segtree[i].lazy1 = segtree[i].lazy1 * c % mod;
return;
} else {
segtree[i].lazy1 = (c + segtree[i].lazy1) % mod;
ll sum1 = segtree[i].cnt1, sum2 = segtree[i].cnt2, sum3 = segtree[i].cnt3;
segtree[i].cnt1 = (sum1 + c * (segtree[i].r - segtree[i].l + )) % mod;
segtree[i].cnt2 = ((sum2 % mod + * c % mod * sum1 % mod) % mod + c * c % mod * (segtree[i].r - segtree[i].l + ) % mod) % mod;
segtree[i].cnt3 = ((sum3 % mod + * c % mod * (sum2 + sum1 * c) % mod) % mod + c * c % mod * c * (segtree[i].r - segtree[i].l + ) % mod) % mod;
return;
}
}
push_down(i);
int mid = (segtree[i].l + segtree[i].r) >> ;
if(l > mid) update(rson, l, r, c, op);
else if(r <= mid) update(lson, l, r, c, op);
else {
update(lson, l, mid, c, op);
update(rson, mid + , r, c, op);
}
push_up(i);
} ll query(int i, int l, int r, int op) {
if(segtree[i].l == l && segtree[i].r == r) {
if(op == ) return segtree[i].cnt1;
if(op == ) return segtree[i].cnt2;
if(op == ) return segtree[i].cnt3;
}
push_down(i);
int mid = (segtree[i].l + segtree[i].r) >> ;
if(l > mid) return query(rson, l, r, op);
else if(r <= mid) return query(lson, l, r, op);
else {
return (query(lson, l, mid, op) + query(rson, mid + , r, op)) % mod;
}
} int main() {
//FIN;
while(~scanf("%d%d", &n, &q)) {
if(n == && q == ) break;
build(, , n);
while(q--) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if(op == ) {
printf("%lld\n", query(, x, y, z));
} else {
z %= mod;
update(, x, y, z, op);
}
}
}
return ;
}