Submission #38076430

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double PI = acos(-1);



int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    fenwick_tree<int> fs(n+1);
    vector<fenwick_tree<int>> fenal(26, fenwick_tree<int>(n+1)); 
    vector<int> al(26);
    rep(i,n) {
        int cint = s[i]-'a';
        al[cint]++;
        fenal[cint].add(i, 1);
        if (i) {
            if (!(s[i-1] <= s[i])) fs.add(i,-1);
        }
        if (i != n-1) {
            if (!(s[i] <= s[i+1])) fs.add(i,-1);
        }
    }
    int q;
    cin >> q;
    rep(qi,q) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            x--; 
            char c;
            cin >> c;

            al[s[x]-'a']--;
            fenal[s[x]-'a'].add(x, -1);
            al[c-'a']--;
            fenal[c-'a'].add(x, 1);

            fs.add(x, -fs.sum(x,x+1));
            s[x] = c;
            if (x) {
                if (!(s[x-1] <= s[x])) fs.add(x,-1);
            }
            if (x != n-1) {
                if (!(s[x] <= s[x+1])) fs.add(x,-1);
            }
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            if (fs.sum(l, r+1) < 0) {
                cout << "No" << endl;
                continue;
            }

            vector<int> al2(26);
            rep(i,26) {
                al2[i] = fenal[i].sum(l, r+1);
            }

            int first = s[l]-'a';
            int last = s[r]-'a';
            bool ok = true;
            rep(i,26) {
                if (i == first || i == last) continue;
                if (al2[i]) {
                    if (al2[i] != al[i]) ok = false;
                }
            }
            if (ok == true) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

Submission Info

Judge Result