#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll key,prio,size;
node* left,right;
};
struct vtx
{
node root;
}seg[2000005];
node* create(ll x)
{
node* p=new node;
p->key=x;
p->prio=rand();
p->size=1;
p->left=p->right=NULL;
return p;
}
ll nsize(node* root)
{
if(root)
return root->size;
return 0;
}
void usize(node* root)
{
root->size=1+nsize(root->left)+nsize(root->right);
}
pair<node*,node*> split(node* root,ll x)
{
if(root==NULL)
return make_pair(root,root);
if(root->key<x)
{
pair<node*,node*>p=split(root->right,x);
root->right=p.first;
usize(root);
return make_pair(root,p.second);
}
pair<node*,node*>p=split(root->left,x);
root->left=p.second;
usize(root);
return make_pair(p.first,root);
}
node* merge(node* l,node* r)
{
if(!l||!r)
return l?l:r;
if(l->prioprio)
{
l->right=merge(l->right,r);
usize(l);
return l;
}
r->left=merge(l,r->left);
usize®;
return r;
}
node* insert(node* root,ll x)
{
node* tmp=create(x);
pair<node*,node*>p=split(root,x);
node* p1=merge(p.first,tmp);
node* p2=merge(p1,p.second);
return p2;
}
node* erase(node* root,ll x)
{
if(!root)
return root;
pair<node*,node*>p1=split(root,x);
pair<node*,node*>p2=split(p1.second,x+1);
if(p2.first&&p2.first->size==1&&p2.first->key==x)
delete p2.first;
node* p=merge(p1.first,p2.second);
return p;
}
pair<node*,ll> count(node* root,ll k)
{
pair<node*,node*>p=split(root,k);
ll u=nsize(p.second);
node* p1=merge(p.first,p.second);
return make_pair(p1,u);
}
void build(ll s,ll e,ll p,ll indx,ll val)
{
if(s==e)
{
seg[p].root=insert(seg[p].root,val);
return;
}
ll mid=(s+e)/2;
if(indx<=mid)
{
build(s,mid,2p+1,indx,val);
seg[p].root=insert(seg[p].root,val);
}
else
{
build(mid+1,e,2p+2,indx,val);
seg[p].root=insert(seg[p].root,val);
}
}
void update1(ll s,ll e,ll p,ll indx,ll val)
{
if(s==e)
{
seg[p].root=erase(seg[p].root,val);
return;
}
ll mid=(s+e)/2;
if(indx<=mid)
{
update1(s,mid,2p+1,indx,val);
seg[p].root=erase(seg[p].root,val);
}
else
{
update1(mid+1,e,2p+2,indx,val);
seg[p].root=erase(seg[p].root,val);
}
}
ll querry(ll s,ll e,ll p,ll ql,ll qh,ll val)
{
if(s>qh||e<ql)
return 0;
if(s>=ql&&e<=qh)
{
pair<node*,ll>p1=count(seg[p].root,val);
seg[p].root=p1.first;
return p1.second;
}
ll mid=(s+e)/2;
ll u=querry(s,mid,2p+1,ql,qh,val);
ll v=querry(mid+1,e,2p+2,ql,qh,val);
return u+v;
}
int main()
{
ll n,i,l,r,x,q,qt;
scanf("%lld",&n);
for(i=0;i<2000005;i++)
seg[i].root=NULL;
ll a[n];
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
build(0,n-1,0,i,a[i]);
}
scanf("%lld",&q);
while(q–)
{
scanf("%lld",&qt);
if(qt==0)
{
scanf("%lld%lld%lld",&l,&r,&x);
l–;
r–;
ll ans=querry(0,n-1,0,l,r,x);
printf("%lld\n",ans);
}
else
{
scanf("%lld%lld",&l,&x);
l–;
update1(0,n-1,0,l,a[l]);
a[l]=x;
build(0,n-1,0,l,a[l]);
}
}
}
why tle in give away please see…
1 Like
Hey, could you include the problem link in your question? I don’t understand your source.
Also, please use the Code formatting or a paster for your code, it’s barely readable
1 Like
okk sorry for inconvenience
here is link to problem SPOJ.com - Problem GIVEAWAY
and her is link to my code FeEtTv - Online C++ Compiler & Debugging Tool - Ideone.com
i used treaps at every node of segment tree and this is how i responded to each query
type 0 l r k queried segment tree in range [l,r]
type 1 l k deleted element k from root to leaf from segment tree nodes coming in path of leaf index l and inserted the new updated element k similarly in all nodes in paths till leaf index l rest can be understood …