AtCoder abc285 F
// compile: g++ -o data data.cpp -O3 -std=gnu++20 -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -ggdb3 -fmax-errors=2 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) {_variables(#x);_print(x);}
#define deb(x...) {_print(x);}
#else
#define debug(x...)
#define deb(x...)
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTINF (int)(9223372036854775807)
#define int long long
#define MAXN 200010

struct node {
    struct node *ch[2];
    struct node *p;
    int ind, letter, cnt[26];
    int lm, rm;
    bool ordered;
};
node *root = nullptr;
node datalist[MAXN];
int cnt = 0;
int n, q, total[26];

struct node *newnode(int ind, int letter) {
    node *x = datalist + ind;
    x->p = x->ch[0] = x->ch[1] = nullptr;
    x->ind = ind;
    memset(x->cnt, 0, sizeof(x->cnt));
    x->cnt[letter] = 1;
    x->ordered = 1;
    x->lm = x->rm = x->letter = letter;
    return x;
}

int get(struct node *x) {
    return (x->p->ch[1] == x);
}

void maintain(struct node *x) {
    if (!x) return;
    if (!x->ch[0] && !x->ch[1]) {
        x->ordered = 1;
        x->lm = x->rm = x->letter;
        memset(x->cnt, 0, sizeof(x->cnt));
        x->cnt[x->letter] = 1;
    }
    else if (!x->ch[0]) {
        x->ordered = x->ch[1]->ordered && (x->letter <= x->ch[1]->lm);
        x->lm = x->letter;
        x->rm = x->ch[1]->rm;
        for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[1]->cnt[i];
        ++x->cnt[x->letter];
    }
    else if (!x->ch[1]) {
        x->ordered = x->ch[0]->ordered && (x->letter >= x->ch[0]->rm);
        x->lm = x->ch[0]->lm;
        x->rm = x->letter;
        for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[0]->cnt[i];
        ++x->cnt[x->letter];
    }
    else {
        x->ordered = x->ch[0]->ordered && x->ch[1]->ordered && (x->letter >= x->ch[0]->rm) && (x->letter <= x->ch[1]->lm);
        x->lm = x->ch[0]->lm;
        x->rm = x->ch[1]->rm;
        for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[0]->cnt[i] + x->ch[1]->cnt[i];
        ++x->cnt[x->letter];
    }
}

void rotate(struct node *x) {
    node *y = x->p;
    node *z = y->p;
    int t = get(x);
    y->ch[t] = x->ch[t ^ 1];
    if (x->ch[t ^ 1]) x->ch[t ^ 1]->p = y;
    x->ch[t ^ 1] = y;
    y->p= x;
    if (z) z->ch[y == z->ch[1]] = x;
    x->p= z;
    maintain(y);
    maintain(x);
}

void splay(struct node *x, struct node *target) {
    for (struct node *f; f = x->p, f != target; rotate(x)) {
        if (f->p!= target) rotate((get(x) == get(f)) ? f : x);
    }
    if (target == NULL) root = x;
}

void insert(int ind, int letter) {
    if (!root) {
        root = newnode(ind, letter);
        return;
    }
    struct node *x = root;
    for (; ; x = x->ch[ind > x->ind]) {
        if (x->ind == ind) {
            maintain(x);
            maintain(x->p);
            splay(x, NULL);
            return;
        }
        if (!x->ch[ind > x->ind]) {
            x->ch[ind > x->ind] = newnode(ind, letter);
            x->ch[ind > x->ind]->p = x;
            maintain(x);
            splay(x->ch[ind > x->ind], nullptr);
            return;
        }
    }
}

void treavel(struct node *x) {
    if (x) {
        treavel(x->ch[0]);
        // deb(x->ind, x->letter, x->ordered, x->ch[0] ? x->ch[0]->ind : -1, x->ch[1] ? x->ch[1]->ind : -1);
        // deb(x->ind, x->cnt[0], x->cnt[1], x->cnt[2], x->cnt[3], x->cnt[4], x->cnt[5])
        treavel(x->ch[1]);
    }
}

string check(node *x) {
    if (!x->ordered) return "No";
    int s = 0, t = 25;
    while (!x->cnt[s]) ++s;
    while (!x->cnt[t]) --t;
    ++s, --t;
    for (int i = s; i <= t; ++i) if (x->cnt[i] != total[i]) return "No";
    return "Yes";
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; string s; cin >> s;
    insert(0, 0); insert(n + 1, 0);
    for (int i = 0; i < (int)s.length(); ++i) {
        insert(i + 1, s[i] - 'a');
        ++total[s[i] - 'a'];
    }
    cin >> q;
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int x; char ch; cin >> x >> ch;
            --total[(datalist + x)->letter];
            ++total[ch - 'a'];
            splay(datalist + x, nullptr);
            root->letter = ch - 'a';
            maintain(root);
        }
        else {
            int l, r; cin >> l >> r;
            splay(datalist + l - 1, nullptr);
            splay(datalist + r + 1, root);
            cout << check(root->ch[1]->ch[0]) << endl;
        }
    }

    return 0;
}
No Comments

Send Comment Edit Comment


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