CFR 13 E. Holes ( 平方分割 )

Problem - E - Codeforces
第一次寫平方分割，不太習慣。這題的關鍵在於維護一些值，使得可以O( 1 ) 完成一個塊的查詢。操作也要逆著做回來( 由右到左 ) 才會正確。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;

int BS;

int n, m;
int eng[ MAXN ];

int nxt[ MAXN ];
int lst[ MAXN ];
int jmp[ MAXN ];

void update(int s, int t){
    if( t > n ){
        nxt[ s ] = -1;
        lst[ s ] = s;
        jmp[ s ] = 1;
    } else if( s / BS == t /BS ){
        nxt[ s ] = nxt[ t ];
        lst[ s ] = lst[ t ];
        jmp[ s ] = jmp[ t ] + 1;
    } else{
        nxt[ s ] = t;
        lst[ s ] = t;
        jmp[ s ] = 1;
    }
}

int main(){
    scanf("%d%d", &n, &m);
    BS = sqrt( n ) + 1;
    for(int i = 1; i <= n; ++i)
        scanf("%d", eng + i);
    for(int i = n; i >= 1; --i)
        update( i , i + eng[ i ] );
    for(int i = 0; i < m; ++i){
        int op, a, b; scanf("%d%d", &op, &a);
        if( op ){
            int u = a, ans = 0;
            while( true ){
                ans += jmp[ u ];
                if( nxt[ u ] == -1 ) break;
                u = nxt[ u ];
            }
            printf("%d %d\n", lst[ u ], ans);
        } else{
            scanf("%d", &b);
            eng[ a ] = b;
            int s = a / BS * BS;
            for(int i = a; i >= s; --i)
                update( i, i + eng[ i ] );
        }
    }
    return 0;
}