A. Longest k-Good Segment

题意：给定长度为 n 的数组 a 和整数 k，若连续子段中不同数字个数不超过 k 则称为 k‑good，输出任意一个最长的 k‑good 子段的左右端点（1‑based）。

数据范围：1≤k≤n≤5e5，0≤a_i≤1e6。

核心思路：双指针滑动窗口，维护窗口内不同元素个数，右指针扩展，左指针收缩直到满足条件，更新最优长度。复杂度 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXV=1000005;
int cnt[MAXV];
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n,k; cin>>n>>k;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=1,dist=0,best_len=0,best_l=1,best_r=1;
	for(int r=1;r<=n;r++){
		if(cnt[a[r]]==0) dist++;
		cnt[a[r]]++;
		while(dist>k){
			cnt[a[l]]--;
			if(cnt[a[l]]==0) dist--;
			l++;
		}
		int cur_len=r-l+1;
		if(cur_len>best_len){
			best_len=cur_len;
			best_l=l; best_r=r;
		}
	}
	cout<<best_l<<" "<<best_r<<"\n";
	return 0;
}

正确性：对每个右端点，左端点尽量右移得到最长合法区间，取全局最大。

注意：使用快速 I/O，cnt 数组大小覆盖值域，多解任意输出。

B. Range Update Point Query

题意：给定数组 a，两种操作：① 区间 [l,r] 内每个数变为其数位之和；② 单点查询 a[x]。输出所有查询结果。

数据范围：t≤1000，每组 n,q≤2e5，所有 n 和 q 总和≤2e5，a_i≤1e9。

核心思路：数位和操作会使数快速变小（≤9），之后不再变化。用 set 保存所有当前值 >9 的下标，区间更新时只遍历 set 中落在 [l,r] 的下标，更新后若变为一位数则从 set 删除。每个位置最多被更新 O(log 1e9) 次（实际≤3次），总复杂度 O((n+q) log n)。 代码：

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int f(int x){int s=0; while(x){s+=x%10; x/=10;} return s;}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin>>T;
	while(T--){
		int n,q; cin>>n>>q;
		set<int> st;
		for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]>=10) st.insert(i); }
		while(q--){
			int op; cin>>op;
			if(op==1){
				int l,r; cin>>l>>r;
				auto it=st.lower_bound(l);
				while(it!=st.end() && *it<=r){
					int p=*it;
					a[p]=f(a[p]);
					if(a[p]<10) st.erase(it++);
					else it++;
				}
			}else{
				int x; cin>>x;
				cout<<a[x]<<"\n";
			}
		}
	}
	return 0;
}

正确性：每个位置只有 >9 时才可能变化，且数位和严格减小，故每个位置最多被修改有限次，set 保证只处理有效位置。

注意：使用快速 I/O；每组数据清空 set 和数组（数组覆盖即可）；erase 时注意迭代器失效，使用 it++ 后擦除。