CF#52 C Circular RMQ （线段树区间更新）

Description

You are given circular array a₀, a₁, ..., a_n - 1.
There are two types of operations with it:

inc(lf, rg, v) — this operation increases each element on the segment
[lf, rg] (inclusively) by
v;
rmq(lf, rg) — this operation returns minimal value on the segment
[lf, rg] (inclusively).

Assume segments to be circular, so if n = 5 and
lf = 3, rg = 1, it means the index sequence:
3, 4, 0, 1.

Write program to process given sequence of operations.

Input

The first line contains integer n (1 ≤ n ≤ 200000). The next line contains initial state of the array:
a₀, a₁, ..., a_n - 1
( - 10⁶ ≤ a_i ≤ 10⁶),
a_i are integer. The third line contains integer
m (0 ≤ m ≤ 200000),
m — the number of operartons. Next
m lines contain one operation each. If line contains two integer
lf, rg (0 ≤ lf, rg ≤ n - 1) it means
rmq operation, it contains three integers
lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 10⁶ ≤ v ≤ 10⁶)
— inc operation.

Output

For each rmq operation write result for it. Please, do not use
%lld specificator to read or write 64-bit integers in C++. It is preffered to use
cout (also you may use
%I64d).

Sample Input

Input

Output

题意非常好理解。

假设a>b的话，就查0~b和a~n-1，其余的就是线段树区间更新模板，推断m个询问里是否存在c，详见代码，非常好理解。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <ctype.h>

#include <iostream>

#define lson o << 1, l, m

#define rson o << 1|1, m+1, r

using namespace std;

typedef __int64 LL;

const __int64 MAX =  9223372036854775807;

const int maxn = 200010;

int n, a, q, c, b;

char str[1200];

LL mi[maxn<<2], add[maxn<<2];

void up(int o) {

    mi[o] = min(mi[o<<1], mi[o<<1|1]);

}

void down(int o) {

    if(add[o]) {

        add[o<<1] += add[o];

        add[o<<1|1] += add[o];

        mi[o<<1] += add[o];

        mi[o<<1|1] += add[o];

        add[o] = 0;

    }

}

void build(int o, int l, int r) {

    if(l == r) {

        scanf("%I64d", &mi[o]);

        return;

    }

    int m = (l+r) >> 1;

    build(lson);

    build(rson);

    up(o);

}

void update(int o, int l, int r) {

    if(a <= l && r <= b) {

        add[o] += c;

        mi[o] += c;

        return ;

    }

    down(o);

    int m = (l+r) >> 1;

    if(a <= m) update(lson);

    if(m < b ) update(rson);

    up(o);

}

LL query(int o, int l, int r) {

    if(a <= l && r <= b) return mi[o];

    down(o);

    int m = (l+r) >> 1;

    LL res = MAX;

    if(a <= m) res = query(lson);

    if(m < b ) res = min(res, query(rson));

    return res;

}

int main()

{

    scanf("%d", &n);

    build(1, 0, n-1);

    scanf("%d", &q); getchar(); while(q--) {

        gets(str);

        if(sscanf(str,"%d %d %d", &a, &b, &c) == 3)  {

            if(a <= b) update(1, 0, n-1);

            else {

                int tmp = b;

                b = n-1; update(1, 0, n-1);

                a = 0, b = tmp; update(1, 0, n-1);

            }

        } else {

            LL ans ;

            if(a <= b) ans = query(1, 0, n-1);

            else {

                int tmp = b;

                b = n-1; ans = query(1, 0, n-1);

                a = 0, b = tmp; ans = min(ans, query(1, 0, n-1));

            }

            printf("%I64d\n", ans);

        }

    }

    return 0;

}

巴特西

CF#52 C Circular RMQ （线段树区间更新）

最新文章

热门文章