F. Range Update Point Query 传送门
法一：树状数组
利用差分树状数组来维护所有的\(a_i\)需要维护的次数，前缀和即为需要修改的次数
//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long
// typedef std::pair<int,int> pii;
// typedef std::pair<ll,ll> pll;
// typedef std::pair<ull,ull> pull;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}
using namespace std;
const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,q,a[maxm],qz[maxm];
int lowbit(int x){//经典lowbit
return x&(-x);
}
void update(int x,int v){//单点修改
while(x<=n){
qz[x]+=v;
x=x+lowbit(x);
}
return ;
}
int getsum(int x){//求和
int ans=0;
while(x>0){
ans+=qz[x];
x-=lowbit(x);
}
return ans;
}
int calc(int x){//题目要求的数字update操作
int ans=0;
while(x){
ans+=x%10;
x/=10;
}
return ans;
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>a[i];
qz[i]=0;
}
int c,x,y;
while(q--){
cin>>c;
if(c==1){
cin>>x>>y;
update(x,1);
update(y+1,-1);
}else{
cin>>x;
int ans=a[x],t;
if(ans>9){
t=getsum(x);
while(t--){
ans=calc(ans);
if(ans<10) break;
}
}
cout<<ans<<'\n';
}
}
return ;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--){
solve();
}
return 0;
}
/*
wa原因：在利用树状数组维护差分和之后，在每次查询完之后
因为自己没有将差分数组清零
所以在下次update时，就会出现update多几次的情况出现
或者说，都用了树状数组了，就不需要清零了，因为前缀和就是update的次数
*/