codeforces 13EE. Holes(分块&动态树)

Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are N holes located in a single row and numbered from left to right with numbers from 1 to N. Each hole has it's own power (hole number i has the power a_i). If you throw a ball into hole i it will immediately jump to hole i + a_i, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M moves the player can perform one of two actions:

Set the power of the hole a to value b.
Throw a ball into the hole a and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row.

Petya is not good at math, so, as you have already guessed, you are to perform all computations.

Input

The first line contains two integers N and M (1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M lines describe moves made by Petya. Each of these line can be one of the two types:

0 a b
1 a

Type 0 means that it is required to set the power of hole a to b, and type 1 means that it is required to throw a ball into the a-th hole. Numbers a and b are positive integers do not exceeding N.

Output

For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

Sample test(s)

input
5
1 1 1 1 2 8 2
1
1 3
1
3 4
2

output
7
5
3

题意：

给你n个编号1到N的洞(N<=1e5)。

每一个洞有个能量值po[i]。

当你在i号洞里放一个球时.这个球会弹到i+po[i]号洞内。

然后弹到i+po[i]+po[i+po[i]]。。

。。也就是说球每到一个洞i就会弹到i+po[i]号洞内。

如今有两种操作。

1.0 a b。把a号洞的po改成b

2.1 a。

询问当把球放到a号洞内时。它是从几号洞弹出界的。和它一共弹了几次。

思路：

假设题目没有改动操作。这题就会非常easy。

我们仅仅须要把每一个洞的出界点和弹跳数预处理出来就能够了。如今关键是怎么处理改动操作。假设还是依照上述预处理方式肯定时间复杂度下不来。

所以我们要想办法使每次改动操作更新尽量少的信息。于是能够想到分块处理。就是把整个序列分成sqrt(N)块。序列中每一个节点记录next[i]表示i结点要跳到下个块的位置。ed[i]表示放到i号洞时的出界位置。st[i]表示。

i跳到下个块须要的步数。这样预处理后每次改动操作仅仅会影响同块内且标号比当前小的位置的信息。

所以最多改动sqrt(n)个位置的信息。对于每次查询操作。因为结点指针仅仅会指向不同的块所以仅仅须要顺着指针统计一遍就好了。最多跳sqrt(n)次。

总时间发杂度O(M*sqrt(N))在能够接受的范围内。

具体见代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int st[maxn],next[maxn],ed[maxn],po[maxn];
int block,n,m,ans,ansp;
void update(int x,int y)
{
    if(y>n)
        ed[x]=x,st[x]=1,next[x]=y;
    else
    {
        ed[x]=ed[y];//ed[x]为从x处放球的终点
        if(x/block==y/block)
            next[x]=next[y],st[x]=st[y]+1;//next[i]表示i跳到另外的块的位置
        else
            next[x]=y,st[x]=1;
    }
}
void qu(int x)
{
    ans=0;
    while(1)
    {
        ans+=st[x];
        if(next[x]>n)
        {
            ansp=ed[x];
            break;
        }
        x=next[x];
    }
}
int main()
{
    int i,cmd,a,b;

    while(~scanf("%d%d",&n,&m))
    {
        block=ceil(sqrt(1.0*n));
        for(i=1;i<=n;i++)
            scanf("%d",&po[i]);
        for(i=n;i>=1;i--)
            update(i,i+po[i]);
        while(m--)
        {
            scanf("%d%d",&cmd,&a);
            if(cmd)
            {
                qu(a);
                printf("%d %d
",ansp,ans);
            }
            else
            {
                scanf("%d",&po[a]);
                b=(a/block)*block;
                b=max(b,1);
                for(i=a;i>=b;i--)
                    update(i,i+po[i]);
            }
        }
    }
    return 0;
}

codeforces 13EE. Holes(分块&amp;动态树)

codeforces 13EE. Holes(分块&动态树)