[HNOI 2010] 면양 탄 비 (LCT / 블록)

제목.
묘사 하 다.
어느 날, Lostmonkey 는 엄 청 난 탄력 장 치 를 발 명 했 습 니 다. 그의 면양 친구 앞에서 자랑 하기 위해 그 는 어린 면양 을 초대 하여 함께 게임 을 했 습 니 다.게임 이 시작 되 자마자 Lostmonkey 는 바닥 에 직선 을 따라 n 개의 장 치 를 놓 았 습 니 다. 모든 장 치 는 초기 탄력 계수 ki 를 설정 하고 면양 이 i 번 째 장치 에 이 르 렀 을 때 뒤로 ki 걸음 을 쳐 서 i + ki 번 째 장치 에 이 르 렀 습 니 다. i + ki 번 째 장치 가 존재 하지 않 으 면 면양 이 날 아 갑 니 다.면양 은 i 번 째 장치 에서 시작 할 때 몇 번 맞 으 면 날 아 가 는 지 알 고 싶 어 한다.게임 을 더욱 재미있게 하기 위해 Lostmonkey 는 특정한 탄력 장치 의 탄력 계 수 를 수정 할 수 있 고 언제든지 탄력 계 수 는 정수 이다.
입력 형식
첫 번 째 줄 은 정수 n 을 포함 하고 바닥 에 n 개의 장치 가 있 음 을 나타 내 며 장치 의 번 호 는 0 에서 n - 1 까지 입 니 다.다음 줄 에는 n 개의 정수 가 있 고 n 개의 장치 의 초기 탄력 계수 이다.세 번 째 줄 에는 정수 m 가 있 습 니 다. 그 다음 에 m 줄 마다 적어도 두 개의 i, j 가 있 습 니 다. 만약 에 i = 1 이면 수출 은 j 에서 출발 하여 몇 번 튕 긴 후에 날 아 가 려 고 합 니 다. 만약 에 i = 2 면 하나의 정수 k 를 다시 입력 하여 제 j 의 탄력 장치 의 계수 가 k 로 수정 되 었 음 을 나타 냅 니 다.
출력 형식
모든 i = 1 의 경우 필요 한 걸음 수 를 출력 하여 한 줄 을 차지 해 야 합 니 다.
입력 샘플

4
1 2 1 1
3
1 1
2 1 1
1 1

출력 샘플

2
3

설명 하 다.
20% 의 데이터 n, m < = 10000, 100% 의 데이터 n < = 20000, m < = 100000
문제 풀이 의 사고 방향.
면양 이 노드 n + 1 n + 1 에 '날 아 간다' 는 뜻 을 설정 하면 쉽게 발견 할 수 있다. 만약 에 우리 가 점 하 나 를 그의 후계 와 연결 시 키 면 나무 (모든 노드 에 유일한 후계 가 있 고 나무 중의 모든 노드 에 유일한 아버지 노드 가 있 는 것 과 유사 하 다) 가 형성 되 고 조작 을 수정 하면 삭제 와 연결 이 된다.조회 작업 은 조회 두 점 사이 의 거리 가 되 었 다. 이것 이 바로 LCT 의 템 플 릿 문제 이다.복잡 도 O (MlogN) O (M l o g N)
하지만 이 문 제 는 나 눌 수 있어!원래 의 서열 을 n - − √ n 조각 으로 나 누고 각 조각 은 n - − √ n 이 며 각 노드 는 다음 블록 에 도달 할 수 있 는 어느 노드 를 몇 번 연주 해 야 하 는 지 기록 해 야 한다.수정 시 블록 내 수 정 된 노드 와 관련 된 모든 노드 정 보 를 폭력 적 으로 수정 하고 조회 할 때 블록 간 에 통계 하면 됩 니 다.복잡 도 O (MN − √) = O (4.48×107) O ( M N ) = O ( 4.48 × 10, 7) 넘 어 갈 수 있어!
Code#1 LCT

#include
#include

#define lson tr[id].son[0]
#define rson tr[id].son[1]

using namespace std;

const int N = 200005;
int n, a, b, c, m, k[N];

struct Splay{
    int son[2], fa, size;
    bool rev;
}tr[N];

struct OPT_LCT{
    int sta[N], top;
    inline void pushup(int id){
        tr[id].size = tr[lson].size + tr[rson].size + 1;
    }
    inline void pushdown(int id){
        if(tr[id].rev){
            if(lson){
                tr[lson].rev ^= 1;
                swap(tr[lson].son[0], tr[lson].son[1]);
            }
            if(rson){
                tr[rson].rev ^= 1;
                swap(tr[rson].son[0], tr[rson].son[1]);
            }
            tr[id].rev = 0;
        }
    }
    inline int which(int x){ return tr[tr[x].fa].son[1] == x; }
    inline int isRoot(int x){ return tr[tr[x].fa].son[0] != x && tr[tr[x].fa].son[1] != x; }
    inline void rotate(int x, int kind){
        int y = tr[x].fa, z = tr[y].fa, B = tr[x].son[kind];
        if(!isRoot(y))  tr[z].son[which(y)] = x;
        tr[x].son[kind] = y, tr[y].son[!kind] = B;
        tr[B].fa = y, tr[y].fa = x, tr[x].fa = z;
        pushup(y), pushup(x);
    }
    inline void splay(int x){
        sta[top = 1] = x;
        for(int i = x; !isRoot(i); i = tr[i].fa)    sta[++top] = tr[i].fa;
        while(top)  pushdown(sta[top--]);
        while(!isRoot(x)){
            int y = tr[x].fa, z = tr[y].fa;
            pushdown(z), pushdown(y), pushdown(x);
            int dir1 = !which(x), dir2 = !which(y);
            if(isRoot(y))   rotate(x, dir1);
            else{
                if(dir1 == dir2)    rotate(y, dir2);
                else    rotate(x, dir1);
                rotate(x, dir2);
            }
        }
    }
    inline void access(int x){
        int y = 0;
        while(x){
            splay(x);
            tr[x].son[1] = y;
            pushup(x);
            y = x, x = tr[x].fa;
        }
    }
    inline void makeRoot(int x){
        access(x), splay(x);
        tr[x].rev ^= 1;
        swap(tr[x].son[0], tr[x].son[1]);
        pushup(x);
    }
    inline void link(int x, int y){
        makeRoot(x), access(y), splay(y);
        tr[x].fa = y;
    }
    inline void cut(int x, int y){
        makeRoot(x), access(y), splay(y);
        tr[y].son[0] = tr[x].fa = 0;
        pushup(y);
    }
    inline int query(int x){
        makeRoot(n+1), access(x), splay(x);
        return tr[x].size - 1;
    }
}LCT;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n + 1; i++) tr[i].size = 1;
    for(int i = 1; i <= n; i++){
        scanf("%d", &k[i]);
        LCT.link(i, i+k[i] > n ? n+1 : i+k[i]);
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d%d", &a, &b);
        b++;
        if(a == 1)  printf("%d
", LCT.query(b));
        else if(a == 2){
            scanf("%d", &c);
            LCT.cut(b, b+k[b] > n ? n+1 : b+k[b]);
            LCT.link(b, b+c > n ? n+1 : b+c);
            k[b] = c;
        }
    }
    return 0;
}

코드 \ # 2 조각

#include
#include
#include
#include

using namespace std;

inline int read(){
    int x = 0;
    bool fl = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')   fl = 0;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return fl ? x : -x;
}

const int N = 200005;
int n, q, k[N], opt, a, b, block[N<<1], ans, l[N], r[N];
struct G{
    int cnt, to;
}g[N];

int main(){
    memset(l, 0x7f, sizeof l);
    memset(r, -1, sizeof r);
    n = read();
    for(int i = 1; i <= n; i++){
        k[i] = read();
        block[i] = (i-1) / sqrt(n) + 1;
        l[block[i]] = min(l[block[i]], i);
        r[block[i]] = max(r[block[i]], i);
    }
    for(int i = 1; i <= n; i++){
        int now = i;
        while(block[now] == block[i]){
            g[i].cnt++;
            now += k[now];
        }
        g[i].to = now;
    }
    q = read();
    while(q--){
        opt = read(), a = read(); a++;
        if(opt == 1){
            ans = 0;
            int now = a;
            while(now <= n){
                ans += g[now].cnt;
                now = g[now].to;
            }
            printf("%d
", ans);
        }
        else if(opt == 2){
            b = read();
            k[a] = b;
            for(int i = a; i >= l[block[a]]; i--){
                if(block[i] == block[i+k[i]]){
                    g[i].cnt = g[i+k[i]].cnt + 1;
                    g[i].to = g[i+k[i]].to;
                }
                else{
                    g[i].cnt = 1;
                    g[i].to = i + k[i];
                }
            }
        }
    }
    return 0;
}