In this HackerEarth Akash and too many assignments problem Akash is an assignment-o-holic kind of a person, he's crazy about solving assignments. So, to test his skills, his professor has given him an assignment to solve.

In this assignment, Akash is given a String S of length N consisting of lowercase letters (a - z) only. And he has to take care of 2 types of operations.

Operation type #1: [ 0 index c ] - 0 denotes the operation type #1. This operation expects you to change the character at index index to character c i.e., String[index] = c.

Operation type #2: [ 1 LeftLimit RightLimit K ] - 1 denotes the operation type #2. It expects you to print the lexicographically Kth smallest character in the sub-string of String S starting from LeftLimit to RightLimit, inclusively.

Help Akash out in solving this tricky assignment!


HackerEarth Akash and too many assignments problem solution


HackerEarth Akash and too many assignments problem solution.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const ll MOD = 1000000007;
const int MAX = 1000005;

int tree[MAX][30];

int read(int idx1, int idx2)
{
int sum = 0;
while(idx1 > 0)
{
sum += tree[idx1][idx2];
idx1 -= (idx1 & -idx1);
}
return sum;
}

void update(int idx1, int idx2, int val, int n)
{
while(idx1 <= n)
{
tree[idx1][idx2] += val;
idx1 += (idx1 & -idx1);
}
}


int main()
{
int n, q, l, r, idx, k, c, ans;
char y;
string s;
cin >> n >> q >> s;

for(int i = 0;i < n;++i)
update(i + 1, s[i] - 'a', 1, n);

for(int i = 0;i < q;++i)
{
scanf("%d", &c);
if(c)
{
scanf("%d %d %d", &l, &r, &k);
ans = 0;
int j;
for(j = 0;j < 26;++j)
{
ans += read(r, j) - read(l - 1, j);
if(ans >= k)
break;
}
if(ans >= k)
printf("%c\n", j + 'a');
else printf("Out of range\n");
}
else
{
scanf("%d %c", &idx, &y);
update(idx, s[idx-1] - 'a', -1, n);
s[idx-1] = y;
update(idx, s[idx-1] - 'a', 1, n);
}
}
return 0;
}

Second solution

#include <bits/stdc++.h>
#define MAX 1000004
using namespace std;

int tree[MAX][32];

void update(int idx1, int idx2, int val)
{
while ( idx1 <= MAX-2 ) {
tree[idx1][idx2] += val;
idx1 += (idx1 & (-idx1));
}
return;
}

int query(int idx1, int idx2)
{
int ans = 0;
while ( idx1 > 0 ) {
ans += tree[idx1][idx2];
idx1 -= (idx1 & (-idx1));
}
return ans;
}

int main()
{
int n,q,type,x,l,r,k;
char y;
string s;
cin >> n >> q;
cin >> s;
for ( int i = 0; i < n; i++ ) update(i+1,s[i]-96,1);

while ( q-- ) {
cin >> type;
if ( type == 0 ) {
cin >> x >> y;
update(x,s[x-1]-96,-1);
s[x-1] = y;
update(x,s[x-1]-96,1);
}
else {
cin >> l >> r >> k;
int cnt = 0;
for ( int i = 1; i <= 26; i++ ) {
cnt += query(r,i) - query(l-1,i);
if ( cnt >= k ) {
cout << (char)(i+96) << endl;
goto p1;
}
}
cout << "Out of range" << endl;
p1: { }
}
}
return 0;
}