0 like 0 dislike
1,257 views
| 1,257 views

0 like 0 dislike

Problem name
K-step sequence
Problem statement
Given an array A containing N numbers that are indexed from 1 to N. You are also given Q queries

Each query can be described as follows:

L R K : Print the sum of all numbers that are available in array A, are a part of a K-step sequence, and have their indexes in the range L to R.
A K-step sequence for the given array can be defined as A(1),A(1+K),A(1+2K),... where A(i) denotes the array element at index i.

Example

Assumptions

N = 3
A = [1, 2, 3]
Q = 2
Queries = [[1, 2, 1], [2, 3, 2]]
Approach

You must determine the answer to each query:

For the 1st query, we have values of the array as [1, 2, 3] out of which the value [1, 2] has indexed in a given range. Therefore the answer is 3.

For the 2nd query, we have values of the array as [1, 3] out of which the value [3] has indexed in a given range. Therefore the answer is 3.

``````ll n,q;
ll a[maxN+5];
vector<ll> g[maxN+5],csum[maxN+5];

ll lowerBound(ll k,ll v)
{
ll s,e,m;
s=0;
e=g[k].size()-1;
while((e-s)>1)
{
m=s+(e-s)/2;
if(g[k][m]<=v)
s=m;
else
e=m-1;
}
if(g[k][e]<=v)
return e;
if(g[k][s]<=v)
return s;
return -1;
}

ll upperBound(ll k,ll v)
{
ll s,e,m;
s=0;
e=g[k].size()-1;
while((e-s)>1)
{
m=s+(e-s)/2;
if(g[k][m]>=v)
e=m;
else
s=m+1;
}
if(g[k][s]>=v)
return s;
if(g[k][e]>=v)
return e;
return -1;
}

int main()
{
ll t,i,j,l,r,k,x,y,ans;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(i=0;i<=n;i++)
{
g[i].clear();
csum[i].clear();
}
for(i=1;i<n;i++)
{
l=0;
for(j=1;j<=n;j+=i)
{
g[i].push_back(j);
csum[i].push_back(a[j]);
if(l)
csum[i][l]+=csum[i][l-1];
l++;
}
}
scanf("%lld",&q);
while(q--)
{
scanf("%lld%lld%lld",&l,&r,&k);
if(k>=n)
{
if(l<=1)
printf("%lld\n",a[1]);
else
printf("0\n");
}
else
{
x=upperBound(k,l);	//first number greater than or equal to l
y=lowerBound(k,r);	//last number less than or equal to r
if(x==-1)
printf("0\n");
else if(y==-1)
printf("0\n");
else
{
ans=csum[k][y];
if(x)
ans-=csum[k][x-1];
printf("%lld\n",ans);
}
}
}
}
return 0;
}``````
by Expert (34,270 points)