hdu4578:http://acm.hdu.edu.cn/showproblem.php?pid=4578
题意：
给一个序列 {an}，有 4 种操作。
1、将一段区间的数全部加 c。
2、将一段区间的数全部乘 c。
3、将一段区间的数全部等于 c。
4、询问一段区间的和（和、平方和、立方和）。
解题思路：
这道题自己完全不会打，虽然知道思路。所以借鉴了大神的代码。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + ;
const int mod = ;
#define lson u<<1
#define rson u<<1|1 inline int sqr2(int x){
return x * x % mod;
} inline int sqr3(int x){
return sqr2(x) * x % mod;
} struct SegTree{
int l,r;
int sum[];
int mul,add;
inline int mid(){
return (l+r)>> ;
}
inline int len(){
return r-l+;
}
void flag_init(){
add = , mul = ;
}
void to_mul(int m){
(sum[] *= m) %= mod;
(sum[] *= sqr2(m)) %= mod;
(sum[] *= sqr3(m)) %= mod; (mul *= m) %= mod;
(add *= m) %= mod;
}
void to_add(int a){
(sum[] += sqr3(a) * len()) %= mod;
(sum[] += * a * sum[]) %= mod;
(sum[] += * sqr2(a) * sum[]) %= mod; (sum[] += sqr2(a) * len()) %= mod;
(sum[] += * a * sum[]) %= mod; (sum[] += a * len()) %= mod; (add += a) %= mod;
}
}T[N<<];
void build(int u,int l,int r){
T[u].l = l , T[u].r = r;
memset(T[u].sum,,sizeof(T[u].sum));
T[u].flag_init();
if(l==r)
return ;
int m = T[u].mid();
build(lson,l,m);
build(rson,m+,r);
}
int op;
void push_down(int u){
T[lson].to_mul(T[u].mul);
T[rson].to_mul(T[u].mul);
T[lson].to_add(T[u].add);
T[rson].to_add(T[u].add);
T[u].flag_init();
}
void push_up(int u){
for(int i=;i<=;i++)
T[u].sum[i] = (T[lson].sum[i] + T[rson].sum[i]) % mod;
} void updata(int u,int l,int r,int mul,int add){
if(T[u].l == l && T[u].r == r){
T[u].to_mul(mul);
T[u].to_add(add);
return ;
}
push_down(u);
int m = T[u].mid();
if(r <= m)
updata(lson,l,r,mul,add);
else if(l >m)
updata(rson,l,r,mul,add);
else
updata(lson,l,m,mul,add), updata(rson,m+,r,mul,add);
push_up(u);
}
int query(int u,int l,int r){
if(T[u].l == l && T[u].r == r)
return T[u].sum[op];
push_down(u);
int m = T[u].mid();
if(r <= m)
return query(lson,l,r);
else if(l >m)
return query(rson,l,r);
else
return (query(lson,l,m)+query(rson,m+,r)) % mod;
} int main(){
int n,m,a,b,c;
while(scanf("%d%d",&n,&m),n||m){
build(,,n+);
while(m--){
scanf("%d",&op);
if(op == ){
scanf("%d%d%d",&a,&b,&op);
printf("%d\n",query(,a,b));
}
else{
scanf("%d%d%d",&a,&b,&c);
if(op == )
updata(,a,b,,c);
else if(op == )
updata(,a,b,c,);
else
updata(,a,b,,c);
}
}
}
return ;
}