[cqoi2015] task query system

The interval contains points before k Big problem

link ：[P3168 CQOI2015] Task query system - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given multiple intervals , Each interval has a weight $q_i$. Ask the passing point many times x Before all sections of k Sum of small weights .

Answer key ： Think of the interval as two parentheses （ Left parenthesis , Right bracket ）, Suppose that the problem is that the interval passes from x Before the end k Small weight sum , In fact, you can maintain the right parenthesis , Build a chairman tree for the time axis according to the sequence length , Insert the corresponding prefix according to the position of the right bracket , Create a tree every time you inherit the previous time point or the current time point . Check whether it is greater than or equal to x The point of only needs the last tree minus the x-1 Just one tree . But only after x The interval of , So there are some d The left parenthesis is greater than x The range of is also included . Then maintain a left parenthesized chairman tree , Inquire about x It can be used to look up the last chairman tree in the right bracket and the second chairman tree in the right bracket x-1 The subtraction of the chairman tree , Also subtract the left parenthesis $x(1\le x\le n)$ To n The left parenthesis of the chairman tree , This will eliminate those greater than x The influence of the interval .

Note that the update function inherits itself , Cannot return in advance , Keep the old point information first . When querying, pay attention to the pre query k Hour last $l=r$ The number of returned values may be greater than the number currently required , So you have to subtract the extra number . At the same time k Will be greater than the current number , Taking the maximum $\max (0,num-k)$.

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;

ll b0[maxn],n,m,x,a,b,c,k,ans=1,mx;
int ls[2][maxn<<5],rs[2][maxn<<5],sum[2][maxn<<5],rt[2][maxn],now[2];
ll t[2][maxn<<5];
struct node{
    
	int s,e,p;
}q[maxn];
vector<int>s[maxn],e[maxn];

void update(int o,int u,int&v,int l,int r,int pos)
{
    
	int p=++now[o];
	ls[o][p]=ls[o][u],rs[o][p]=rs[o][u];
	sum[o][p]=sum[o][u]+1,t[o][p]=t[o][u]+b0[pos];
	if(l<r)
	{
    
		int mid=l+r>>1;
		if(pos<=mid)update(o,ls[o][u],ls[o][p],l,mid,pos);
		else update(o,rs[o][u],rs[o][p],mid+1,r,pos);
	}
	v=p; return;
}

ll query(int u1,int v1,int u2,int v2,int l,int r,int k)
{
    
	int num=sum[1][v2]-sum[1][u2]-sum[0][v1]+sum[0][u1];
	if(l==r)return t[1][v2]-t[1][u2]-t[0][v1]+t[0][u1]-max(0,num-k)*b0[l];
	int mid=l+r>>1; num=sum[1][ls[1][v2]]-sum[1][ls[1][u2]]-sum[0][ls[0][v1]]+sum[0][ls[0][u1]];
	if(k<=num)return query(ls[0][u1],ls[0][v1],ls[1][u2],ls[1][v2],l,mid,k);
	else return t[1][ls[1][v2]]-t[1][ls[1][u2]]-t[0][ls[0][v1]]+t[0][ls[0][u1]]+query(rs[0][u1],rs[0][v1],rs[1][u2],rs[1][v2],mid+1,r,k-num);
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
    
		cin>>q[i].s>>q[i].e>>q[i].p,b0[i]=q[i].p;
		s[q[i].s].push_back(i);
		e[q[i].e].push_back(i);  
	}
	sort(b0+1,b0+1+m),mx=unique(b0+1,b0+1+m)-b0-1;
	for(int i=1;i<=m;i++)
	{
    
		q[i].p=lower_bound(b0+1,b0+1+mx,q[i].p)-b0;
	}
	for(int i=1;i<=n;i++)
	{
    
		if(s[i].size())update(0,rt[0][i-1],rt[0][i],1,mx,q[s[i][0]].p);
		else rt[0][i]=rt[0][i-1];
		for(int j=1;j<s[i].size();j++)
		{
    
			update(0,rt[0][i],rt[0][i],1,mx,q[s[i][j]].p);
		}
		if(e[i].size())update(1,rt[1][i-1],rt[1][i],1,mx,q[e[i][0]].p);
		else rt[1][i]=rt[1][i-1];
		for(int j=1;j<e[i].size();j++)
		{
    
			update(1,rt[1][i],rt[1][i],1,mx,q[e[i][j]].p);
		}
	}
	for(int i=1;i<=n;i++)
	{
    
		cin>>x>>a>>b>>c;
		k=1+(a*ans+b)%c; 
		ans=query(rt[0][x],rt[0][n],rt[1][x-1],rt[1][n],1,mx,k);
		cout<<ans<<"\n";
	}
	return 0;
}