题目大意
区间取模,区间求和,单点修改。
分析
其实算是一道蛮简单的水题。
首先线段树非常好解决后两个操作,重点在于如何解决区间取模的操作。
一开始想到的是暴力单点修改,但是复杂度就飙到了\(mnlogn\),直接爆炸。
但是重新看到了题目中给出的4s的操作,说明,我们可以优化单点修改的操作。
那么我们顺便维护一下区间的最大值,如果当前的区间的最大值是小于mod数的,那么这个区间内的所有数都是没有必要mod的。
后面随着数据的越来越大,那么就可以剪去不必要的操作。
代码
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
struct segment_tree {
#define lc (nod << 1)
#define rc (nod << 1 | 1)
#define mid ((l + r) >> 1)
struct node {
ll s;
int l, r, mx;
node() {
mx = s = 0;
}
}tr[N << 2];
void pushup(int nod) {
tr[nod].s = tr[lc].s + tr[rc].s;
tr[nod].mx = max(tr[lc].mx, tr[rc].mx);
}
void build(int l, int r, int nod, int *a) {
tr[nod].l = l, tr[nod].r = r;
if (l == r) {
tr[nod].mx = tr[nod].s = a[l];
return;
}
build(l, mid, lc, a);
build(mid + 1, r, rc, a);
pushup(nod);
}
ll query_sec_sum(int nod, int ql, int qr) {
ll res = 0;
int l = tr[nod].l, r = tr[nod].r;
if (ql <= l && r <= qr) return tr[nod].s;
if (ql <= mid) res += query_sec_sum(lc, ql, qr);
if (qr > mid) res += query_sec_sum(rc, ql, qr);
return res;
}
void update_point(int nod, int k, int val) {
int l = tr[nod].l, r = tr[nod].r;
if (l == r) {
tr[nod].mx = tr[nod].s = val;
return;
}
if (k <= mid) update_point(lc, k, val);
else update_point(rc, k, val);
pushup(nod);
}
void update_sec_mod(int nod, int ql, int qr, int p) {
int l = tr[nod].l, r = tr[nod].r;
if (tr[nod].mx < p) return;
if (l == r) {
tr[nod].s %= p;
tr[nod].mx %= p;
return;
}
if (ql <= mid) update_sec_mod(lc, ql, qr, p);
if (qr > mid) update_sec_mod(rc, ql, qr, p);
pushup(nod);
}
}tr;
int a[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
tr.build(1, n, 1, a);
while(m --) {
int opt, x, y, z;
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d", &x, &y);
printf("%lld\n", tr.query_sec_sum(1, x, y));
}
if (opt == 2) {
scanf("%d%d%d", &x, &y, &z);
tr.update_sec_mod(1, x, y, z);
}
if (opt == 3) {
scanf("%d%d", &x, &z);
tr.update_point(1, x, z);
}
}
return 0;
}