Codeforces Round #849 (Div. 4)-F. Range Update Point Query-STL的应用（bushi）

题目：https://codeforces.com/problemset/problem/1791/F

看完差点想写线段树了（bushi）
但其实用set维护一下位置就行
注：lower_bound(x)找的是第一个大于等于x的元素（的地址），以及set里可以用prev和next访问前后的迭代器耶

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int N=2e5+5;
int n,q,a[N];
set<int> S;
void upd(int &x){
	int s;
	for(s=0;x;x/=10)s+=x%10;
	x=s;
}
void modify(int l,int r){
	auto pos=S.lower_bound(l);
	set<int> tmp;
	while(pos!=S.end()&&*pos<=r){
		upd(a[*pos]);
		if(a[*pos]<10)tmp.insert(*pos);
		pos=next(pos);
	}
	for(auto x:tmp)S.erase(x);
}
void solve(){
	cin>>n>>q;
	rep(i,1,n)cin>>a[i];
	rep(i,1,n)if(a[i]>=10)S.insert(i);
	while(q--){
		int op,l,r,x;
		cin>>op;
		if(op==1){
			cin>>l>>r;
			modify(l,r);
		}else{
			cin>>x;
			cout<<a[x]<<endl;
		}
	}
}
int main(){
	fastio;
	int T;cin>>T;
	while(T--)solve();
	return 0;
}