P3168 [CQOI2015]任务查询系统

先考虑一下暴力怎么打，对于每个时间，我们开一个 $vector$ ，对于每一个任务，我们在 $[S_i,E_i]$ 的 $vector$ 里面都 $pushback$ 一遍 $P_i$ 即可。

但是这样的暴力是愚蠢的暴力，考虑优化，我们在 $S_i$ 和 $E_i+1$ 的位置分别打上加入和删除标记，到某一个时间，我们先复制上一个时间的 $vector$ ，然后按照标记加入和删除 $P_i$ ，事实上，这起了差分的作用。

这样会有什么不好的地方，首先，每次复制上一次的 $vector$ ，绝对会爆空间，其次，查询不好搞。

如何减少空间，我们使用~~jzm~~主席树，每次加入或者删除 $P_i$ 最多只需要 $\log n$ 的空间，在主席树上面查询也比较好搞，只要在每个节点维护任务的总数，任务的优先级之和即可。

如果你想偷懒（像我一样），预处理的时候不用一个一个合并过去，而是每个节点先插入 $P_i$ ，然后一个一个线段树合并过去，代码量能减少不少。

#include <bits/stdc++.h>
#define MAXN 100005
#define LOG 105
using namespace std;
int S[MAXN],E[MAXN],P[MAXN];
int org[MAXN];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int rt[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int cnt;//任务的总数
        int val;//任务的优先级之和
    }tree[MAXN*LOG];
    int tot;
    #define lc tree[i].l
    #define rc tree[i].r
    inline void pushup(int i,int x,int y){
        tree[i].cnt=tree[x].cnt+tree[y].cnt;
        tree[i].val=tree[x].val+tree[y].val;
    }
    void Update(int &i,int l,int r,int pos,int val){
        if (!i) i=++tot;
        if (l==r){
            tree[i].cnt+=val;
            tree[i].val+=val*P[l];
            return ;
        }
        int mid=(l+r)>>1;
        if (pos<=mid) Update(lc,l,mid,pos,val);
        else Update(rc,mid+1,r,pos,val);
        pushup(i,lc,rc);
    }
    int Query(int i,int l,int r,int k){
        if (l==r){
            return P[l]*min(k,tree[i].cnt);//特别注意，因为查询的可能大于任务总数
        }
        int mid=(l+r)>>1;
        if (tree[lc].cnt>=k) return Query(lc,l,mid,k);
        else return tree[lc].val+Query(rc,mid+1,r,k-tree[lc].cnt);
    }
    void Merge(int &x,int y){//y->x
        if (!x||!y){
            x=x+y;
            return ;
        }
        pushup(x,x,y);
        Merge(tree[x].l,tree[y].l);
        Merge(tree[x].r,tree[y].r);
    }
}
using namespace SegmentTree;
int main(){
    int m=read(),n=read();
    for (register int i=1;i<=m;++i){
        S[i]=read(),E[i]=read(),org[i]=P[i]=read();
    }
    sort(P+1,P+1+m);
    int M=unique(P+1,P+1+m)-P-1;
    for (register int i=1;i<=m;++i){
        int rk=lower_bound(P+1,P+1+M,org[i])-P;
        Update(rt[S[i]],1,M,rk,1);
        Update(rt[E[i]+1],1,M,rk,-1);
    }
    for (register int i=1;i<=n;++i){
        Merge(rt[i],rt[i-1]);
    }
    int pre=1;
    for (register int i=1;i<=n;++i){
        int x=read(),a=read(),b=read(),c=read();
        int k=(1+((long long)a*pre+b)%c);
        printf("%d\n",pre=Query(rt[x],1,M,k));
    }
}