[Template] Convex Hull

struct Point {  
      int x, y;  
      Point(int x = 0, int y = 0)  
            : x(x), y(y) {}  
};  
  
bool cmp(Point a, Point b) {  
      return a.x < b.x || (a.x == b.x && a.y < b.y);  
}  
  
bool cw(Point a, Point b, Point c) {  
      return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;  
}  
  
bool ccw(Point a, Point b, Point c) {  
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;  
}  
  
vector <Point> convex_hull(vector <Point>& a) {  
      if (a.size() == 1) {  
            return {};  
      }  
      sort(a.begin(), a.end(), &cmp);  
      Point p1 = a[0];  
      Point p2 = a.back();  
      vector <Point> up;  
      vector <Point> down;  
      up.push_back(p1);  
      down.push_back(p1);  
      for (int i = 1; i < (int)a.size(); i++) {  
            if (i == a.size() - 1 || cw(p1, a[i], p2)) {  
                  while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i])) {  
                        up.pop_back();  
                  }  
                  up.push_back(a[i]);  
            }  
            if (i == a.size() - 1 || ccw(p1, a[i], p2)) {  
                  while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i])) {  
                        down.pop_back();  
                  }  
                  down.push_back(a[i]);  
            }  
      }  
      vector <Point> hull;  
      for (int i = 0; i < (int)up.size(); i++) {  
            hull.push_back(up[i]);  
      }  
      for (int i = down.size() - 2; i > 0; i--) {  
            hull.push_back(down[i]);  
      }  
      return hull;  
}  

[Template] Segment Tree Lazy Propagation

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Algorithm         : Segment Tree Lazy Propagation
Source            : 
Category          : 
Algorithm         : 
Verdict           : Tested

struct data
{
      ll sum;
      data() : sum(0) {}
};
 
ll store[Max];
 
struct SegTree
{
      int N;
      vector <data> st;
      vector <bool> cLazy;
      vector <ll> lazy;
 
      void init(int n)
      {
            N = n;
            st.resize(4 * N + 5);
            cLazy.resize(4 * N + 5);
            lazy.resize(4 * N + 5);
      }
      void merge(data &cur, data &l, data &r)
      {
            cur.sum = (l.sum + r.sum) % mod;
      }
      void propagate(int node, int L, int R)
      {
            if (L != R)
            {
                  int lft = node * 2;
                  int rgt = lft + 1;
                  cLazy[lft] = 1;
                  cLazy[rgt] = 1;
                  lazy[lft] = (lazy[lft] + lazy[node]) % mod;
                  lazy[rgt] = (lazy[rgt] + lazy[node]) % mod;
            }
            st[node].sum = (st[node].sum + lazy[node]) % mod;
            cLazy[node] = 0;
            lazy[node] = 0;
      }
      void build(int node, int L, int R)
      {
            if (L == R)
            {
                  st[node].sum = store[L];
                  cLazy[node] = 0;
                  lazy[node] = 0;
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            build(lft, L, M);
            build(rgt, M + 1, R);
            merge(st[node], st[lft], st[rgt]);
      }
      data Query(int node, int L, int R, int i, int j)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (j < L || i > R) return data();
            if (i <= L && R <= j) return st[node];
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            data p = Query(lft, L, M, i, j);
            data q = Query(rgt, M + 1, R, i, j);
            data cur;
            merge(cur, p, q);
            return cur;
      }
      data pQuery(int node, int L, int R, int pos)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (L == R) return st[node];
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            if (pos <= M) return pQuery(lft, L, M, pos);
            else return pQuery(rgt, M + 1, R, pos);
      }
      void update(int node, int L, int R, int i, int j, ll val)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (j < L || i > R) return;
            if (i <= L && R <= j)
            {
                  cLazy[node] = 1;
                  lazy[node] = (lazy[node] + val) % mod;
                  propagate(node, L, R);
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            update(lft, L, M, i, j, val);
            update(rgt, M+1, R, i, j, val);
            merge(st[node], st[lft], st[rgt]);
      }
      void pUpdate(int node, int L, int R, int pos, ll val)
      {
            if (cLazy[node]) propagate(node, L, R);
            if (L == R)
            {
                  cLazy[node] = 1;
                  lazy[node] = (lazy[node] + val) % mod;
                  propagate(node, L, R);
                  return;
            }
            int lft = node * 2;
            int rgt = lft + 1;
            int M = (L + R) / 2;
            if (pos <= M) pUpdate(lft, L, M, pos, val);
            else pUpdate(rgt, M+1, R, pos, val);
            merge(st[node], st[lft], st[rgt]);
      }
      data query(int pos)
      {
            return pQuery(1, 1, N, pos);
      }
      data query(int l, int r)
      {
            return Query(1, 1, N, l, r);
      }
      void update(int pos, ll val)
      {
            pUpdate(1, 1, N, pos, val);
      }
      void update(int l, int r, ll val)
      {
            update(1, 1, N, l, r, val);
      }
};

[Codemarshal] F. Find the Substrings

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Find the Substrings
Source            : Codemarshal
                    ACM-ICPC 2018 Preliminary
Category          : String, Data Structure
Algorithm         : Suffix Automata, Number of distinct substring
Verdict           : Accepted

#include "bits/stdc++.h"  
using namespace std;  
  
#define ll            long long int  
#define endl          '\n'  
  
static const int maxn = 1e6 + 5;  
static const ll mod = 1e9 + 7;  
static const int Max = 1e6 + 7;  
  
int N;  
ll Tree[maxn];  
  
ll add(ll a, ll b)  
{  
      a = (a + b + mod) % mod;  
      return a;  
}  
  
void update(int pos, ll val)  
{  
      while (pos <= N)  
      {  
            Tree[pos] = add(Tree[pos], val);  
            pos += (pos & -pos);  
      }  
}  
  
void rangeUpdate(int l, int r, ll val)  
{  
      update(l, val);  
      update(r + 1, -val);  
}  
  
ll query(int pos)  
{  
      ll sum = 0;  
      while (pos > 0)  
      {  
            sum = add(sum, Tree[pos]);  
            pos -= (pos & -pos);  
      }  
      return sum;  
}  
  
struct state  
{  
      int len, link;  
      map <char, int> next;  
} st[Max * 2];  
  
int sz, last;  
  
void init()  
{  
      sz = last = 0;  
      st[0].len = 0;  
      st[0].link = -1;  
      st[0].next.clear();  
      for (int i = 1; i < Max * 2; i++)  
      {  
            st[i].len = 0;  
            st[i].link = 0;  
            st[i].next.clear();  
      }  
      ++sz;  
}  
  
void szExtend(char c)  
{  
      int l, r;  
      int cur = sz++;  
      st[cur].len = st[last].len + 1;  
      int p;  
      for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)  
      {  
            st[p].next[c] = cur;  
      }  
      if (p == -1)  
      {  
            st[cur].link = 0;  
      }  
      else  
      {  
            int q = st[p].next[c];  
            if (st[p].len + 1 == st[q].len)  
            {  
                  st[cur].link = q;  
            }  
            else  
            {  
                  int clone = sz++;  
                  st[clone].len = st[p].len + 1;  
                  st[clone].next = st[q].next;  
                  st[clone].link = st[q].link;  
                  for ( ; p != -1 && st[p].next[c] == q; p = st[p].link)  
                  {  
                        st[p].next[c] = clone;  
                  }  
                  l = st[ st[q].link ].len;  
                  r = st[q].len;  
                  assert(l+1 <= r);  
                  rangeUpdate(l+1, r, -1);  
                  st[q].link = st[cur].link = clone;  
                  l = st[ st[q].link ].len;  
                  r = st[q].len;  
                  assert(l+1 <= r);  
                  rangeUpdate(l+1, r, 1);  
                  l = st[ st[clone].link ].len;  
                  r = st[clone].len;  
                  assert(l+1 <= r);  
                  rangeUpdate(l+1, r, 1);  
            }  
      }  
      l = st[ st[cur].link ].len;  
      r = st[cur].len;  
      assert(l+1 <= r);  
      rangeUpdate(l+1, r, 1);  
      last = cur;  
}  
  
ll power[Max];  
ll powerSum[Max];  
ll sum[Max];  
ll cumsum[Max];  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(12);  
  
//      #ifndef ONLINE_JUDGE  
//            freopen("in.txt", "r", stdin);  
//      #endif // ONLINE_JUDGE  
  
      power[0] = 1LL;  
      powerSum[0] = 0LL;  
      for (int i = 1; i < Max; i++)  
      {  
            power[i] = (power[i-1] * 26) % mod;  
            powerSum[i] = (powerSum[i-1] + power[i]) % mod;  
      }  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            string s;  
            cin >> s;  
            int len = s.size();  
            N = len;  
            init();  
            for (char ch : s) szExtend(ch);  
            for (int i = 1; i <= len; i++)  
            {  
                  sum[i] = query(i);  
                  cumsum[i] = add(cumsum[i-1], sum[i]);  
            }  
            cout << "Case " << tcase << ":" << endl;  
            int q;  
            cin >> q;  
            while (q--)  
            {  
                  int l, r;  
                  cin >> l >> r;  
                  ll tsub = (powerSum[r] - powerSum[l-1] + mod) % mod;  
                  ll dsub = (cumsum[r] - cumsum[l-1] + mod) % mod;  
                  ll ans = (tsub - dsub + mod) % mod;  
                  cout << ans << endl;  
            }  
            for (int i = 0; i <= N; i++) Tree[i] = 0;  
      }  
}