In this HackerEarth Convoluted Operations problem solution, Mishki is quite interested in playing games, and recently she found an empty stack. Now she wants to perform 3 types of operations on the stack:
  1. 1 A : push element A in the stack.
  2. 0 : pop one element from stack.
  3. 2 K X : find how many elements were less than X present in the stack, after performing Kth operation on the stack.
Can you help her in performing the above operations ?


HackerEarth Convoluted Operations problem solution

HackerEarth Convoluted Operations problem solution.

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int ma = 5e5+5;

ll n, ans[ma], pus[ma], bit[ma],op[ma], val[ma], compr[ma];
pair <ll, ll> p[ma];
vector < pair<ll,ll> >  v[ma];

void update(int x, int val)
{
  
  while(x<=5e5)
  {
    bit[x]+=val;
    x = x + (x&-x);
  }
}
int query(int x)
{

  int an=0;
  while(x>0)
  {
    an+=bit[x];
    x = x&(x-1);
  }
  return an;
}
int main(int argc, char* argv[])
{
  //freopen(argv[1],"r",stdin);
  //freopen(argv[2],"w",stdout);*/
  cin>>n;
  ll x,y,k,q=0,opr=1,cnt=0;

  for(int i=1;i<=n;i++)
  {
    cin>>x;
    if(x==1)
    {
      cin>>y;
      p[i] = make_pair(x,y);
      compr[cnt++] = y;
    }
    else if(x==0)
      p[i] = make_pair(x,-1);
    else
    {
      p[i] = make_pair(-1,-1);
      cin>>op[q]>>val[q];
      compr[cnt++] = val[q];
      q++;
    }
  }
  //compression
  sort(compr, compr+cnt);
  for(int i=1;i<=n;i++)
  {
    
    if(p[i].first!=-1 and p[i].second!=-1)
    {
      p[i].second = lower_bound(compr, compr+cnt, p[i].second) - compr+1;
    }

  }
  for(int i=0;i<q;i++)
  {
    val[i] = lower_bound(compr, compr+cnt, val[i]) - compr+1;
  }

  for(int i=0;i<q;i++)
  {
    v[op[i]].push_back(make_pair(val[i],i));
  }
  int o=0;
  for(int i=1;i<=n;i++)
  {
      if(p[i].first==1)
      {
        update(p[i].second,1); 
        pus[o++] = i;
      }
      else if(p[i].first==0)
      {
        update(p[pus[o-1]].second,-1);
        o--;
      }

      if(v[i].size())
      {
        for(int j=0;j<v[i].size();j++)
        {
          ans[v[i][j].second] = query(v[i][j].first-1);
        }
      }
  }
  for(int i=0;i<q;i++)
  {
    cout<<ans[i]<<endl;
  }
  return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int N;
int A[500001];
vector<int> adj[500001];
vector<int> q[500001];
int T[500001];
int P[500001];
int X[500001];
int C[500001], NC;
int bit[500001];
int ans[500001];

void add(int x, int v)
{
    for(x=lower_bound(C, C+NC, x)-C+1; x<=NC; x+=x&-x)
        bit[x]+=v;
}

int sum(int x)
{
    int ret=0;
    for(x=lower_bound(C, C+NC, x)-C+1; x>0; x-=x&-x)
        ret+=bit[x];
    return ret;
}

void dfs(int u)
{
    for(auto& it: q[u])
        ans[it]=sum(X[it]);
    for(auto& v: adj[u])
    {
        add(A[v]+1, 1);
        dfs(v);
        add(A[v]+1, -1);
    }
}

int main()
{
    memset(ans, -1, sizeof ans);
    scanf("%d", &N);
    assert(1<=N && N<=500000);
    int n=1;
    for(int i=1; i<=N; i++)
    {
        int op;
        scanf("%d", &op);
        assert(0<=op && op<=2);
        if(op==0)
        {
            assert(T[i-1]);
            T[i]=P[T[i-1]];
        }
        else if(op==1)
        {
            scanf("%d", A+n);
            assert(0<=A[n] && A[n]<=1000000000);
            C[NC++]=A[n]+1;
            P[n]=T[i-1];
            adj[P[n]].push_back(n);
            T[i]=n++;
        }
        else
        {
            int k, x;
            scanf("%d%d", &k, &x);
            assert(1<=k && k<=i);
            assert(0<=x && x<=1000000000);
            C[NC++]=x;
            X[i]=x;
            T[i]=T[i-1];
            q[T[k]].push_back(i);
        }
    }
    sort(C, C+NC);
    dfs(0);
    for(int i=1; i<=N; i++) if(ans[i]!=-1)
        printf("%d\n", ans[i]);
    return 0;
}