PROBLEM LINK:
Author: Siddharth
Tester: Aneesh D H , Suryansh Kumar
Editorialist: Siddharth
DIFFICULTY:
EASY
PREREQUISITES:
Trees, Ordered-Set
PROBLEM:
Given a string of lowercase alphabets we have to process 2 types of queries:
TYPE 1: Update the character at index i
TYPE 2: Print the Kth smallest alphabet in the range [L, R]
EXPLANATION:
Maintain a BIT or Segment tree for each alphabet.
- For query of TYPE 1: We can just update the trees and replace the ith character of the string.
- Now for query of TYPE 2: We will just calculate the number of occurrence of each alphabet in the given range [L, R] and search for the Kth smallest alphabet.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
string ss;
int n, q;
vector<int> FTree[30];
int getnext(int node);
int getP(int node);
void updateTree(int which, int node, int val);
void init();
void hq1(int index, int prev, int newv);
int sum(int idx,int where);
char hq2(int l,int r,int k);
int getnext(int node)
{
return node + (node & -node);
}
int getP(int node)
{
return node - (node & -node);
}
void updateTree(int which, int node, int val)
{
if (node > n)
{
return;
}
FTree[which][node] += val;
updateTree(which, getnext(node), val);
}
void init()
{
for (int i = 0; i < 30; i++)
{
FTree[i].assign(n + 1, 0);
}
for (int i = 0; i < ss.length(); i++)
{
int where = ss.at(i) - 'a';
updateTree(where, i + 1, 1);
}
}
void hq1(int index, int prev, int newv)
{
updateTree(prev,index,-1);
updateTree(newv,index,1);
}
int sum(int idx,int where)
{
if(idx<=0)
{
return 0;
}
return FTree[where][idx]+sum(getP(idx),where);
}
char hq2(int l,int r,int k)
{
for(char c='a';c<='z';c++)
{
int i = c-'a';
k-=(sum(r,i)-sum(l-1,i));
if(k<=0)
{
return c;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--)
{
cin >> n >> q >> ss;
init();
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int idx, newv, prev;
char ch;
cin >> idx >> ch;
prev = ss.at(idx-1) - 'a';
newv = ch - 'a';
ss.at(idx-1)=ch;
hq1(idx, prev, newv);
}
else
{
int l, r, k;
cin >> l >> r >> k;
cout << hq2(l,r,k)<< '\n';
}
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
struct BitTree{
vector<vector<int>> bit;
int n;
string s;
BitTree(string &S, int N){
n = N;
s = '#' + S;
bit.assign(26 , vector<int>(n+5,0));
for(int i=1;i<=n;i++){
up(s[i],i,1);
}
}
void up(char c,int id, int val){
while(id<=n) bit[c - 'a'][id] += val , id += id & -id;
}
int sum(char c,int id){
int ans = 0;
while(id>0) ans+= bit[c - 'a'][id] , id -= id & -id;
return ans;
}
void update(int id, char c){
up(s[id],id,-1);
up(c,id,1);
s[id] = c;
}
char query(int l, int r, int k){
char ans='a';
for(char c='a';c<='z';c++){
int temp = sum(c , r) - sum(c , l-1);
if(temp>=k){
ans = c;
break;
}
else k -= temp;
}
return ans;
}
};
void _sol(){
int n,q; cin >> n >> q;
string s; cin >> s;
BitTree Tree(s,n);
while(q--){
int type; cin >> type;
if(type==1){
int id; cin >> id;
char c; cin >> c;
Tree.update(id,c);
}
else{
int l,r,k; cin >> l >> r >> k;
cout << Tree.query(l,r,k) << "\n";
}
}
return;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1; cin >> t;
while(t--) _sol();
}
