[文章目录]
Description
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000
强制在线，将优先级离散化，然后按照时间建主席树，维护sum和siz，注意到叶子节点需要单独计算sum。内存回收的话由于可能涉及到前面的时间，所以不能回收。空间复杂度n*logn。
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
vector <int> v[N<<1];
int n,m,a[N],c[N],tot;
int getid(int x)
{
int l=1,r=tot+1,mid;
while(l<r)
{
mid=l+r>>1;
if(c[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
ll sum[N*50]; int ls[N*50],rs[N*50],siz[N*50],cnt,root[N];
void update(int l,int r,int z,int &x,int y,int w)
{
x=++cnt; sum[x]=sum[y]+w; siz[x]=siz[y]+((w>0)?1:-1);
if(l==r) return ;
int mid=l+r>>1;
if(z<=mid) rs[x]=rs[y],update(l,mid,z,ls[x],ls[y],w);
else ls[x]=ls[y],update(mid+1,r,z,rs[x],rs[y],w);
}
void build()
{
for(int i=1;i<=m;i++)
{
root[i]=root[i-1];
for(int j=0;j<v[i].size();j++)
update(1,tot,getid(v[i][j]),root[i],root[i],v[i][j]);
for(int j=0;j<v[i+m].size();j++)
update(1,tot,getid(v[i+m][j]),root[i],root[i],-v[i+m][j]);
}
}
ll query(int l,int r,int x,int y)
{
if(!y) return 0;
if(siz[x]<=y) return sum[x];
if(l==r){return 1ll*c[l]*y;}
int mid=l+r>>1;
if(siz[ls[x]]<=y) return sum[ls[x]]+query(mid+1,r,rs[x],y-siz[ls[x]]);
else return query(l,mid,ls[x],y);
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,k,x,y,z;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[i]=z; v[x].push_back(z); v[y+m+1].push_back(z);
}
sort(a+1,a+n+1); tot=1; c[1]=a[1];
for(i=2;i<=n;i++) if(a[i]!=a[i-1]) c[++tot]=a[i];
build();
ll pre=1,ai,bi,ci;
while(m--)
{
scanf("%d%lld%lld%lld",&x,&ai,&bi,&ci);
ai=(ai%ci*(pre%ci)%ci+bi)%ci+1;
printf("%lld\n",pre=query(1,tot,root[x],ai));
}
return 0;
}