【题目描述】 给定一个长度为n的非负整数序列a，你需要支持以下操作： 1：给定l,r，输出a[l]+a[l+1]+…+a[r]。 2：给定l,r,x，将a[l],a[l+1],…,a[r]对x取模。 3：给定k,y，将a[k]修改为y。
【输入数据】 第一行两个整数n,m。 第二行n个整数a[1]~a[n]。 接下来m行每行3或4个整数表示操作。
【输出数据】 对于每个操作1，输出一行一个整数表示答案。
【样例输入】 5 5 1 2 3 4 5 2 3 5 4 3 3 5 1 2 5 2 1 3 3 1 1 3
【样例输出】 8 5
【数据范围】 对于40%的数据，n,m<=1000。 对于100%的数据，n,m<=100000，1<=l<=r<=n，1<=k<=n，1<=x<=10^9， 0<=a[i],y<=10^9。
用线段树处理，用线段树维护区间最大值以及区间和。
进行取模操作时，如果x> 区间最大值那么退出，否则两边都递归下去。
（其实第一次做也不太明白，套模板加瞎蒙数据结果还真ac了）
这里先码一下，再复习一下线段树之后编辑详细思路。
#include <bits/stdc++.h>
#define N 1000010
#define fuck return
using namespace std;
typedef long long ll;
int n, m;
int arr[N], l[N], r[N], maxn[N];
ll sum[N]; void upd(int num) {
sum[num] = sum[num*] + sum[num*|];
maxn[num] = max(maxn[num*], maxn[num*|]);
fuck;
}
void build(int num, int pos, int y) {
l[num] = pos, r[num]=y;
if(pos == y) {
maxn[num] = arr[pos];
sum[num] = arr[pos];
fuck;
}
build(num*, pos, (pos+y)/);
build(num*|, (pos+y)/+ ,y);
upd(num);
}
void mod(int num, int pos, int y, int val) {
if(pos>r[num] || y<l[num] || maxn[num]<val) fuck;
if(l[num] == r[num]) {
sum[num] %= val;
maxn[num] = sum[num];
fuck;
}
mod(num*, pos, y, val);
mod(num*|, pos, y, val);
upd(num);
}
void act(int num, int pos, int y) {
if(l[num] == r[num]) {
maxn[num] = y;
sum[num] = y;
fuck;
}
if(pos <= (l[num] + r[num]) / ) act(num*, pos, y);
else act(num*|, pos, y);
upd(num);
}
ll output(int num, int pos, int y) {
if(pos>r[num] || y<l[num]) fuck ;
if(pos<=l[num] && y>=r[num]) fuck sum[num];
fuck output(num*, pos, y) + output(num*|, pos, y);
} int main() {
freopen("mod.in", "r", stdin);
freopen("mod.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++) {
scanf("%d", &arr[i]);
}
build(, , n);
int pos, y, val, opt;
while(m--) {
scanf("%d", &opt);
switch(opt) {
case :
scanf("%d%d", &pos, &y);
printf("%lld\n", output(, pos, y));
break;
case :
scanf("%d%d%d", &pos, &y, &val);
mod(, pos, y, val);
break;
case :
scanf("%d%d", &pos, &y);
act(, pos, y);
break;
}
}
fuck ;
}
//being fucked by this code (2) hr (16) min