HI,I TRIED TO SOLVE KQUERY USING PERSISTENT SEGMENT TREE BUT I DONT KNOW WHY IT VERDICTS TLE PLEASE CHECK AND POINT OUT.
CODE
#include<bits/stdc++.h>
using namespace std;
typedef long ll;
#define f(i,a,b) for(i=a;i<b;i++)
#define g(i,a,b) for(i=a;i>=b;i–)
struct node
{
ll count;
node* left,right;
};
node build(ll s,ll e)
{
if(s==e)
{
node* p=new node;
p->count=0;
p->left=p->right=NULL;
return p;
}
ll mid=(s+e)/2;
node* p=new node;
p->left=build(s,mid);
p->right=build(mid+1,e);
p->count=p->left->count+p->right->count;
return p;
}
node* update(node* root,ll s,ll e,ll indx)
{
if(s==e)
{
node* p=new node;
p->count=1+root->count;
p->left=p->right=NULL;
return p;
}
node* p=new node;
ll mid=(s+e)/2;
if(indx<=mid)
{
p->left=update(root->left,s,mid,indx);
p->right=root->right;
}
else
{
p->right=update(root->right,mid+1,e,indx);
p->left=root->left;
}
p->count=p->left->count+p->right->count;
return p;
}
ll querry(node* root,ll s,ll e,ll ql,ll qh)
{
if(s>e)
return 0;
if(s>qh||e<ql)
return 0;
if(s>=ql&&e<=qh)
return root->count;
ll mid=(s+e)/2;
ll u=querry(root->left,s,mid,ql,qh);
ll v=querry(root->right,mid+1,e,ql,qh);
return u+v;
}
int main()
{
ll n,i,L,R,q,x;
scanf("%lld",&n);
ll a[n];
map<ll,ll>mp;
ll b[n];
f(i,0,n){
scanf("%lld",&a[i]);
b[i]=a[i];
mp[a[i]];}
ll indx=0;
sort(b,b+n);
for(auto it=mp.begin();it!=mp.end();it++)
mp[it->first]=indx++;
node* root=build(0,n-1);
node* r[n];
node* cur;
for(i=0;i<n;i++)
{
if(i==0)
cur=root;
else
cur=r[i-1];
r[i]=update(cur,0,n-1,mp[a[i]]);
}
scanf("%lld",&q);
ll kk=*max_element(a,a+n);
while(q–)
{
scanf("%lld%lld%lld",&L,&R,&x);
L–;
R–;
if(x>=kk)
{
printf(“0\n”);
continue;
}
ll dd=upper_bound(b,b+n,x)-b;
if(dd==n)
{
printf(“0\n”);
continue;
}
ll pp=b[dd];
ll u1=querry(r[R],0,n-1,mp[pp],n-1);
ll v1=0;
if(L)
v1=querry(r[L-1],0,n-1,mp[pp],n-1);
printf("%lld\n",u1-v1);
}
}
