HackerEarth Retrieve passwords problem solution

In this HackerEarth Retrieve passwords problem solution A password is a number that is exactly divisible by 9. It is the largest number that can be formed by rearranging all the available digits in a provided range (L, R) inclusive and adding another number of your own choice to this sequence at any position. The password is missing a digit that must be added. You are also given an encrypted number. You are also provided q queries. The queries could be of two types.

Update a digit at a position.

Determine the largest number that is divisible by 9 in the provided range with the mentioned conditions. In the provided mentioned number, print its xth digit.

You must retrieve the password.

#include <bits/stdc++.h>
#//include <ext/pb_ds/assoc_container.hpp>
#//include <ext/pb_ds/tree_policy.hpp>
#//include <ext/pb_ds/detail/standard_policies.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//insert(), find_by_order(), order_of_key()
typedef long long int ll;
typedef unsigned long long int llu;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define ref(i, n) for (int i = 0; i < n; ++i)
#define rer(i, n) for (int i = n; i >= 0; --i)
#define refv(i, n, k) for (int i = k; i <= n; ++i)
#define rerv(i, n, k) for (int i = k; i >= n; --i)
#define fi first
#define pii pair<int, int>
#define piii pair<pii, int>
#define priority_queue_2 priority_queue<int, vector<int>, greater<int>>
#define se second
#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
inline void pin(int n)
{
    printf("%dn", n);
}
#define onec(x) __builtin_popcount(x);
#define all(x) x.begin(), x.end()
double PI = acos(-1);
const int inf = 0x3f3f3f3f;
#define sv()         
    int t;           
    scanf("%d", &t); 
    while (t--)
#define MOD 1000000007
#define TRACE
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif

struct node
{
    vector<int> p;
    node()
    {
        p.resize(10, 0);
    }
};

string s;
int n;
vector<node> v(1000005);

void update(int pos, int val, int no)
{
    while (pos <= n)
    {
        v[pos].p[no] += val;
        pos += pos & (-pos);
    }
}

int sum(int pos, int no)
{
    int s = 0;
    while (pos > 0)
    {
        s += v[pos].p[no];
        pos -= pos & (-pos);
    }
    return s;
}

int main()
{
    bool ti= false;
    fast1;
    fast2;
    cin >> s;
    n = s.size();
    clock_t start, end;
    start = clock();
    assert(n <= 1000000);
    for (int i = 0; i < n; i++)
        update(i + 1, 1, s[i] - '0');
    int q;
    cin >> q;
    assert(q <= 500000);
    vector<int> m(10, 0);
    while (q--)
    {
        int t;
        cin >> t;
        assert(t == 2 || t == 1);
        if (t == 1)
        {
            int x, y;
            cin >> x >> y;
            assert(x>0 && x <= n);
            assert(y >= 0 && y < 10);
            int old = s[x-1] - '0';
            if(old==y) 
                continue;
            s[x-1] = (char)(y + '0');
            update(x , -1, old);
            update(x , 1, y);
            //cout<< s << endl;
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x;
            assert(l <= n && r >= l && r <= n && l>0);
            assert(x>0 && x <= (r - l + 2));
            for (int i = 0; i < 10; i++)
            {
                m[i] = sum(r, i);
                m[i] -= sum(l-1, i);
                //trace2(i,m[i]);
            }
            int ss = 0;
            for (int i = 1; i < 10; i++)
            {
                ss += ((i % 9) * (m[i] % 9)) % 9;
                ss %= 9;
            }
            m[9 - ss]++;
            for (int i = 9; i >= 0; i--)
            {
                if (m[i] >= x)
                {
                    cout << i << endl;
                    break;
                }
                x -= m[i];
            }
        }
    }
    end = clock();
    if(ti){
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
    cout << "Time taken by program is : " << fixed
         << time_taken << setprecision(5);
    cout << " sec " << endl;}
    return 0;
}