HYSBZ - 2002: Bounce 탄 비 면양 (블록 알고리즘)

바 운 스 탄 면양
어느 날, 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 < = 20000, m < = 100000
Output
모든 i = 1 의 경우 필요 한 걸음 수 를 출력 하여 한 줄 을 차지 해 야 합 니 다.
Sample Input
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Output
2 3
또 조각 을 만 들 었 다   단순 하고 난폭 하 다.   

#include
#include
#include
#include
#include
using namespace std;
struct node
{
    int ahead,step;//ahead          step          
    int Next,pos;//Next            Next 0   pos          
};
int temp;
int block[200005];
node p[200005];
int main()
{
    int n,m,op;
    scanf("%d",&n);
    //memset(block,0,sizeof(block));
    for(int i=0; i=0; i--)//             T 
    {
        if(block[i+p[i].ahead]!=block[i])//         
        {
            p[i].Next=block[i+p[i].ahead];
            p[i].pos=i+p[i].ahead;
            p[i].step=1;
        }
        else
        {
            p[i].Next=p[i+p[i].ahead].Next;
            p[i].pos=p[i+p[i].ahead].pos;
            p[i].step=p[i+p[i].ahead].step+1;
        }
    }
    scanf("%d",&m);
    int x,y;
    for(int cas=1; cas<=m; ++cas)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            int ans=0;
            while(p[x].Next!=0)//        
            {
                ans+=p[x].step;
                x=p[x].pos;
            }
            ans+=p[x].step;
            printf("%d
",ans);
        }
        else if(op==2)//  
        {
            scanf("%d%d",&x,&y);
            p[x].ahead=y;
            int l=(block[x]-1)*temp;
            for(int i=x; i>=l; i--)//             T 
            {
                if(block[i+p[i].ahead]!=block[i])
                {
                    p[i].Next=block[i+p[i].ahead];
                    p[i].pos=i+p[i].ahead;
                    p[i].step=1;
                }
                else
                {
                    p[i].Next=p[i+p[i].ahead].Next;
                    p[i].pos=p[i+p[i].ahead].pos;
                    p[i].step=p[i+p[i].ahead].step+1;
                }
            }
        }
    }
}