# BZOJ 3932 task query system

Chairman tree question two....
I'm a real dish.
Take a look, emmmmm
K small before dynamic query
It's obvious to use the chairman tree.
How to achieve it?
Time is the subscript and priority is the interval. For tasks existing in an interval [l,r], the number of occurrences at L is increased by 1, and the number of occurrences at r+1 is decreased by 1. These events are regarded as events, and all occurrences at time i are added to the line tree of i. Then you can count the answers on T[x].
The time given to us is not necessarily the endpoint, so we need to migrate the input time.
Query method emmmmm
Two.

```#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define ls l,mid
#define rs mid+1,r
#define il inline
#define ll long long
using namespace std;
const ll maxm=300050;
ll rson[maxm<<5],lson[maxm<<5],size[maxm<<5],sum[maxm<<5];
ll root[maxm];
ll tot,max_w=-1;
ll to[maxm];
struct node{
ll poi,val;
};
node e[maxm];
ll build(ll l,ll r)
{
ll rt=++tot;
size[rt]=sum[rt]=0;
if(l<r)
{
ll mid=(l+r)>>1;
lson[rt]=build(ls);
rson[rt]=build(rs);
}
return rt;
}
ll updata(ll pre,ll l,ll r,ll val)
{
ll rt=++tot;
lson[rt]=lson[pre],rson[rt]=rson[pre];
if(val>0) size[rt]=size[pre]+1;
else size[rt]=size[pre]-1;
sum[rt]=sum[pre]+val;
if(l<r)
{
ll mid=(l+r)>>1;
if(abs(val)<=mid) lson[rt]=updata(lson[pre],ls,val);
else rson[rt]=updata(rson[pre],rs,val);
}
return rt;
}
bool comp(node x,node y)
{
return x.poi<y.poi;
}
il ll get_ans(ll time,ll kth)
{
ll x=root[time],l=1,r=max_w,ans=0;
if(size[x]<=kth) return sum[x];
while(l<r)
{
ll mid=(l+r)>>1;
if(size[lson[x]]>=kth) r=mid,x=lson[x];
else
{
l=mid+1;
kth-=size[lson[x]];
ans+=sum[lson[x]];
x=rson[x];
}
}
if(kth) ans+=(1ll*l*kth);
return ans;
}
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll cnt=0;
for(ll i=1,t,s,p;i<=n;i++)
{
scanf("%lld%lld%lld",&t,&s,&p);
e[++cnt].poi=t,e[cnt].val=p;
e[++cnt].poi=s+1,e[cnt].val=-p;
max_w=max(max_w,p);
}
//root[0]=build(1,max_w);
sort(e+1,e+cnt+1,comp);
for(ll i=1;i<=cnt;i++)
root[i]=updata(root[i-1],1,max_w,e[i].val);
for(ll i=cnt;i>=1;i--)
if(e[i].poi!=e[i+1].poi) to[e[i].poi]=i;
for(ll i=1;i<=m;i++)
if(!to[i]) to[i]=to[i-1];
ll pre=1;
for(ll i=1;i<=m;i++)
{
ll x,a,b,c;
scanf("%lld%lld%lld%lld",&x,&a,&b,&c);
ll k=(a*pre+b)%c+1;
pre=get_ans(to[x],k);
printf("%lld\n",pre);
}

return 0;
} ```

Added by freelancer on Sat, 02 May 2020 22:04:54 +0300