Product of Prices

I've solved another Binary Indexed Tree problem today. It is the Div 1 Hard problem from TopCoder SRM 424. This problem is a bit harder to formulate than the previous one. You can check the complete analysis of the problem in the official match editorial. And don't forget to check the tutorial if you have any difficulty understanding BIT.



I'm not going into any detail analysis today as the editorial explains the solution nicely. Just note that BIT stores the frequencies from index 1 and in this problem we need indices in the range [0,L). So, we have to increase each index by 1.

/*
Problem Name : Product Of Prices
Problem Number : TopCoder SRM 424 Div 1 Hard
Link : http://www.topcoder.com/stat?c=problem_statement&pm=10170&rd=13515
Problem Type : Search
Difficulty : 6.5 / 10
Interest : 8.5 / 10
Complexity : O(NlogL)
Date : November 16, 2010
*/

#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define MAXL 200000
#define i64 long long

const i64 MOD = 1000000007;

i64 tree[2][MAXL+2];
int L;

struct ProductOfPrices{
 void update(int tr, int dex, int val) {
  while(dex <= L) {
   tree[tr][dex] += val;
   dex += (dex & -dex);
  }
 }

 i64 read(int tr, int dex) {
  i64 sum = 0;
  while(dex > 0) {
   sum += tree[tr][dex];
   dex -= (dex & -dex);
  }
  return sum;
 }

 int product(int N, int L, int X0, int A, int B) {
  ::L = L;
  int x;
  int i;
  i64 f1,f2, s1,s2, sl,sh;
  i64 res = 1;
  A %= L;
  B %= L;
  memset(tree,0,sizeof(tree));
  x = X0 % L;
  update(0,x+1,1);
  update(1,x+1,x+1);
  for(i=1;i<N;i++) {
   x = (x * (long long)A + B) % L;
   f1 = read(0,x+1); //total numbers below (or equal) current number
   f2 = read(0,L) - f1; //total numbers above current number

   s1 = read(1,x+1); // sum below (or equal) current number
   s2 = read(1,L) - s1; // sum above current number

   sl = (f1 * (x+1) - s1)%MOD; //sum of differences for numbers below (or equal) current number
   sh = (s2 - f2 * (x+1))%MOD; //sum of differences for numbers above current number
   res = (res * (sl + sh)%MOD) % MOD;
   
   update(0,x+1,1);
   update(1,x+1,x+1);
  }
  return res;
 }
};