水题

P8024 [ONTAK2015] Stumilowy sad[1]

#include<bits/stdc++.h>
#define ls (x<<1)
#define rs (ls|1)
#define inf 0x3f3f3f3f
#define unsigned int
#define mids(l,r) const auto mid = l+r>>1
using cint = const unsigned&;
using funtype = cint(cint, cint);
using todo = void(cint, cint, cint, cint, cint, cint);
using namespace std;
constexpr int maxn = 2000010;
unsigned maxv[maxn << 2], mins[maxn << 2], maxs[maxn << 2], val[maxn], n, k, l, r, h;
template<funtype min>
inline void pushto(cint x, cint v) {
    mins[x] = min(mins[x], v);
    maxs[x] = min(maxs[x], v);
    maxv[x] = min(maxv[x], v);
}
inline void addto(cint x, cint v) {
    mins[x] += v;
    maxs[x] += v;
    val[x] += v;
    maxv[x] += v;
}
inline void pushdown(cint x) {
    addto(ls, val[x]);
    addto(rs, val[x]);
    pushto<max>(ls, maxs[x]);
    pushto<max>(rs, maxs[x]);
    pushto<min>(ls, mins[x]);
    pushto<min>(rs, mins[x]);
    mins[x] = inf;
    maxs[x] = -inf;
    val[x] = 0;
}
inline void pushup(cint x) {
    maxv[x] = max(maxv[ls], maxv[rs]);
}
template<funtype min>
void update(cint x, cint ml, cint mr, cint ql, cint qr, cint v) {
    if (ql <= ml && mr <= qr)
        return pushto<min>(x, v);
    pushdown(x);
    mids(ml, mr);
    if (mid >= ql) update<min>(ls, ml, mid, ql, qr, v);
    if (mid < qr) update<min>(rs, mid + 1, mr, ql, qr, v);
    pushup(x);
}
void add(cint x, cint ml, cint mr, cint ql, cint qr, cint v) {
    if (ql <= ml && mr <= qr)
        return addto(x, v);
    pushdown(x);
    mids(ml, mr);
    if (mid >= ql) add(ls, ml, mid, ql, qr, v);
    if (mid < qr) add(rs, mid + 1, mr, ql, qr, v);
    pushup(x);
}
int ht[maxn];
void build(cint x, cint l, cint r) {
    mins[x] = inf;
    maxs[x] = -inf;
    if (l == r) {
        maxv[x] = ht[l];
        return;
    }
    mids(l, r);
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(x);
}
int res;
void get(cint x, cint ml, cint mr, cint ql, cint qr, cint v = 0) {
    if (ql <= ml && mr <= qr)
        return res = maxv[x], x == 1 && cout << res << 'n', void(0);
    pushdown(x);
    mids(ml, mr);
    int ans = -inf;
    res = -inf;
    if (mid >= ql) get(ls, ml, mid, ql, qr);
    ans = max(ans, res);
    res = -inf;
    if (mid < qr) get(rs, mid + 1, mr, ql, qr);
    ans = max(ans, res);
    if (x == 1) cout << ans << 'n';
    res = ans;
}
char t;
const todo* funs[]{ add,update<min>,update<max>,get };
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> ht[i];
    }
    build(1, 1, n);
    while (k--) {
        cin >> t >> l >> r;
        if (t != '4')cin >> h;
        funs[t - '1'](1, 1, n, l, r, h);
    }
}

有意思。

#include<bits/stdc++.h>
#define ls (x<<1)
#define rs (ls|1)
#define inf 0x3f3f3f3f
#define unsigned int
#define mids(l,r) const auto mid = l+r>>1
using cint = const unsigned&;
using funtype = cint(cint, cint);
using todo = void(cint, cint, cint, cint, cint, cint);
using namespace std;
constexpr int maxn = 2000010;
unsigned maxv[maxn << 2], mins[maxn << 2], maxs[maxn << 2], val[maxn], n, k, l, r, h;
template<funtype min>
inline void pushto(cint x, cint v) {
mins[x] = min(mins[x], v);
maxs[x] = min(maxs[x], v);
maxv[x] = min(maxv[x], v);
}
inline void addto(cint x, cint v) {
mins[x] += v;
maxs[x] += v;
val[x] += v;
maxv[x] += v;
}
inline void pushdown(cint x) {
addto(ls, val[x]);
addto(rs, val[x]);
pushto<max>(ls, maxs[x]);
pushto<max>(rs, maxs[x]);
pushto<min>(ls, mins[x]);
pushto<min>(rs, mins[x]);
mins[x] = inf;
maxs[x] = -inf;
val[x] = 0;
}
inline void pushup(cint x) {
maxv[x] = max(maxv[ls], maxv[rs]);
}
template<funtype min>
void update(cint x, cint ml, cint mr, cint ql, cint qr, cint v) {
if (ql <= ml && mr <= qr)
return pushto<min>(x, v);
pushdown(x);
mids(ml, mr);
if (mid >= ql) update<min>(ls, ml, mid, ql, qr, v);
if (mid < qr) update<min>(rs, mid + 1, mr, ql, qr, v);
pushup(x);
}
void add(cint x, cint ml, cint mr, cint ql, cint qr, cint v) {
if (ql <= ml && mr <= qr)
return addto(x, v);
pushdown(x);
mids(ml, mr);
if (mid >= ql) add(ls, ml, mid, ql, qr, v);
if (mid < qr) add(rs, mid + 1, mr, ql, qr, v);
pushup(x);
}
int ht[maxn];
void build(cint x, cint l, cint r) {
mins[x] = inf;
maxs[x] = -inf;
if (l == r) {
maxv[x] = ht[l];
return;
}
mids(l, r);
build(ls, l, mid), build(rs, mid + 1, r);
pushup(x);
}
int res;
void get(cint x, cint ml, cint mr, cint ql, cint qr, cint v = 0) {
if (ql <= ml && mr <= qr)
return res = maxv[x], x == 1 && cout << res << '\n', void(0);
pushdown(x);
mids(ml, mr);
int ans = -inf;
res = -inf;
if (mid >= ql) get(ls, ml, mid, ql, qr);
ans = max(ans, res);
res = -inf;
if (mid < qr) get(rs, mid + 1, mr, ql, qr);
ans = max(ans, res);
if (x == 1) cout << ans << '\n';
res = ans;
}
char t;
const todo* funs[]{ add,update<min>,update<max>,get };
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> ht[i];
}
build(1, 1, n);
while (k--) {
cin >> t >> l >> r;
if (t != '4')cin >> h;
funs[t - '1'](1, 1, n, l, r, h);
}
}

参考

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇