Problem Link : https://www.hackerrank.com/contests/womens-codesprint-4/challenges/lexicographically-smaller-or-equal-strings
Solution Idea:
-
This problem is an example of basic merge sort tree problem. Merge Sort tree is a segment tree in which every node contains a vector. In this problem we can store string in every leaf node of segment tree as the size of the string is <=15. And while merging two leaf node we will merge them in sorted order. Now as the vectors of every node in the segment tree is sorted we can apply binary search on segment tree node to get how many string is lexicographically smaller than the given string.
So after building merge sort tree we can easily answer every query using binary search.
If you want to learn some wonderful application of segment tree or merge sort tree you can see this article.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair <int,int>
#define pll pair <long long,long long>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define db double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define sqr(x) (x)*(x)
#define D(x) cerr<<#x " = "<<(x)<<endl
#define VI vector <int>
#define DBG pf("Hi\n")
#define MOD 1000000007
#define CIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a) (int)a.size()
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>=b;i--)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define LINE_PRINT_CASE printf("Case %d:\n",z)
#define CASE_PRINT cout<<"Case "<<z<<": "
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define infinity (1<<28)
#define ull unsigned long long
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
#define mx 100005
vector<string>tree[3*mx],v;
void init(int n, int b, int e)
{
if(b==e)
{
tree[n].pb(v[b]);
return;
}
int l=n*2,r=l+1,mid=(b+e)/2;
init(l,b,mid);
init(r,mid+1,e);
merge(all(tree[l]),all(tree[r]),back_inserter(tree[n]));
// cout<<n<<" "<<b<<" "<<e<<endl;
// for(int i=0;i<SZ(tree[n]);i++)
// cout<<tree[n][i]<<endl;
// cout<<"-----------------------------"<<endl;
}
int query(int n, int b, int e, int i, int j, string &str)
{
if(b>j || e<i) return 0;
if(b>=i && e<=j)
{
// int x=upper_bound(all(tree[n]),str)-tree[n].begin();
// int y=lower_bound(all(tree[n]),str)-tree[n].begin();
// int z=x-y;
// return z;
return upper_bound(all(tree[n]),str)-tree[n].begin();
}
int l=n*2,r=l+1,mid=(b+e)/2;
int p=query(l,b,mid,i,j,str);
int q=query(r,mid+1,e,i,j,str);
return p+q;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
sf(n);
v.pb("");
char sss[30];
for(int i=0;i<n;i++)
{
scanf(" %s",sss);
v.pb(string(sss));
}
init(1,1,n);
int q;
sf(q);
while(q--)
{
int a,b;
sff(a,b);
scanf(" %s",sss);
string str=string(sss);
// cout<<str<<endl;
int ans=query(1,1,n,a,b,str);
printf("%d\n",ans);
}
return 0;
}