Codeforces Round #250 (Div. 1) D 线段树
2014-09-03 11:04:34         来源：0922

```int n,m;

ll nnum[100000 + 55];

typedef struct Node {
int l,r;
ll sum;
ll maxn;
};

Node tree[100000 * 4 + 55];

void init() {
memset(nnum,0,sizeof(nnum));
}

bool input() {
while(cin>>n>>m) {
for(int i=1;i<=n;i++)scanf("%I64d",&nnum[i]);
return false;
}
return true;
}

void push_up(int id) {
tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
tree[id].maxn = max(tree[id<<1].maxn,tree[id<<1|1].maxn);
}

void build(int l,int r,int id) {
tree[id].l = l;
tree[id].r = r;
tree[id].maxn = 0;
tree[id].sum = 0;
if(l == r) {
tree[id].maxn = nnum[l];
tree[id].sum = nnum[l];
return ;
}
int mid = (l + r)>>1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
push_up(id);
}

ll query(int l,int r,int id) {
if(tree[id].l == l && tree[id].r == r)return tree[id].sum;
int mid = (tree[id].l + tree[id].r)>>1;
if(r <= mid) return query(l,r,id<<1);
else if(l > mid) return query(l,r,id<<1|1);
else
return query(l,mid,id<<1) + query(mid + 1,r,id<<1|1);
}

void update(int l,int r,ll x,int id) {
if(tree[id].maxn < x) return ;
int mid = (tree[id].l + tree[id].r)>>1;
if(tree[id].l == tree[id].r) {
tree[id].sum %= x;
tree[id].maxn = tree[id].sum;
return ;
}
if(r <= mid)update(l,r,x,id<<1);
else if(l > mid)update(l,r,x,id<<1|1);
else {
update(l,mid,x,id<<1);
update(mid + 1,r,x,id<<1|1);
}
push_up(id);
}

void update2(int pos,int val,int id) {
if(tree[id].l == tree[id].r) {
tree[id].sum = tree[id].maxn = val;
return ;
}
int mid = (tree[id].l + tree[id].r)>>1;
if(pos <= mid)update2(pos,val,id<<1);
else update2(pos,val,id<<1|1);
push_up(id);
}

void cal() {
build(1,n,1);
int q = m;
while(q--) {
int type;
scanf("%d",&type);
if(type == 1) {
int l,r;
scanf("%d %d",&l,&r);
ll ans = query(l,r,1);
printf("%I64d\n",ans);
}
else if(type == 2) {
int l,r;
ll x;
scanf("%d %d %I64d",&l,&r,&x);
update(l,r,x,1);
}
else {
int k,x;
scanf("%d %d",&k,&x);
update2(k,x,1);
}
}
}

void output() {

}

int main() {
while(true) {
init();
if(input())return 0;
cal();
output();
}
return 0;
}
```