14131: 【原4131】Welcome to the Aperture Science

题目描述

author: 黄俊翔原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4131 ## Description

今天也是和平的一天，雪儿依旧被困在光圈科技实验室中，用她手中的传送门枪和GLaDOS一起做着无尽的实验。雪儿刚刚又进入了一个新的实验房间。她的右手边是一个重量同伴方块生成器，刚开始的时候天花板上的生成器会向下弹出一个同伴方块。而雪儿的前方是一个无法进入的长条形实验房间，地上放着排成一排的n个向右弹射的弹簧板，最右边是一个焚化炉。每个弹簧板后面还贴心的标记了该弹簧板的向右弹射距离（弹射距离的单位长度为弹簧板的宽度，必然是一个正整数。此外，众所周知的，光圈科技的弹簧板弹射的距离，与物体的重量、入射角度与速度都是无关的）。而其中某几个弹簧板上方对应的天花板上，涂了可以放置空间传送门的白色凝胶，雪儿手中的传送门枪可以选择击中其中的一个位置来开启一个传送门。雪儿的左手边是该实验房间的出口，大门上方有一个计数器连接着所有的弹簧板，计数器的初始值是n。

雪儿很快解开了这个实验室的谜题。她需要在同伴方块生成器的下方地板上开一个传送门，并在弹簧板房间中的天花板上选择一个位置开启传送门的另一端。这样同伴方块会掉进传送门，从天花板上竖直落下，然后在n块弹簧板上弹呀弹，最后掉进最右边的焚化炉。同伴方块每在弹簧板上弹一下，出口大门上方的计数器就会-1；当计数器的数值mod n刚好等于0时，出口就会开启。当然，只弹一次计数器是不会刚好mod n为0的，为了使得计数器的值再次为0，雪儿可能需要不断调整弹簧板上方传送门的位置，由于每个同伴方块被焚化炉焚毁时，生成器就会弹出一个新的同伴方块，所以她有无限次反复尝试的机会。

雪儿心想，这道题目实在easy，因为弹簧板的弹射距离是固定的，只需要从右往左花费O(n)的时间，就能求出任何一个弹簧板弹到最右边需要多少次，剩下的事情雪儿可以人脑处理好。然而GLaDOS看穿了雪儿的想法，决定加大实验室难度，因此GLaDOS会时不时的修改某一个弹簧板的弹射距离。这下雪儿傻眼了，她心想：如果我只管保存每个弹簧板的弹射距离，那么修改是O(1)的，询问是O(n)的；但如果我选择维护每个弹簧板弹到最右边需要多少次，那么询问是O(1)的，修改却是O(n)的。不管怎么写时间复杂度都是O(nm)，根本过不去啊！

此时在旁边默默看了很久的你说了一句话：“这不是裸的动态树Link-Cut-Tree嘛，水题啦，10分钟就写完了。”

雪儿的内心是崩溃的：过一个实验室要写LCT，你就不能考虑一下玩家们对游戏难度的接受能力吗。

于是你说：“唉，没办法，我用分块总行了吧，O(sqrt(n)m)的。”

雪儿想了想觉得可以，于是她把实验室任务分成了两个部分，你只需要负责反复回答她的询问：从某个点投下同伴方块的话，计数器会减少多少。剩下的任务雪儿会去完成。当然，你也需要对付GLaDOS时不时对某个弹簧板弹射距离的修改。

Input Format

第一行一个正整数n，表示地上有n块弹簧板。由于弹簧板的编号从0开始，所以有第0块弹簧板。

接下来一行n个正整数ki，表示第i块弹簧板的弹射距离。比如弹射距离为1的话，落到这块弹簧板上的同伴方块就会被弹射到下一块弹簧板上，依此类推。

接下来一行一个正整数m，表示有总共m个的询问和修改。

接下来m行。每行的第一个正整数为a。如果a=1，则这一行总共会有两个自然数a、b，代表这是一个询问，雪儿询问同伴方块落到第b块弹簧板上时会被弹射多少次。如果a=2，则这一行总共会有三个自然数a、b、c，代表这是一个修改，GLaDOS将第b块弹簧板的弹射距离修改成了c，c大于0。

Output Format

对于每个a=1的情况输出一行一个正整数，代表对雪儿询问的回答。

Sample Input

Sample Output

2
3

样例说明：再次提示，弹簧板的编号是从0开始的。

Data Range

对于\(30\%\)的数据，\(n \le 1000, m \le 1000\)。

对于额外\(20\%\)的数据，\(a=1\)出现的次数小于100。

对于额外\(20\%\)的数据，\(a=2\)出现的次数小于100。

对于\(100\%\)的数据，\(n \le 500000, m \le 100000\)。

FineArtz's solution

/* Welcome to the Aperture Science */
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n, m, N, M;
int a[500005], b[710][1400], c[710][1400];

inline int query(int x){
    int p = x / N, q = x - p * N;
    int ret = 0;
    for (int i = p; i < M; ++i){
        ret += c[i][q];
        q = b[i][q];
    }
    if (n % M != 0){
        ret += c[M][q];
    }
    return ret;
}

inline void update(int x, int y){
    int p = x / N, q = x - p * N;
    a[x] = y;
    int st = p * N, ed = st + N;
    if (p != M){
        for (int j = q; j >= 0; --j){
            if (j + a[st + j] >= N){
                b[p][j] = j + a[st + j] - N;
                c[p][j] = 1;
            }
            else{
                b[p][j] = b[p][j + a[st + j]];
                c[p][j] = c[p][j + a[st + j]] + 1;
            }
        }
    }
    else{
        for (int j = q; j >= 0; --j){
            if (j + st >= n)
                continue;
            if (j + a[st + j] >= n - st){
                b[p][j] = j + a[st + j] - n + st;
                c[p][j] = 1;
            }
            else{
                b[p][j] = b[p][j + a[st + j]];
                c[p][j] = c[p][j + a[st + j]] + 1;
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    N = sqrt(n);
    M = n / N;
    for (int i = 0; i < M; ++i){
        int st = i * N, ed = st + N;
        for (int j = N - 1; j >= 0; --j){
            if (j + st >= n)
                continue;
            if (j + a[st + j] >= N){
                b[i][j] = j + a[st + j] - N;
                c[i][j] = 1;
            }
            else{
                b[i][j] = b[i][j + a[st + j]];
                c[i][j] = c[i][j + a[st + j]] + 1;
            }
        }
    }
    if (n % M != 0){
        int st = N * M, ed = st + N;
        for (int j = N - 1; j >= 0; --j){
            if (j + st >= n)
                continue;
            if (j + a[st + j] >= n - st){
                b[M][j] = j + a[st + j] - n + st;
                c[M][j] = 1;
            }
            else{
                b[M][j] = b[M][j + a[st + j]];
                c[M][j] = c[M][j + a[st + j]] + 1;
            }
        }
    }
    scanf("%d", &m);
    while (m--){
        int op, u, v;
        scanf("%d", &op);
        if (op == 1){
            scanf("%d", &u);
            printf("%d\n", query(u));
        }
        else{
            scanf("%d%d", &u, &v);
            update(u, v);
        }
    }
    return 0;
}

WashSwang's solution

#include <cstdio>
#include <cmath>
using namespace std;
int a,b,k[510000],jump[510000],to[510000],n,m,p,q,ans[100001],s,l[510000];//jump代表跳出块需要的次数 to代表跳出块以后下一个块的坐标
inline void upgrade(int x)
{
    if (k[x]+x>=l[x]+b||k[x]+x>=n) {
        jump[x] = 1;
        to[x]=k[x]+x;
    }
    else{
        jump[x]=jump[k[x]+x]+1;
        to[x]=to[k[x]+x];
    }
}
int main() {
    scanf("%d",&n);
    b=int(sqrt(n));//块的大小
    for (int i=0;i<n;++i) {
        scanf("%d", &k[i]);
        if (p==b) {p=0; q+=b;}
        l[i]=q;
        p++;
    }
    for (int i=n-1;i>=0;--i)
        upgrade(i);
    scanf("%d",&m);
    for (int i=0;i<m;++i)
    {
        scanf("%d",&a);
        if (a==1)
        {
            scanf("%d",&p);
            for (int j=p;j<n;j=to[j])
                ans[s]+=jump[j];
            s++;
        }
        if (a==2)
        {
            scanf("%d%d",&p,&q);
            k[p]=q;
            for (int j=p;j>=l[p];j--)
                upgrade(j);
        }
    }
    for (int i=0;i<s;++i)
        printf("%d\n",ans[i]);
    return 0;
}