The solution is a dynamic tree, which is too difficult, so we have to deal with water in chunks. Looking at status, it’s about twice as slow.

The block algorithm is basically looking for a compromise point, so that the time complexity of query and modification is not too high, both o(SQRT (n)), so the total time complexity is O (m* SQRT (n)).

The general idea of chunking is to divide the whole interval into SQRT (n), each change affecting SQRT (n) points in the segment, each query traversing the SQRT (n) segment, and then doing something.

For this problem, first explain the meaning of several arrays:

  • The meaning of CNT [I] is the number of steps required to jump out of its segment from point I.
  • Goal [I] means the last point experienced from point I.
  • JMP [I] means the first point to be reached after jumping out of the segment from point I.

After understanding these several meanings, it is good to look at the code, the text is too weak.

    

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 using namespace std; const int MAXN = 100010,BLOCK = sqrt(100010); int jmp[MAXN],cnt[MAXN],goal[MAXN],val[MAXN]; void Updata(int x,int y,int n) { if(y > n) { jmp[x] = MAXN; cnt[x] = 1; goal[x] = x; } else if(x/BLOCK*BLOCK == y/BLOCK*BLOCK) { jmp[x] = jmp[y]; cnt[x] = cnt[y]+1; goal[x] = goal[y]; } else { jmp[x] = y; cnt[x] = 1; goal[x] = y; } } void Cal(int x) { int ans = 0,f; while(x ! = MAXN) { f = goal[x]; ans += cnt[x]; x = jmp[x]; } printf("%d %d\n",f,ans); } int main() { int i,j,u,v,n,m,ord,L; scanf("%d %d",&n,&m); for(i = 1; i <= n; ++i) scanf("%d",&val[i]); for(i = n; i >= 1; --i) Updata(i,i+val[i],n); while(m--) { scanf("%d",&ord); if(ord) { scanf("%d",&u); Cal(u); } else { scanf("%d %d",&u,&v); val[u] = v; L = u/BLOCK*BLOCK; for(i = u; i >= L; --i) Updata(i,i+val[i],n); } } return 0; }Copy the code

\

​