LT17-Editorial

editorial
, ,
1

Problem Link

Loop Through

Author:pskalbhav1

Difficulty

HARD

Prerequisites

Dp, Combinatorics

Problem Statement

You want to go attend your friend's party but the guard at the entrance stops you. He gives you a problem to solve and if you are able to do it, you get a free entry.

Given a sequence of n integers, you are allowed to perform the following actions: if p and q be two adjacent numbers, then you can remove them and write p + 2q instead of them. Here, p comes before q in sequence. You have to keep doing so until only 1 number is left. You have to get the biggest possible number.

The guard doesn’t want to let you in. So he erases some of the numbers in a certain pattern.
He has m options, in the option j he erases all numbers to the left of the lj-th number and all numbers to the right of rj-th number. For each of the options he wants to know how big your final number is going to be.

This number can be very big, so output it modulo 109 + 7.

Approach

Let the last number be negative. Then you want to minimize kn. You can always can use kn= 1. If that last number is non-negative, he can use kn = kn-1 + 1. In this case, you can first merge the last two numbers. Thus, the sequence ki consists of several blocks, in each of which ki+1 = ki + 1, and each of the blocks except the first begins with 1.

Now we need to answer queries. We will do it offline. On the step i add the number aiand and answer all queries with r=i. We will support the blocks for the query [1, i].

What happens when we add a number? If it’s negative, it simply forms a separate block. Otherwise it becomes the end of some block. It is easy to see that the new block is the union of several old blocks.

How to answer queries? [l,r] is the union of some blocks and a suffix of another block. We can see that this is the partition into blocks for our query.

How to do it fast? We will store the boundaries of blocks to do binary search on them and find the block in which the l lies. We need to store the results for each block and prefix sums of these results. Also we need to find sums to find out results for suffixes.

Each step is processed in O(log(n)) except for merging blocks. But we create at most one block on each step, so amortized time of each step is O(log(n)).

Also in this problem we need to be careful with overflows. Although we need to find the result modulo some prime, in some places the sign is important. We can use that if |q| is more than maximum ai, then p+2q is also big and have the same sign.

Solution

#include<bits/stdc++.h>

#define int long long
#define ld long double

#define err(A) cout<<#A<<" = "<<(A)<<endl

using namespace std;

const ld big=1e20;
const int M=1e9+7;
const int maxn=131072;
const int mxlg=18;

int n,q;

int a[maxn];

int f[maxn];
int t[maxn];

ld x[maxn];

int L[maxn][mxlg];
int s[maxn][mxlg];

int32_t main()
{
 t[0]=1;
for(int i=1;i<maxn;i++)
t[i]=t[i-1]*2%M;

ios::sync_with_stdio(0);cin.tie(0);

cin>>n>>q;

 for(int i=0;i<n;i++)
cin>>a[i];

for(int i=n;i--;)
f[i]=(f[i+1]*2+a[i])%M;

 for(int i=0;i<n;i++)
{ 
  x[i]=a[i];

  int j=i;
  for(;j and x[i]>0.5;)
if(x[i]>big or !L[j-1][0] or j-L[j-1][0]>40)
  j=0;
else
  x[i]=x[i]*(1ll<<(j-L[j-1][0]))+x[j-1],
  j=L[j-1][0];

  L[i][0]=j;
  s[i][0]=(f[j]-f[i+1]*t[i-j+1]%M)%M;

  for(int j=1;j<mxlg;j++)
if(L[i][j-1])
  L[i][j]=L[L[i][j-1]-1][j-1],
  s[i][j]=(s[i][j-1]+s[L[i][j-1]-1][j-1])%M;
else
  s[i][j]=s[i][j-1];
}
for(int ans,l,r;cin>>l>>r;cout<<ans<<"\n")
{
  ans=0;
  for(int j=mxlg;j--;)
if(L[r-1][j]>l)
  ans+=s[r-1][j],r=L[r-1][j];
  ans=((f[l-1]-f[r]*t[r-l+1]+ans*2)%M+M)%M;
}

return 0;
}