Hey CodeForces,

TL;DR How to support different callable types as a template argument?

Data structures like segment tree, sparse table, fenwick tree, etc support various operations like max, min, gcd, sum etc. So it would be convenient to write a generic class for the data structure which takes the required operation as an input while constructing the object of the data structure, much in same spirit that std::sort takes various comparators. The binary operation would then be the data member of the data structure's class.

The problem while implementing the operation as a template parameter is that there are many callable types like: lambdas, functors, functions (std::min, std::gcd), function objects(std::less<int>, std::plus<int>), std::function.

One solution would be:

For functions like std::min, std::gcd to work co-exist std::plus, there will a requirement for a functor with operator() implementing desired functionality. Then the functor can be used a template argument and it would be easy. But it certainly is not convenient to wrap the existing functions like std::gcd, std::max, std::min to a class.

Something like this would be ideal:

sparse_table<int, std::plus<int>> st;
sparse_table<int, std::min<int>> st;

Is there a cleaner solution for this?

TL;DR This article features Modular class which can be conviniently used for modular arithmetic more "naturally".

Motivation

Recent round featured an interesting problem 1081C - Colorful Bricks (if you plan to solve it, read this later). Combinatoric solution requires you to calculate:

Many contestants failed pretest because of missing modulo operation somewhere in code.

Solution

Many contestants use functions like add(ll a, ll b) or mul(ll a , ll b) which makes implementation somewhat clumsy.

I present you an alternate approach using Modular class.

template <int MOD=998'244'353>
struct Modular {
  int value;
  static const int MOD_value = MOD;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};

Using this code can be written more naturally in modular field just like integers. This implementation simplifies usage, for example:

// Chained Multiplication or Successive Simple Multiplication
Modular<998244353> a=1, m=123456789;
a *= m * m * m; // a = 519994069
// Inverse
a=inverse(m) // a=25170271
// fractions
Modular<> frac=(1,2); // frac=1*2^(-1) % 998244353 = 499122177
// Modular exponentiation
Modular<> power(2);
power=mexp(power,500); // power = 616118644

Credits to Jakube and here's the link to original source. Link: Modular.h

I found no blog on ABC 90 or ARC 091 discussion, so let's discuss problem here:

ARC 091 — Link

ABC 090 — Link

If similar blog exists, notify me and I will delete this.

After reading some tutorials on segment tree:

• Efficient and easy segment trees

• Segment Tree by e-maxx

I thought to implement this data structure in Object Oriented methodology whereby I used vector instead of arrays in (contrast with tutorials) approach to hide implementation details, but it verdicts SIGSEGV for size in order of 10^5. But works fine (I hope) for array size less than of 10^4 order;

typedef struct SegmentTree{
   vector<int> tree, udp; int orgsize;
  /******************BUILD***********************/
  SegmentTree(vector<int>& list){ //CONSTRUCTOR
    orgsize=list.size();
    int size=((int)(pow(2,31-__builtin_clz(orgsize))))<<1;
    tree.resize(size); udp.assign(size,0); build(1,0,orgsize-1,list);
  }
  void build(int cur, int s, int e, vector<int>& list){
    if(s==e){ tree[cur]=list[s]; return ;}
    else{
      int mid=(s+e)/2;
      build(cur<<1,s,mid,list); build((cur<<1)+1,mid+1,e,list);
      tree[cur]= tree[cur<<1]+tree[(cur<<1)+1];     //NODE FUNCTION
    }
  }
  /***************  UPDATE  **************************/
  void update(int s, int e, int val){ update(1,0,orgsize-1,s,e,val);}
  void update(int cur, int ts, int te, int s, int e, int val){ //ts: temporary start, cur: current
    if(ts>=s && te<=e) udp[cur]+=val;
    else{
      tree[cur]+=(min(te,e)-max(ts,s)+1)*val;      //NODE FUNCTION
      int mid=(ts+te)/2;
      if(mid>=s && ts<=e) update(cur<<1,ts,mid,s,e,val);
      if(mid+1<=e && te>=s) update((cur<<1)+1,mid+1,te,s,e,val);
    }
  }
  /***************  QUERY ***************************/
  ll query(int s, int e){return q(1,0,orgsize-1,s,e);}
  ll q(int cur, int ts,int te, int s, int e){    //ts: temporary start, cur: current
    if(ts>=s && te<=e){
      if(udp[cur]!=0){
        tree[cur]+=(te-ts+1)*udp[cur];            //NODE FUNCTION
        if(2*cur < udp.size()){
          udp[cur<<1]+=udp[cur];
          udp[(cur<<1)+1]+=udp[cur];
        }
        udp[cur]=0;
      }
      return tree[cur];
    }
    else{
      tree[cur]+=(te-ts+1)*udp[cur];
      if((cur<<1) < udp.size()){
        udp[cur<<1]+=udp[cur];
        udp[(cur<<1)+1]+=udp[cur];
      }
      udp[cur]=0;
      ll temp=0; int mid=(ts+te)/2;
      if(mid>=s && ts<=e) temp+=q(cur<<1,ts,mid,s,e);
      if(mid+1<=e && te>=s) temp+=q((cur<<1)+1,mid+1,te,s,e);
      return temp;
    }
  }
} ST;

I tried this program for SPOJ-Horrible and get "Runtime error — SIGSEGV" which then I presume to arise from implementation as when I tried running on 10^5 it shows that error again.

My submission for above mention problem: Ideone

I tried using global vector of the object udp & tree and also the vector which I used to build this segment tree. But it didn't work. Is there a fix or shall I not use this OOP based implementation? Because

Thank you for having time to read this.!

UPD: Its solved! For those who are wondering the source of bug, it was in the calculation of size in constructor changing to 2 << (32 - __builtin_clz(orgsize - 1)) led to Accepted verdict.