In Problem E: lets save for each hole the answer , number of jumps after ball leaves this hole and the last hole for it. Then for each query we have answer in o(1) and for each update of strength we can look the hole which will be after this hole . ((new strength)+i) and rewrite its answer to this hole and increase the first answer (number of jumps ) by 1 and second answer (last hole) will be same. This is o(M) solution . Any mistake ?

Problem C :in which all elements are equal to some element from the initial sequence

Why? to get the min step , the final sequence 's every number is same to the initial sequence?? why is this optimal? Thanks.

kadar not able to visualize the solution can you please help me do that ?

Can someone please give me a good link for square root decomposition.

i found various links on google but don't know which one is good and contains all details on sqrt decomposition.

Problem E can also be solved using the Link-cut tree in .

Anyone noticed that Problem E also required the number of the last hole the ball visited?

So we'll have to jump to the block before we jump to the fictious hole and jump to the last hole before we jump to the fictious hole. So I had to add another while loop.

But it seems that the complexity is the same? Well, I'm just here to say that the type 1 query is not that easy(probably still easy for great coder,but not for this noob)

solve C

In problem E, but also the number of the first hole which belongs to other, do the number here refer to the smallest index of hole in which are residing in different segment and also could be hopped on through a series of jump ?

I did E using square root decomposition (Divided the array into blocks of size sqrt(n), then for each element stored only the last index within its block after which it jumps to an element in another block or out of the array).

My O(n * sqrt(n)) solution is getting TLE on testcase 16. Can anyone help? 285297411

I'm getting a Wrong Answer (WA) on test case 3 while using Square Root Decomposition. Can anyone help me figure out why? For the problem E **** //

include<bits/stdc++.h>

define ll long long

define endl "\n"

using namespace std;

vector<map<ll, pair<ll, ll>>> mp; ll flg[100005]; ll arr[100005]; ll n, k; vector<pair<ll,ll>>combi;

void findd() { ll l; cin >> l; ll val = 0; while (1) { ll com = flg[l]; val += mp[com][l].second; if (mp[com][l].first == l || com == 0) { cout << mp[com][l].first << " " << val << endl; break; } else l = mp[com][l].first; } }

void update(ll i) { ll e = combi[i].first; ll s = combi[i].second; map<ll, pair<ll, ll>> mm; for (ll j = e; j >= s; j--) { ll p = arr[j] + j; if (p > n) p = j; mm[j] = {p, 0}; if (flg[j] == flg[p]) { mm[j].second = mm[p].second + 1; mm[j].first = mm[p].first; } else mm[j].second = 1; } mp[i] = mm; }

void out() { ll i=0; for (auto v : mp) { cout<<"block "<<i<<endl;i++; for (auto p : v) { cout << p.first << " = " << p.second.first << " " << p.second.second << endl; } cout << endl; } }

int main () { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (ll i = 1; i <= n; i++) cin >> arr[i]; ll x = sqrt(n); mp.resize(x+2); ll cnt = 0; ll s = 0; pair<ll,ll>pp; for (ll i = n; i > 0; i--) { if(cnt==0)pp.first=i; cnt++; flg[i] = s; if (cnt == x || i==1) {pp.second=i;combi.push_back(pp); cnt = 0; s++; } }

// update all from end;
for(ll i=0;i<combi.size();i++)
update(i);


for (ll i = 0; i < k; i++) {
    ll t; cin >> t;
    if (t == 1) findd();
    else if (t == 0) {
        ll i; cin >> i >> arr[i];
        update(flg[i]);
        //out(); 
    }
}

} // ****