Sort Left and Right

题目传送门

Sort Left and Right

题目大意

给定关于 \(N\) 的排列 \(P\)，定义一个操作为选择一个 \(k(1\le k\le N)\)，然后把 \([1,k-1]\) 和 \([k+1,N]\) 都按升序排序。求讲 \(P\) 变成一个从 \(1\) 到 \(N\) 的序列的最小操作次数。带多测。

\(\sum N\le 2\times10^5\)

思路

其实是一个小结论题，赛时智障写了 30min。

首先发现，如果 \(P\) 本身就是排好序的，那么输出 \(0\) 即可。

然后可以考虑遍历一下 \(P\)，选取 \(k\)，判断是否可以在 \(1\) 次操作内完成。如果可以的话就输出 \(1\)。

如果 \(1\) 次操作不行的话，那么考虑存在一种排列 \(\{a,b,\cdots,1\}\)，显然我们可以先选取 \(k=1\)，把 \([2,N]\) 排好序，然后在选取一个 \(k\) 满足 \(3\le k\le N\) 就可以在两步之内完成。由这个排列可以推广到几乎所有情况，那么最优解就是 \(2\)。

值得一提的是，当排列为 \(\{N,a,b,\cdots,1\}\) 时，最优解只能是 \(3\)。

时间复杂度 \(O(\sum N)\)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,a[200001];
bool v[200001]={0};
int pos;

void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];

	pos=0;
	for(int i=1;i<=n;i++)
		v[i]=0;

	bool f=1;
	for(int i=1;i<=n;i++){
		if(a[i]!=i){
			f=0;
			break;
		}
	}

	if(f){
		cout<<0<<endl;
		return;
	}
	
	if(a[1]==n&&a[n]==1){
		cout<<3<<endl;
		return;
	}

	for(int i=1;i<=n;i++){
		while(v[pos+1]&&pos<n)
			pos++;

		if(a[i]==i){
			if(pos>=i-1){
				cout<<1<<endl;
				return;
			}
		}

		v[a[i]]=1;
	}

	cout<<2<<endl;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int t; cin>>t;
	while(t--) solve();

	return 0;
}

Distinct Characters Queries

题目传送门

Distinct Characters Queries

题目大意

给定一个字符串 \(s\)，有两种操作。

• 给出 \(i,c\)，将 \(s_i\) 改成 \(c\)。

• 给出 \(l,r\)，求 \([l,r]\) 中不同字符的种类个数。

思路

其实挺水的，但是考场上不一定会写这种做法。

给出一个数组 \(cnt_{i,j}\) 满足 \(1\le i\le|s|,1\le j\le 26\) 表示前 \(i\) 位中拥有字符 \(j\) 的个数，可以 \(O(|s|)\) 预处理。

对于每一次更改，就是把 \(cnt_{i\text{~}|s|,s_i}\) 都减 \(1\)，同样地，把 \(cnt_{i\text{~}|s|,c}\) 都加 \(1\)。

显然地，区间加单点查，线段树和树状数组都可以做。

这时肯定很多人就想这道题用数据结构肯定不是正解！一定有更优秀的解法。

其实不是的，这道题的正解就是数据结构。

代码

代码没写咕咕咕。