[Toph] Unique Substrings Query

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Unique Substrings Query
Source            : Toph.co
Category          : Data Structure, String
Algorithm         : Suffix Automaton, Binary Indexed Tree, Persistent Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll            long long int
#define endl          '\n'
 
static const int maxn = 2e3 + 5;
static const ll mod = 1e9 + 7;
static const int Max = 6e6 + 7;
 
int N = 1000 + 2;
ll Bit[maxn];
 
ll add(ll a, ll b)
{
      a = (a + b);
      return a;
}
 
void bitUpdate(int pos, ll val)
{
      while (pos <= N)
      {
            Bit[pos] = add(Bit[pos], val);
            pos += (pos & -pos);
      }
}
 
void rangeUpdate(int l, int r, ll val)
{
      bitUpdate(l, val);
      bitUpdate(r + 1, -val);
}
 
ll read(int pos)
{
      ll sum = 0;
      while (pos > 0)
      {
            sum = add(sum, Bit[pos]);
            pos -= (pos & -pos);
      }
      return sum;
}
 
struct state
{
      int len, link;
      map <char, int> next;
} st[maxn * 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 < maxn * 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;
}
 
 
struct Node
{
      ll st;
      int lft, rgt;
      Node(ll st = 0, int lft = 0, int rgt = 0) : st(st), lft(lft), rgt(rgt) {}
} Tree[Max];
 
int version[maxn];
int NODES;
//int N = 1000;
 
int update(int root, int a, int b, int pos, ll val)
{
      int newNode = ++NODES;
      Tree[newNode] = Tree[root];
      if (a == b)
      {
            Tree[newNode].st += val;
            return newNode;
      }
      int mid = (a + b) >> 1;
      if (pos <= mid) Tree[newNode].lft = update(Tree[newNode].lft, a, mid, pos, val);
      else Tree[newNode].rgt = update(Tree[newNode].rgt, mid + 1, b, pos, val);
      Tree[newNode].st = Tree[ Tree[newNode].lft ].st + Tree[ Tree[newNode].rgt ].st;
      return newNode;
}
 
ll query(int proot, int root, int a, int b, int i, int j)
{
      if (a > b or a > j or b < i) return 0;
      if (a >= i && b <= j)
      {
            return Tree[root].st - Tree[proot].st;
      }
      int mid = a + b >> 1;
      ll p = query(Tree[proot].lft, Tree[root].lft, a, mid, i, j);
      ll q = query(Tree[proot].rgt, Tree[root].rgt, mid + 1, b, i, j);
      return p + q;
}
 
int originalVersion[maxn];
 
signed main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      cout << fixed << setprecision(8);
 
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
      int n, m;
      cin >> n >> m;
      string s;
      cin >> s;
      s = "#" + s;
 
      NODES = 0;
      version[0] = 0;
      for (int i = 0; i < maxn; i++) Tree[i] = Node();
 
      int ptr = 0;
      originalVersion[n + 1] = 0;
      init();
      int len = 0;
      for (int i = n; i >= 1; i--)
      {
            szExtend(s[i]);
            ++len;
            ++ptr;
            originalVersion[i] = ptr;
            bool isCreated = 0;
            for (int j = 1; j <= len; j++)
            {
                  ll val = read(j);
                  if (isCreated == 0)
                  {
                        version[ptr] = update(version[ptr - 1], 1, N, j, val);
                        isCreated = 1;
                  }
                  else
                  {
                        version[ptr] = update(version[ptr], 1, N, j, val);
                  }
            }
      }
      while (m--)
      {
            int L, R, P, Q;
            cin >> L >> R >> P >> Q;
            ll ans = query(version[ originalVersion[R + 1] ], version[ originalVersion[L] ], 1, N, P, Q);
            cout << ans << '\n';
      }
}
 
 

[CS Academy] Rectangle Fit

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Rectangle Fit
Source            : CS Academy
Category          : Data Structure, PBDS
Algorithm         : Easy implementation of Compressed 2D Binary Indexed Tree for grid of 
                    binary numbers
Verdict           : Accepted

Algo Link : Compressed 2D Binary Indexed Tree

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
#define pii           pair <int, int>
#define piii          pair <pii, int>
#define mk            make_pair
 
template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
static const int maxn = 1e6 + 5;
 
int N = 1000000;
orderset <piii> bit[maxn];
int ptr;
 
void Insert(int x, int y)
{
      for (int i = x; i <= N; i += (i & -i))
      {
            bit[i].insert(mk(mk(y, x), ++ptr));
      }
}
 
void Remove(int x, int y)
{
      for (int i = x; i <= N; i += (i & -i))
      {
            bit[i].erase(mk(mk(y, x), -1));
      }
}
 
int query(int x, int y)
{
      int ans = 0;
      for (int i = x; i > 0; i -= (i & -i))
      {
            ans += bit[i].order_of_key(mk(mk(y + 1, 0), -1));
      }
      return ans;
}
 
signed main()
{
      int n, area;
      scanf("%d %d", &n, &area);
      vector <pii> point;
      for (int i = 1; i <= n; i++)
      {
            int x, y;
            scanf("%d %d", &x, &y);
            point.push_back(mk(x, y));
      }
      sort(point.begin(), point.end());
      for (pii p : point) Insert(p.first, p.second);
      int maxPoints = 0;
      for (int i = 0; i < n; i++)
      {
            int x = point[i].first;
            int y = min(area / x, N);
            int points = query(x, y);
            maxPoints = max(maxPoints, points);
      }
      printf("%d\n", maxPoints);
}
 

[Toph] Taju Kage Bunshin No Jutsu

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Taju Kage Bunshin No Jutsu
Source            : Toph.CO
Category          : Data Structure
Algorithm         : Persistent Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 4e5 + 5;  
static const int Max = 2e7 + 5;  
  
struct Node  
{  
      int st;  
      int lft, rgt;  
      Node(int st = 0, int lft = 0, int rgt = 0) : st(st), lft(lft), rgt(rgt) {}  
} Tree[Max];  
  
int version[maxn];  
int NODES;  
int N = 300000 + 5;  
  
int update(int root, int a, int b, int pos, int val)  
{  
      int newNode = ++NODES;  
      Tree[newNode] = Tree[root];  
      if (a == b)  
      {  
            Tree[newNode].st += val;  
            return newNode;  
      }  
      int mid = (a + b) >> 1;  
      if (pos <= mid) Tree[newNode].lft = update(Tree[newNode].lft, a, mid, pos, val);  
      else Tree[newNode].rgt = update(Tree[newNode].rgt, mid + 1, b, pos, val);  
      Tree[newNode].st = Tree[ Tree[newNode].lft ].st + Tree[ Tree[newNode].rgt ].st;  
      return newNode;  
}  
  
int query(int proot, int root, int a, int b, int k)  
{  
      if (a == b) return a;  
      int mid = a + b >> 1;  
      int sizeLeftChild = Tree[ Tree[root].lft ].st - Tree[ Tree[proot].lft ].st;  
      if (k <= sizeLeftChild) return query(Tree[proot].lft, Tree[root].lft, a, mid, k);  
      else return query(Tree[proot].rgt, Tree[root].rgt, mid + 1, b, k - sizeLeftChild);  
}  
  
void init()  
{  
      NODES = 0;  
      version[0] = 0;  
      for (int i = 0; i < maxn; i++) Tree[i] = Node();  
}  
  
struct Query  
{  
      int type;  
      int v;  
      int l, r, k;  
      Query(int type = 0, int v = 0, int l = 0, int r = 0, int k = 0)  
            : type(type)  
            , v(v)  
            , l(l)  
            , r(r)  
            , k(k) {}  
};  
  
vector <Query> queries;  
vector <int> vec;  
int arr[maxn];  
map <int, int> mapper, rmapper;  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      for (int i = 1; i <= n; i++)  
      {  
            cin >> arr[i];  
            vec.emplace_back(arr[i]);  
      }  
      int q;  
      cin >> q;  
      for (int i = 1; i <= q; i++)  
      {  
            int type;  
            cin >> type;  
            if (type == 1)  
            {  
                  int v;  
                  cin >> v;  
                  queries.emplace_back(type, v);  
                  vec.emplace_back(v);  
            }  
            else if (type == 2)  
            {  
                  queries.emplace_back(type);  
            }  
            else  
            {  
                  int l, r, k;  
                  cin >> l >> r >> k;  
                  queries.emplace_back(type, 0, l, r, k);  
            }  
      }  
      sort(vec.begin(), vec.end());  
      int ptr = 0;  
      for (int x : vec)  
      {  
            if (mapper.find(x) == mapper.end())  
            {  
                  mapper[x] = ++ptr;  
                  rmapper[ptr] = x;  
            }  
      }  
      init();  
      for (int i = 1; i <= n; i++)  
      {  
            arr[i] = mapper[ arr[i] ];  
            version[i] = update(version[i-1], 1, N, arr[i], 1);  
      }  
      int lastVersion = n;  
      for (Query &it : queries)  
      {  
            if (it.type == 1)  
            {  
                  it.v = mapper[it.v];  
                  int newVersion = lastVersion + 1;  
                  version[newVersion] = update(version[lastVersion], 1, N, it.v, 1);  
                  lastVersion = newVersion;  
            }  
            else if (it.type == 2)  
            {  
                  --lastVersion;  
            }  
            else  
            {  
                  int l = it.l;  
                  int r = it.r;  
                  int k = it.k;  
                  k = (r - l + 1) - k + 1;  
                  int kth = query(version[l-1], version[r], 1, N, k);  
                  cout << rmapper[kth] << endl;  
            }  
      }  
}