ABC285F字符串线段树二分查找简单动脑筋

题目的意思是，字符串S的一个子串X，是否是字符串S排序后字符串T的字串？
首先，符合要求，字符串X必须是不递减的，这样才可能跟不递减的S有重合部分。
其次，X中除了最大、最小的字符外，其他字符不能出现在两边，否则S排序后，这些字符就会插入到X中。
是否递增可以用线段树维护；保证单调性的前提下，字符数量可以用二分查找统计。

#include <bits/stdc++.h>
const int N=1<<18|9;
using namespace std;
int n, m, i, j, k, l, r, x, y, v, c[130];
char s[N], t[5], u[N];
void gai(int p, int l, int r, int x, int y){
    if(l == r) c[s[x]] -= m>0, s[x] = y, c[y]++;
    else{
        int m=l+r>>1, lc=p<<1, rc=lc|1;
        if(x <= m) gai(lc, l, m, x, y);
        else gai(rc, m+1, r, x, y);
        u[p] = u[lc] | u[rc] | (s[m]>s[m+1]);
    }//维护区间是否不递减、字母出现次数
}
void cha(int p, int l, int r, int x, int y){
    if(x<=l && r<=y) v |= u[p];
    else{
        int m=l+r>>1, lc=p<<1, rc=lc|1;
        if(x <= m) cha(lc, l, m, x, y);
        if(y > m) cha(rc, m+1, r, x, y);
        if(x<=m && y>m) v |= s[m] > s[m+1];
    }
}
int cnt(char c){
    l = lower_bound(s+x, s+y+1, c) - s;
    r = upper_bound(s+x, s+y+1, c) - s;
    return r - l;//统计[x, y]字符c数量 
}
int main(){
    scanf("%d%s", &n, s+1);
    for(i=1; i<=n; i++) gai(1, 1, n, i, s[i]);
    scanf("%d", &m);
    while(m--){
        scanf("%d%d%s", &k, &x, t);
        if(k == 1) gai(1, 1, n, x, t[0]);
        else{
            sscanf(t, "%d", &y);
            v = 0;
            cha(1, 1, n, x, y);
            if(v) printf("No\n");//出现递减 
            else{//两边不能出现中间字符
                for(i=s[x]+1; i<s[y]; i++){
                    if(cnt(i) < c[i]) break;
                }//中间字符数量要等于总数 
                if(i < s[y]) printf("No\n");
                else printf("Yes\n");
            }
        }
    }
    return 0;
}