HackerEarth String query problem solution

In this HackerEarth String query problem solution we have given a string s and m queries. For each query delete the K-th occurrence of a character x.

HackerEarth String query problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 5000000007
#define total 500005
#define M 1000000007
#define NIL 0
#define INF (1<<28)
#define MAXN 200001
typedef unsigned long long int uint64;
typedef long long int int64;


int BIT[27][MAXN];
void update(int loc,int x,int vl){
    for(int i=x;i<=MAXN;i+=(i&-i))
        BIT[loc][i]+=vl;
}
int query(int loc,int x){
    int ans=0;
    for(int i=x;i>=1;i-=(i&-i))
        ans+=BIT[loc][i];
    return ans;
}
int remocu(int loc,int x){
    int mid,lb=1,ub=MAXN,ans;
    while(lb<=ub){
        mid=((lb+ub)>>1);
        if(query(loc,mid)>=x){
            ans=mid;
            ub=mid-1;
        }
        else
            lb=mid+1;
    }
    update(loc,ans,-1);
    return ans;
}
bool vis[2000004];
string p,s;
int main(){
    int k,i,x,n;
    char c;
    cin>>s;
    scanf("%d",&n);
    for(i=0;i<s.size();i++){
        update(s[i]-'a',i+1,1);
    }
    while(n--){
        cin>>x>>c;
        //cout<<x<<" "<<c;
        c-='a';
        int le=remocu(c,x);
        //cout<<le<<endl;
        vis[le-1]=1;
    }
    for(i=0;i<s.size();i++){
        if(vis[i]==0)
            printf("%c",s[i]);
    }
    printf("n");
    return 0;
}

Second solution

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ft first
#define sd second
#define VI vector<int>
#define VLL vector<long long int>
#define PII pair<int,int>
#define pb push_back
#define rsz(v,n) v.resize(n)
// input and output
#define scan(x) scanf("%d",&x)
#define scanll(x) scanf("%lld",&x)
#define ll long long int
#define rep(i,x,y) for(i=x;i<y;i++)
#define print(x) printf("%dn",x)
#define printll(x) printf("%lldn",x)
#define all(v) v.begin(),v.end()
#define ms(v) memset(v,0,sizeof(v))
#define FOR(i,a,b)  for(i=a;i<b;i++)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#ifdef ONLINE_JUDGE
 inline void inp( int &n )
 {
    n=0;
    int ch=getchar_unlocked();int sign=1;
    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

    while(  ch >= '0' && ch <= '9' )
            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n=n*sign;
  }
#else
inline void inp(int &n){
 cin>>n;
}
#endif
string str;
struct node{
 int F[26];

};
vector<node> st;

inline void buildst(int idx,int ss,int se){

  if(ss==se){
    for(int i=0;i<26;i++) st[idx].F[i]=0;
    st[idx].F[str[ss]-'a']=1;
    return ;
  }
  int mid=(ss+se)>>1;
  buildst(2*idx+1,ss,mid);
  buildst(2*idx+2,mid+1,se);
  for(int i=0;i<26;i++) st[idx].F[i]=st[idx*2+1].F[i]+st[idx*2+2].F[i];
}

void update(int idx,int ss,int se,int val,int count){

  if(ss==se){
   st[idx].F[count]=0;
   str[ss]='X';
   return;
  }
  int mid=(ss+se)>>1;
  if(st[2*idx+1].F[count]>=val){
   update(2*idx+1,ss,mid,val,count);
  }else{
   update(2*idx+2,mid+1,se,val-st[2*idx+1].F[count],count);
  }
  for(int i=0;i<26;i++) st[idx].F[i]=st[idx*2+1].F[i]+st[idx*2+2].F[i];
}
int main()
{
   // std::ios_base::sync_with_stdio(false);
    int t;
    t=1;
    while(t--){
     cin>>str;
     int n=str.length();
     int size=(ceil)(log2(n))+1;
     st.resize(1<<size);
     buildst(0,0,n-1);
     int q;
     inp(q);
     int val,count;
     char ch;
     while(q--){
      inp(val);
      cin>>ch;
      count=ch-'a';
      update(0,0,n-1,val,count);
     }

     for(int i=0;i<n;i++){
      if(str[i]!='X')
       cout<<str[i];
     }
     cout<<endl;
    }
    return 0;
}

coding problems