CF1791F - Range Update Point Query

题目地址

题意：给你一个数组a，进行q次操作

有两种操作：

1:给出一个区间[l,r]，令该区间内所有数都变成他们自身每一位数字的和

2:给出x，输出a[x]的值

Solution

显然可以发现，当数字变为个位数的时候，之后的操作都不用进行了

用树状数组维护一个操作的次数的前缀和，这里用差分，对l进行+1的更新操作，对r+1进行-1的更新操作

最后直接对数字进行操作即可

 1 void update(int x,int a)
 2 {
 3     while(x<=n)
 4     {
 5         t[x]+=a;
 6         x+=lowbit(x);
 7     }
 8 }
 9 
10 int get_sum(int x)
11 {
12     int res=0;
13     while(x>=1)
14     {
15         res+=t[x];
16         x-=lowbit(x);
17     }
18     return res;
19 }
20 
21 
22 
23 void solve()
24 {
25     cin>>n>>q;
26     for(int i=1;i<=n;i++)
27     {
28         cin>>a[i];
29         t[i]=0;
30     }
31     while(q--)
32     {
33         int op;cin>>op;
34         if(op==2)
35         {
36             int x;cin>>x;
37             int cnt=get_sum(x);
38             cnt=min(3LL,cnt);
39             int ans=a[x];
40             while(cnt--)
41             {
42                 int res=0;
43                 while(ans>0)
44                 {
45                     res+=ans%10;
46                     ans/=10;
47                 }
48                 ans=res;
49             }
50             cout<<ans<<"\n";
51         }else
52         {
53             int l,r;cin>>l>>r;
54             update(l,1),update(r+1,-1);
55         }
56     }
57 }