超级线段树
//P2824

#include<iostream>
using namespace std;

namespace SegmentTree {
    static unsigned lim;
    static unsigned* a;
    using cints = const unsigned&;
    constexpr unsigned maxn = 1e5;
    enum class ArrayState {
        UnSet, AllZero, AllOne
    };
    struct node {
        struct son {
            static inline unsigned lft(cints root) { return root << 1; }
            static inline unsigned rit(cints root) { return root << 1 | 1; }
        };
        struct tags {
            template<node* seg>
            static inline void pushdown(cints root, cints l, cints r) {
                if (seg[root].tag.state == ArrayState::UnSet) return;
                const auto lc = son::lft(root), rc = son::rit(root), mid = midof(l,r);
                seg[lc].tag.state = seg[rc].tag.state = seg[root].tag.state;
                if (seg[root].tag.state == ArrayState::AllOne) {
                    seg[lc].val.cnt = mid - l + 1; seg[rc].val.cnt = r - mid;
                }
                else seg[lc].val.cnt = seg[rc].val.cnt = 0;
                seg[root].tag.state = ArrayState::UnSet;
            }
            ArrayState state;
        }tag;
        struct vals {
            unsigned cnt;
            template<node* seg>
            static inline void update(cints root) { seg[root].val.cnt = seg[son::lft(root)].val.cnt + seg[son::rit(root)].val.cnt; }
        }val;
        static inline void tie(unsigned* Arr) { a = Arr; }
        static inline const unsigned midof(cints l, cints r) { return ((r - l) >> 1) + l; }
        template<node* seg>
        static void build(cints root, cints l, cints r) {
            if (l == r) return void(seg[root].val.cnt = (a[l] >= lim));
            node::build<seg>(son::lft(root), l, midof(l, r)), node::build<seg>(son::rit(root), midof(l, r) + 1, r);
            vals::update<seg>(root); seg[root].tag.state = ArrayState::UnSet;
        }
        struct gets {
            template<node* seg>
            static unsigned cntof(cints root, cints ml, cints mr, cints ql, cints qr) {
                if (ql <= ml && mr <= qr) return seg[root].val.cnt;
                if (ql > mr || qr < ml) return 0;
                tags::pushdown<seg>(root, ml, mr);
                return
                    gets::cntof<seg>(son::lft(root), ml, midof(ml, mr), ql, qr) +
                    gets::cntof<seg>(son::rit(root), midof(ml, mr) + 1, mr, ql, qr);
            }
            template<node* seg>
            static const vals pointof(cints root, cints l, cints r, cints on){
                if (l == on && r == on) return seg[root].val;
                tags::pushdown<seg>(root, l, r);
                if (auto mid = midof(l, r); on <= mid) return gets::pointof<seg>(son::lft(root), l, mid, on);
                else return gets::pointof<seg>(son::rit(root), mid + 1, r, on);
            }
        };
        struct update {
            template<node* seg>
            static inline void sets(cints root, cints ml, cints mr, cints ql, cints qr, cints val){
                if (ql <= ml && qr >= mr)
                    return 
                    void(seg[root].val.cnt = val * (mr - ml + 1)),
                    void(seg[root].tag.state = (val ? ArrayState::AllOne : ArrayState::AllZero));
                if (ql > mr || qr < ml) return;
                tags::pushdown<seg>(root, ml, mr);
                update::sets<seg>(son::lft(root), ml, midof(ml,mr), ql, qr, val);
                update::sets<seg>(son::rit(root), midof(ml, mr) + 1, mr, ql, qr, val);
                vals::update<seg>(root);
            }
        };
    } nnd[maxn];
}
unsigned a[SegmentTree::maxn],L[SegmentTree::maxn],R[SegmentTree::maxn],p,n,m;
char opt[SegmentTree::maxn];
template<SegmentTree::node* seg>
inline const bool check(const unsigned int& x){
    SegmentTree::lim = x;
    SegmentTree::node::build<seg>(1, 1, n);
    for (unsigned i = 1; i <= m; ++i)
        if (unsigned cnt1 = SegmentTree::node::gets::cntof<seg>(1, 1, n, L[i], R[i]);opt[i] == '0')
            SegmentTree::node::update::sets<seg>(1, 1, n, R[i] - cnt1 + 1, R[i], 1),
                SegmentTree::node::update::sets<seg>(1, 1, n, L[i], R[i] - cnt1, 0);
        else
            SegmentTree::node::update::sets<seg>(1, 1, n, L[i], L[i] + cnt1 - 1, 1),
                SegmentTree::node::update::sets<seg>(1, 1, n, L[i] + cnt1, R[i], 0);
    return SegmentTree::node::gets::pointof<seg>(1, 1, n, p).cnt;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), std::cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin>>a[i];
    SegmentTree::node::tie(a);
    for (int i = 1; i <= m; i++) {
        cin>>opt[i]>>L[i]>>R[i];
    }
    cin>>p;
    int ll = 1, rr = n, midd, ans=0;
    while (ll <= rr)
        if(midd = (ll + rr) >> 1;check<SegmentTree::nnd>(midd)) ans = midd, ll = midd + 1; 
        else rr = midd - 1;
    std::cout << ans;
    return 0;
}
暂无评论

发送评论 编辑评论


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