「CF52C」Circular RMQ

概述更好的阅读体验 Portal Portal1: Codeforces Portal2: Luogu Description You are given circular array \(a_0, a_1, \cdots, a_{n - 1}\). There are two types of operations with it: inc(\(lf\), \(rg\), \(v\)) — this

更好的阅读体验

Portal

Portal1: Codeforces

Portal2: Luogu

Description

You are given circular array \(a_0,a_1,\cdots,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,1\).

Write program to process given sequence of operations.

input

The first line contains integer \(n (1 \le n \le 200000)\). The next line contains initial state of the array: \(a_0,a_{n - 1} ( -10^6 \le ai \le 10^6)\),\(a_i\) are integer. The third line contains integer \(m (0 \le m \le 200000)\),\(m\) — the number of operartons. Next \(m\) lines contain one operation each. If line contains two integer \(lf,rg (0 \le lf,rg \le n - 1)\) it means rmq operation,it contains three integers \(lf,rg,v (0 \le lf,rg \le n - 1; -10^6 \le v \le 10^6)\) — 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

41 2 3 443 03 0 -10 12 1

Sample Output

100

Solution

我们可以用线段树来解决区间RMQ问题，我们在线段树上维护一个最小值与懒标记，这样问题就解决了。

读入的时候我们可以判断后面一个字符是不是空格，可以直接在快速读入里判断，这样就可以判断出一行有三个数还是两个数。

Code

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int MAXN = 200005;int n,m,l,r,val,a[MAXN];bool opt;namespace Segtree {    #define ls rt << 1    #define rs rt << 1 | 1    typedef long long LL;    const LL Seg_INF = 1e18;    const int Seg_MAXN = 1000005;    struct SMT {        LL Min,tag;    } tree[Seg_MAXN];    inline voID build(int rt,int l,int r) {//建立线段树        if (l == r) {            tree[rt].Min = a[l];            return ;        }        int mID = l + r >> 1;        build(ls,mID);        build(rs,mID + 1,r);        tree[rt].Min = min(tree[ls].Min,tree[rs].Min);    }    inline voID update(int rt,int r,int ansl,int ansr,int val) {//线段树修改        if (ansl <= l && r <= ansr) {            tree[rt].tag += val;            return ;        }        int mID = l + r >> 1;        if (ansl <= mID) update(ls,mID,ansl,ansr,val);        if (mID < ansr) update(rs,val);        tree[rt].Min = min(tree[ls].Min + tree[ls].tag,tree[rs].Min + tree[rs].tag);    }    inline LL query(int rt,int ansr) {//线段树查询        if (ansl <= l && r <= ansr) return tree[rt].Min + tree[rt].tag;        int mID = l + r >> 1;        LL ret = Seg_INF;        if (ansl <= mID) ret = min(ret,query(ls,ansr));        if (mID < ansr) ret = min(ret,query(rs,ansr));        return ret + tree[rt].tag;    }}using namespace Segtree;inline int read() {    opt = 0;    char ch = getchar();    int x = 0,f = 1;    while (ch < '0' || ch > '9') {        if (ch == '-') f = -1;        ch = getchar();    }    while ('0' <= ch && ch <= '9') {        x = (x << 1) + (x << 3) + ch - '0';        ch = getchar();    }    if (ch == ' ') opt = 1;//判断空格    return x * f;}int main() {    n = read();    for (int i = 1; i <= n; i++)        a[i] = read();    build(1,1,n);    m = read();    for (int i = 1; i <= m; i++) {        l = read(); r = read(); L++; r++;        if (!opt) {            if (l <= r) printf("%lld\n",query(1,n,r)); else printf("%lld\n",min(query(1,n),r)));        } else {            val = read();            if (l <= r) update(1,val); else {                update(1,val);                update(1,val);            }        }    }    return 0;}

总结

以上是内存溢出为你收集整理的「CF52C」Circular RMQ全部内容，希望文章能够帮你解决「CF52C」Circular RMQ所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。