树状数组

思维+树状数组

题目链接：https://codeforces.com/contest/1791/problem/F

题意

操作 1 l r：区间[l,r]中每个数修改为数位和
操作 2 x：查询当前a[x]的值

数据范围

题解

    因为一个数通过若干次操作1的数位和是固定不变的，直到变为个位数后就不会发生变化，所以对于下标i只需要记录a[i]随操作次数的变化值（可以用二维vector保存），这题就将转化为了操作次数.     操作1就是对区间[l,r]执行操作数加一，区间二则是查询下标i的操作次数，经典的“区间修改+单点查询”问题，使用树状数组进行维护.     另外，完全不需要担心数位和与操作次数的范围，因为数值是非常小的，如

Code:

#include < bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
vector< int> v[200010];
int diff[200010]; // 操作次数
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int T;cin >> T;
    while (T--){
        int n, q;cin >> n >> q;
        for (int i = 1; i <= n; i++){
            int x;
            cin >> x;
            v[i].clear();
            diff[i] = 0;
            v[i].push_back(x);
            if(x< 10)v[i].push_back(x);
            while (x >= 10)
            {
                int sum = 0, y = x;
                while (y)sum += y % 10, y /= 10;
                v[i].push_back(sum), x = sum;
            }
        }
        auto lowbit = [&](int x) -> int{
            return x & (-x);
        };
        auto add1 = [&](int x, int k) -> void{
            for (int i = x; i <= n; i += lowbit(i))
                diff[i] += k;
        };
        auto add2 = [&](int l, int r, int x) -> void{
            add1(l, x), add1(r + 1, -x);
        };
        auto query = [&](int x) -> int{
            int res = 0;
            for (int i = x; i; i -= lowbit(i))
                res += diff[i];
            return res;
        };
        while (q--){
            int opt;
            cin >> opt;
            if (opt == 1){
                int l, r;cin >> l >> r;
                add2(l, r, 1);
            }
            else{
                int x;cin >> x;
                int maxn = v[x].size() - 1;
                if (query(x) <= maxn)
                    cout << v[x][query(x)] << endl;
                else
                    cout << v[x][maxn] << endl;
            }
        }   
    }
    return 0;
}