Codeforces Round #250 (Div. 1)D:http://codeforces.com/problemset/problem/438/D
题意：给你一个序列，然后有3种操作 1x y.表示查询[x,y]之间的区间和，2 x y z表示把[x y]内的数%z,3x y,表示把第x个数变成y。
题解：肯定是用线段树来维护，但是一开始想不到维护什么统计量，对于区间取模，没办法用lazy标记，更新到第的话，肯定会T。后来，认为既然没办法用lazy,那么只能用别的方法来优化更新。发现每次取模之后，数都会变小，如果要取模的数比当前模数小的话，就不用取模，于是可以维护区间最大值，如果区间最大值都小于模数的话，这个区间肯定不用更新，这样来减少更新。这样的方法，其实以前也做过，就是对于一个区间内的数进行开平方操作，每个数会越开越小，到了1的时候就可以直接不开了。因此，对于线段树的区间更新来说：1如果能找到好的lazy可以标记的话，就使用lazy标记；2如果找不到就要想办法优化区间更新，让单点更新的次数变少。另外此题，自己用线段树省空间的写法，结果不熟练，一个地方写错，最后wa几发。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+;
int n,m;
long long sum[N*],maxn[N*];
void pushup(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
maxn[rt]=max(maxn[rt<<],maxn[rt<<|]);
}
void build(int l,int r,int rt){
if(l==r){
scanf("%I64d",&maxn[rt]);
sum[rt]=maxn[rt];
return;
}
int mid=(l+r)/;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
void update(int l,int r,int rt,int from,int to,long long mod){
if(maxn[rt]<mod)return;
if(l==r){
maxn[rt]%=mod;
sum[rt]=maxn[rt];
return;
}
int mid=(l+r)/;
if(mid>=to)update(l,mid,rt<<,from,to,mod);
else if(mid<from)update(mid+,r,rt<<|,from,to,mod);
else{
update(l,mid,rt<<,from,mid,mod);
update(mid+,r,rt<<|,mid+,to,mod);
}
pushup(rt);
}
void update2(int l,int r,int rt,int pos,long long val){
if(l==r){
maxn[rt]=val;
sum[rt]=val;
return;
}
int mid=(l+r)/;
if(mid>=pos)update2(l,mid,rt<<,pos,val);
else update2(mid+,r,rt<<|,pos,val);
pushup(rt);
}
long long query(int l,int r,int rt,int from,int to){
if(l==from&&r==to){
return sum[rt];
}
int mid=(l+r)/;
if(mid>=to)return query(l,mid,rt<<,from,to);
else if(mid<from)return query(mid+,r,rt<<|,from,to);
else {
return query(l,mid,rt<<,from,mid)+query(mid+,r,rt<<|,mid+,to); }
}
int t,t1,t4;
long long t2,t3;
int main(){
while(~scanf("%d%d",&n,&m)){
memset(sum,,sizeof(sum));
memset(maxn,,sizeof(maxn));
build(,n,);
for(int i=;i<=m;i++){
scanf("%d%d",&t,&t1);
if(t==){
scanf("%d",&t4);
printf("%I64d\n",query(,n,,t1,t4));
}
else if(t==){
scanf("%d%I64d",&t4,&t2);
update(,n,,t1,t4,t2);
}
else{
scanf("%I64d",&t2);
update2(,n,,t1,t2);
}
}
}
}