ABC 285 F – Substring of Sorted String

好久都没写线段树的题解了……水一发

题意：

给定一个字符串，满足两种操作。第一种为修改串上某个地方的字母，第二种为查询一个区间，并判断当整个字符串按照升序排序后这一段区间是不是仍能保持连续。

给个结论，在第二种操作中，如果仍能保持连续，必须满足以下条件：

• 区间内字母本身按照升序排列。
• 设该区间开头的字母为 \(a\)，结尾的字母为 \(b\)，要求 \(a + 1\) 到 \(b - 1\) 这个区间内所有字母出现的次数必须等于这些字母在整个串里出现的次数。否则的话排序后就会有其他字符插入其中，该区间就不能连续了。

因此，我们就要维护区间内每种字母出现的个数。一种方法是开 \(26\) 个树状数组，维护每一种字母的区间出现次数，并用一个线段树维护某个区间是否有序，主要的缺点是树状数组会给复杂度多套上个 \(log\)，加上常数。另一种是给线段树上每个节点开一个大小为 \(26\) 的数组，直接在这里面维护字母的区间出现次数。

两种代码：

#include<bits/stdc++.h>
#define mid (tl + tr >> 1)
#define ll tree[i].ls
#define rr tree[i].rs
using namespace std;
const int MAXN = 1e6;
int n,tot,m;
string s;
int lowbit(int i){
	return i & (-i);
}
struct Tree{
	int a[MAXN + 5];
	void change(int pos,int num){
		for(int i = pos; i <= n; i += lowbit(i)){
			a[i] += num;
		}
	}
	int query(int pos){
		int sum = 0;
		for(int i = pos; i > 0; i -= lowbit(i))sum += a[i];
		return sum;
	}
	int get(int l,int r){
		int ans = 0;
		ans = query(r) - query(l - 1);
		return ans;
	}
}t[30];
struct node{
	int ls,rs;
	int cr,cl;
	bool ord;
}tree[MAXN + 5];
void push_up(int i){
	tree[i].cl = tree[ll].cl,tree[i].cr = tree[rr].cr;
	tree[i].ord = tree[ll].ord & tree[rr].ord & (tree[ll].cr <= tree[rr].cl);
}
void build(int i,int tl,int tr){
	if(tl == tr){
		tree[i].ord = 1;
		tree[i].cr = tree[i].cl = s[tl] - 'a' + 1;
		return;
	}
	tree[i].ls = ++tot;
	tree[i].rs = ++tot;
	build(ll,tl,mid);
	build(rr,mid + 1,tr);
	push_up(i);
}
void change(int i,int tl,int tr,int pos,char to){
	if(tl == tr){  
		int k = s[pos] - 'a' + 1;
		t[k].change(pos,-1);
		s[pos] = to;
		k = s[pos] - 'a' + 1;
		t[k].change(pos,1);
		tree[i].cl = tree[i].cr = to - 'a' + 1;
		return;
	}
	if(pos <= mid)change(ll,tl,mid,pos,to);
	else change(rr,mid + 1,tr,pos,to);
	push_up(i);
}
bool query(int i,int tl,int tr,int l,int r){
	if(tl >= l && tr <= r)return tree[i].ord;
	int flag = 1;
//	if(l <= mid && r > mid){
//		flag = flag & query(rr,mid + 1,tr,l,r);
//		flag = flag & query(ll,tl,mid,l,r);
//		if(s[mid] > s[mid + 1])flag = 0;
//		return flag;
//	}
//	if(r <= mid)return query(ll,tl,mid,l,r);
//	if(l > mid)return query(rr,mid + 1,tr,l,r);
	int last = 1;
	if(l <= mid){
		flag = flag & query(ll,tl,mid,l,r);
		last = tree[ll].cr;
	}
	if(r > mid){
		flag = flag & query(rr,mid + 1,tr,l,r) & (tree[rr].cl >= last);
	}
	return flag;
}
bool check(int l,int r){
	if(!query(1,1,n,l,r))return 0;
	int L = s[l] - 'a' + 1,R = s[r] - 'a' + 1;
	for(int i = L; i <= R; i++){
		if(i == s[l] - 'a' + 1 || i == s[r] - 'a' + 1)continue;
		int cnt = t[i].get(l + 1,r - 1);
	//	if(cnt == 0)continue;
		if(cnt != t[i].get(1,n))return 0;
		
	}
	return 1;
}
int main(){
	//freopen("data","r",stdin);
	//freopen("ans1","w",stdout);
	++tot;
	scanf("%d",&n);
	cin >> s;
	s = " " + s;
	build(1,1,n);
	for(int i = 1; i < s.size(); i++)t[s[i] - 'a' + 1].change(i,1);
	int k,l,r;
	char c;
	scanf("%d",&m);
	for(int i = 1; i <= m; i++){
		//cout << query(1,1,n,2,2) << "\n";
		scanf("%d",&k);
		if(k == 1){
			scanf("%d",&l);
			cin >> c;
			change(1,1,n,l,c);
		}
		else{
			scanf("%d%d",&l,&r);
			bool ans = check(l,r);
			if(ans)printf("Yes\n");
			else printf("No\n");
		}
		
	}
}

#include<bits/stdc++.h>
#define mid (tl + tr >> 1)
using namespace std;
const int MAXN = 1e6;
int n,m, sum[30], tot[30];
string s;
struct node{
	int ls,rs, dat[30];
	bool ord;
}tree[MAXN << 2];
void push_up(int p){
	for (int i = 1; i <= 26; i++) tree[p].dat[i] = tree[p << 1].dat[i] + tree[p << 1 | 1].dat[i];
	tree[p].ord = (tree[p << 1].ord & tree[p << 1 | 1].ord) & (tree[p << 1].rs <= tree[p << 1 | 1].ls);
	tree[p].rs = tree[p << 1 | 1].rs, tree[p].ls = tree[p << 1].ls;
}
void build(int i,int tl,int tr){
	if(tl == tr){
		tree[i].ord = 1;
		tree[i].dat[s[tl] - 'a' + 1]++;
		tree[i].ls = tree[i].rs = s[tl] - 'a' + 1;
		return;
	}
	build(i << 1,tl,mid);
	build(i << 1 | 1,mid + 1,tr);
	push_up(i);
}
void change(int i,int tl,int tr,int pos,char to){
	if(tl == tr){  
		int k = s[pos] - 'a' + 1;
		tree[i].dat[k]--;
		tot[k]--;
		s[pos] = to;
		k = s[pos] - 'a' + 1;
		tot[k]++;
		tree[i].dat[k]++;
		tree[i].ls = tree[i].rs = k;
		return;
	}
	if(pos <= mid)change(i << 1,tl,mid,pos,to);
	else change(i << 1 | 1,mid + 1,tr,pos,to);
	push_up(i);
}
bool query(int i,int tl,int tr,int l,int r){
	if (tl >= l && tr <= r) {
		for (int j = 1; j <= 26; j++) sum[j] += tree[i].dat[j];
		return tree[i].ord;
	}
	int last = 1; bool flag = true;
	if (l <= mid) {
		flag &= query(i << 1, tl, mid, l, r), last = tree[i << 1].rs;
//		printf("%d %d %d\n", tl, mid, last);
	}
	if (r > mid) {
		flag &= query(i << 1 | 1, mid + 1, tr, l, r) && (last <= tree[i << 1 | 1].ls);
//		printf("%d %d %d %d\n", mid + 1, tr, tree[i << 1 | 1].ls, last);	
	}
	return flag;
}
bool check(int l,int r){
	memset(sum, 0, sizeof(sum));
	if(!query(1,1,n,l,r))return 0;
	int minl = 27, maxl = 0;
	for (int i = 1; i <= 26; i++) if (sum[i]) minl = min(minl, i), maxl = max(maxl, i);
	for (int i = minl + 1; i < maxl; i++) if (sum[i] < tot[i]) return false;
	return true;
}
int main(){
	freopen("data","r",stdin);
	freopen("ans2","w",stdout);
	scanf("%d",&n);
	cin >> s;
	s = ' ' + s;
	for (int i = 1; i < s.length(); i++) tot[s[i] - 'a' + 1]++;
	build(1,1,n);
	int k,l,r;
	char c;
	scanf("%d",&m);
	for(int i = 1; i <= m; i++){
		//cout << query(1,1,n,2,2) << "\n";
		scanf("%d",&k);
		if(k == 1){
			scanf("%d",&l);
			cin >> c;
			change(1,1,n,l,c);
		}
		else{
			scanf("%d%d",&l,&r);
			bool ans = check(l,r);
			if(ans)printf("Yes\n");
			else printf("No\n");
		}
		
	}
}
/*
6
abcdcf
4
1 5 e
2 2 6
*/