search

线段树

hashtag
线段树

给n个数a1,a2,a3…ana_{1},a_{2},a_{3}…a_{n}。

支持q个操作：

  1. 1 x d，修改ax=da_{x}=d。

  2. 2 l r，查询mini=lraimin_{i=l}^{r}a_{i}，并且求出最小值出现了多少次。

const int N = 200010;
int n, q;
int a[N];
​
struct info {
    int minv, mincnt;
};
​
info operator+(const info& l, const info& r) {
    info a;
    a.minv = min(l.minv, r.minv);
    if (l.minv == r.minv) a.mincnt = l.mincnt + r.mincnt;
    else if (l.minv < r.minv) a.mincnt = l.mincnt;
    else a.mincnt = r.mincnt;
    return a;
}
​
struct node {
    info val;
}seg[N * 4];
​
void update(int id) {
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
​
void build(int id, int l, int r) {
    if (l == r) {
        seg[id].val = { a[l],1 };
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r); 
        update(id);
    }
}
​
//节点为id,对应的区间为[l,r]，修改a[pos]为val
void change(int id, int l, int r, int pos, int val) {
    if (l == r) seg[id].val = { val,1 };
    else {
        int mid = (l + r) / 2;
        if (pos <= mid) change(id * 2, l, mid, pos, val);
        else change(id * 2 + 1, mid + 1, r, pos, val);
        update(id);
    }
}
​
info query(int id, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) return seg[id].val;
    int mid = (l + r) / 2;
    //[l,mid]   [mid+1,r]
    if (qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}
​
void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int x, d;
            scanf("%d%d", &x, &d);
            change(1, 1, n, x, d);
        }
        else {
            int l, r; scanf("%d%d", &l, &r);
            info ans = query(1, 1, n, l, r);
            printf("%d %d\n", ans.minv, ans.mincnt);
        }
    }
}
​
signed main()
{
    int T;
    //T = read();
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

给n个数a1,a2,a3…ana_{1},a_{2},a_{3}…a_{n}。

支持q个操作：

  1. 1 x d，修改ax=da_{x}=d。

  2. 2 l r，查询[l,r]中的最大子段和，也就是找到l≤l′≤r′≤r，使得∑i=l′r′ai\sum_{i=l'}^{r'}a_{i}最大。

给n个数a1,a2,a3…ana_{1},a_{2},a_{3}…a_{n}。

支持q个操作：

  1. 1 l r d，令所有的aia_{i}(l≤i≤r)加上d。

  2. 2 l r，查询maxi=lraimax_{i=l}^{r}a_{i}。

给n个数a1,a2,a3…ana_{1},a_{2},a_{3}…a_{n}。

支持q个操作：

  1. 1 l r d，令所有的aia_{i}(l≤i≤r)加上d。

  2. 2 l r d，令所有的aia_{i}(l≤i≤r)乘上d。

  3. 3 l r d，令所有的aia_{i}(l≤i≤r)等于d。

  4. 4 l r，查询∑i=lraimod(109+7)\sum_{i=l}^{r}a_{i}mod(10^{9}+7)。

Last updated