首页 > 代码库 > 分块 (貌似能用LCT做,反正我现在还不会) BZOJ 2002

分块 (貌似能用LCT做,反正我现在还不会) BZOJ 2002

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 9844  Solved: 5070
[Submit][Status][Discuss]

Description

某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。

Sample Input

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

Sample Output

2
3

HINT

 

Source

 

 

思路:感觉这个如果说用分块的话感觉是基础题?

总体思路就是分成sqrt(n)块,然后每次都对这个块内进行更新, need表示每次走的步数,我们就只要for(j = r[i]; j >= l[i]; j--) 来逆序迭代更新就好了。

技术分享
//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 200000 * 2;
int n, m;
int step[maxn];
int l[maxn], r[maxn], belong[maxn], block, num;
int to[maxn], need[maxn];

void build(){
    block = sqrt(n); num = n / block;
    if (n % block) num++;
    for (int i = 1; i <= num; i++){
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    }
    for (int i = 1; i <= n; i++)
        belong[i] = (i - 1) / block + 1;
}


void update(int be){
    for (int i = l[be]; i <= r[be]; i++)
        to[i] = -1, need[i] = 0;
    for (int i = r[be]; i >= l[be]; i--){
        int nxtpos = i + step[i];
        if (nxtpos > n) nxtpos = n + 1;
        if (belong[nxtpos] != be){//如果只走一步,且两个不是同一个块
            to[i] = nxtpos; need[i] = 1;
        }
        else {//同一个块
            need[i] = 1;
            need[i] += need[nxtpos];
            to[i] = to[nxtpos];
        }
    }
}

void query(int pos){
    int cnt = 0;
    while (pos <= n){
        cnt += need[pos];
        pos = to[pos];
    }
    printf("%d\n", cnt);
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        scanf("%d", step + i);
    }
    build();
    memset(to, -1, sizeof(to));
    for (int i = 1; i <= num; i++){
        update(i);
    }
/*
    for (int i = 1; i <= n; i++){
        printf("to[%d] = %d need[%d] = %d\n", i, to[i], i, need[i]);
    }
*/
    cin >> m;
    for (int i = 1; i <= m; i++){
        int a, b, c;
        scanf("%d%d", &a, &b); b++;
        if (a == 2){
            scanf("%d", &c);
            step[b] = c;
            update(belong[b]);
        }
        else {
            query(b);
        }
    }
    return 0;
}
View Code

 

关键:分块的魅力在于每次不需要将序列全部更新,而是只需要更新其中的片段

 

分块 (貌似能用LCT做,反正我现在还不会) BZOJ 2002