最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

链接🔗

「CQOI 2015」 任务查询系统

题解

把区间开始结束时间理解成差分，然后根据时间排序后在主席树上插入即可

代码

#include<cstdio>
#include<algorithm>
#include <cstring>
using namespace std;
const int maxd = 2e5+10;
int rt[maxd<<5],ls[maxd<<5],rs[maxd<<5],size[maxd<<5];
long long sum[maxd<<5];
int x,a,b,c,tot;
void insert(int &rt,int last,int l,int r,int x)
{
    rt = ++tot; ls[rt] = ls[last],rs[rt] = rs[last];
    size[rt] = size[last]+((x>0)?1:-1);
    sum[rt] = (long long)sum[last] + x;
    //printf("%d %d %d %d %lld\n",rt,l,r,size[rt],sum[rt]);
    if(l==r) return ;
    int mid = (l+r)>>1;
    if(abs(x)<=mid) insert(ls[rt],ls[last],l,mid,x);
    else insert(rs[rt],rs[last],mid+1,r,x);
    //printf("%d %d %d %d %d\n",size[rt],size[last],l,r,x);
}
long long query(int y,int l,int r,int v)
{
    //printf("%d %d %d %d %d %d\n",y,l,r,size[y],size[ls[y]],size[rs[y]]);
    if(l==r)return min(v,size[y])*l;
    int mid = (l+r)>>1;
    if(v <= size[ls[y]]) return query(ls[y],l,mid,v);
    else return sum[ls[y]] + query(rs[y],mid+1,r,v-size[ls[y]]);
}
int eid;
struct node
{
    int pos,v;
}arr[maxd];
bool cmp(const node &x,const node &y)
{
    return x.pos < y.pos;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int n,m,k=0;scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        arr[++eid].pos = a, arr[eid].v = c;
        arr[++eid].pos = b+1,arr[eid].v = -c;
        k = max(k,b+1);
    }
    sort(arr+1,arr+1+eid,cmp);
    int id=1;arr[eid+1].pos = 0;
    for(int i=1;i<=k;i++)
    {
        if(arr[id].pos!=i) rt[i] = rt[i-1];
        else
        {
            //printf("%d %d %d\n",i,i-1,arr[id].v);
            insert(rt[i],rt[i-1],1,10000000,arr[id++].v);
            while(arr[id].pos == i)
            {
                //printf("%d %d %d\n",i,i,arr[id].v);
                insert(rt[i],rt[i],1,10000000,arr[id++].v);
            }
        }
        //printf("%d %d %d %d\n",i,rt[i],size[ls[rt[i]]],size[rs[rt[i]]]);
    }
    long long ans = 1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&x,&a,&b,&c);
        long long k = 1+(a*ans%c+b)%c;
        //printf("%d %lld\n",x,k);
        ans = query(rt[x],1,10000000,k);
        printf("%lld\n",ans);
    }
    return 0;
}