题目描述

Description

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

Input

输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格
分开的正整数Si、Ei和Pi(Si≤Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，
描述一次查询。查询的参数Ki需要由公式 Ki=1+(A*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，
对于第一次查询，Pre=1。

Output

输出共n行，每行一个整数，表示查询结果。

Sample Input

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

Sample Output

2
8
11

对于100%的数据，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi为1到n的一个排列

题目分析

差分+主席树
按照时间顺序建造主席树 对于[S,E]的任务 在S时间主席树+1 （E+1）时间主席树-1
拿vector存一下就好了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int val[100100];
vector<int>b[100100];
struct your
{
    int lson,rson;
    int size;
    long long sum;
}a[10000010];
int root[100100],cnt;
void update(int x,int &y,int c,int l,int r)
{   
    y=++cnt;
    a[y]=a[x];
    a[y].sum=(long long) a[y].sum+c; 
    a[y].size+= (c>=0)?1:-1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(abs(c)<=mid) update(a[x].lson,a[y].lson,c,l,mid);
    else update(a[x].rson,a[y].rson,c,mid+1,r);
}
long long ask(int l,int r,int c,int x)
{
    if(!x) return 0;
    if(a[x].size<=c)
        return a[x].sum;
    if(l==r) return (long long) c*l;
    int mid=(l+r)>>1;
    if(c<=a[a[x].lson].size) return ask(l,mid,c,a[x].lson);
    else return a[a[x].lson].sum+ask(mid+1,r,c-a[a[x].lson].size,a[x].rson);
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int x,y,c,i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        b[x].push_back(c);
        b[y+1].push_back(-c);
    }
    for(int i=1;i<=m;i++)
    {
        root[i]=root[i-1];
        for(int j=0;j<b[i].size();j++)
            update(root[i],root[i],b[i][j],1,1000000000);
    }
    long long ans=1;
    for(int x,ai,bi,ci,i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x,&ai,&bi,&ci);
        int ki=1+(ai%ci*ans+bi)%ci;
        ans=ask(1,1000000000,ki,root[x]);
        printf("%lld\n",ans);
    }
    return 0;
}