E. 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 ai). If you throw a ball into hole i it will immediately jump to hole i + ai, 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 ≤ 105, 1 ≤ M ≤ 105) — 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
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.
Examples
input
8 5 1 1 1 1 1 2 8 2 1 1 0 1 3 1 1 0 3 4 1 2
output
8 7 8 5 7 3
THIS PROBLEM CAN BE SOLVED WITH SQRT DECOMPOSITION , AND SOME BASIC CONCEPT OF DYNAMIC PROGRAMMING ,
FIRST OF ALL WE DIVIDE THE ENTIRE HOLES IN TO BLOCKS , EACH BLOCK WILL CONTAIN AT MAX 350 HOLES ,
NOW WE WILL KEEP TRACK OF 3 THINGS
1-> NEXT[i] = IF WE ARE CURRENTLY AT SOME INDEX i , SO ITS CURRENT BLOCK WILL BE i/350( SAY IT x) , NEXT[i] WILL CONTAIN THE FIRST INDEX IN NEXT BLOCK(x+1) WHICH IT WILL REACH ... IN ITS MOVE ..
2-> COUNT[i]= IF WE ARE AT INDEX i NUMBER OF MOVES REQUIRED TO LEAVE THE CURRENT BLOCK AND REACH TO THE NEXT BLOCK .. ( ie FORM BLOCK x TO x+1 )
MEANS NUMBER OF MOVE IN THE SAME BLOCK BEFORE REACHING TO NEXT BLOCK
3->LAST[i] = IF WE ARE AT INDEX i , IT WILL CONTAIN THE LAST INDEX( IN THE CURRENT BLOCK ) WHICH COVER WHILE LEAVING CURRENT BLOCK
NOTE:- ALWAYS NEXT[i]= LAST[i]+ARR[LAST[i]] SINCE FORM LAST INDEX WE MAKE A JUMP TO REACH TO THE NEXT INDEX IN NEXT BLOCK...
ALL THESE 3 ARRAY CAN BE CALCULATED USING BACKWARD DP .......
for(int i=n-1;i>=0;i--) fix(i);
int fix(int i)
{
//if ith index will directly go out of the block in next move than steps taken in the block=1, //next=i+arr[i] and last index used in the same block will be i ..
if((i+arr[i])>=n || (i+arr[i])/bs!=i/bs)
{
nexxt[i]=i+arr[i];
cnt[i]=1;
last[i]=i;
}
// else if remain i the same block , than count will be equal to count of i+arr[i] , and also
// next will be the next of i +arr[i] , ans last will be also same as last of i+arr[i]
else
{
cnt[i]=1+cnt[i+arr[i]];
nexxt[i]=nexxt[i+arr[i]];
// cout<<" set last of "<<i<<" as "<<last[i+arr[i]]<<endl;
last[i]=last[i+arr[i]];
}
}
now
we have 2 types of query ,
for type 1 query , we just need to count the number for jump , which can be easily calculate now
start from the current node and add count[cur] for the current node( which will give answer for the no of moves taken inside the block ) ans than jump to the next block ,, till no reach to some index>=n
if(type)
{
int ans=0;
int cur;
scanf("%d",&cur);
cur--;
int l=last[cur];
while(cur<n)
{
ans+=cnt[cur];// add moves within same block
l=last[cur];// this node will be the last index used in current block
cur=nexxt[cur]; // go to next block
}
printf("%d %d\n",(l+1),ans);
}
for type 0 query ,
suppose we update the value at index a , what are index affected due to that ,,
obviously some indexs < a since these are the index can go through 'a'
now according to our method we have calculated next[i] , count[i] , and last[i] for each block
so the answer of the index which lies in some block < than the block of 'a' can be affected but we need to update the next , count, and last of index in the current block only , since index in other block < than current block can use the values of of this block ..( if they reach in this block).
else// calling fix function for all index < a and in the block of a
{
int a,b;
scanf("%d %d",&a,&b);
a--;
arr[a]=b;
int cur=a;
while(cur>=0 && cur/bs==a/bs)
{
fix(cur);
cur--;
}
}
===============================CODE=================================
#include<bits/stdc++.h>
using namespace std;
int arr[1000000];
int nexxt[1000000];
int cnt[1000000];
int last[1000000];
int bs=350;
int n,q;
int fix(int i)
{
if((i+arr[i])>=n || (i+arr[i])/bs!=i/bs)
{
nexxt[i]=i+arr[i];
cnt[i]=1;
last[i]=i;
}
else
{
cnt[i]=1+cnt[i+arr[i]];
nexxt[i]=nexxt[i+arr[i]];
// cout<<" set last of "<<i<<" as "<<last[i+arr[i]]<<endl;
last[i]=last[i+arr[i]];
}
}
int main()
{
cin>>n>>q;
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(int i=n-1;i>=0;i--)
{
fix(i);
}
for(int i=0;i<q;i++)
{
int type;
scanf("%d",&type);
if(type)
{
int ans=0;
int cur;
scanf("%d",&cur);
cur--;
int l=last[cur];
while(cur<n)
{
ans+=cnt[cur];
l=last[cur];
cur=nexxt[cur];
}
printf("%d %d\n",(l+1),ans);
}
else
{
int a,b;
scanf("%d %d",&a,&b);
a--;
arr[a]=b;
int cur=a;
while(cur>=0 && cur/bs==a/bs)
{
fix(cur);
cur--;
}
}
}
}
====================================OR===========================
Let's divide all row into blocks of length K=sqrt(N) of consecutive holes. If N is not a complete square, then we will take K=sqrt(N) rounded down. For each hole we will maintain not only it's power (let's call it power[i]), but also the number of the first hole which belongs to other block and which can be reached from the current one with sequence of jumps (let's call it next[i]). Also, for each hole we will maintain the number of jumps required to reach the hole next[i] from the current one (let's call it count[i]). We will consider that there is a fictious hole, which lies after the hole N and it belongs to it's own block.
To answer the query of the first type (when the ball is thrown) we will jump from the hole i to hole next[i] and so on, until we reach the fictious hole. Each time we will add count[i] to the answer. We will jump not more than N/K times.
To maintain the query of the seqond type (when the power of hole i is changed) we will change power[i], next[i] and count[i]. Then for each hole which belongs to the same block as i and has smaller number than i we will update next[i] and power[i] in decreasing order of number of the hole. We will perform not more than K updates.
The complexity is O(Nsqrt(N)).
.
? We use a max-segment tree which does these two operations: