【题目描述】 给定一个长度为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*2] + sum[num*2|1]; maxn[num] = max(maxn[num*2], maxn[num*2|1]); 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*2, pos, (pos+y)/2); build(num*2|1, (pos+y)/2+1 ,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*2, pos, y, val); mod(num*2|1, 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]) / 2) act(num*2, pos, y); else act(num*2|1, pos, y); upd(num); } ll output(int num, int pos, int y) { if(pos>r[num] || y<l[num]) fuck 0; if(pos<=l[num] && y>=r[num]) fuck sum[num]; fuck output(num*2, pos, y) + output(num*2|1, pos, y); } int main() { freopen("mod.in", "r", stdin); freopen("mod.out", "w", stdout); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { scanf("%d", &arr[i]); } build(1, 1, n); int pos, y, val, opt; while(m--) { scanf("%d", &opt); switch(opt) { case 1: scanf("%d%d", &pos, &y); printf("%lld ", output(1, pos, y)); break; case 2: scanf("%d%d%d", &pos, &y, &val); mod(1, pos, y, val); break; case 3: scanf("%d%d", &pos, &y); act(1, pos, y); break; } } fuck 0; } //being fucked by this code (2) hr (16) min
