题目链接

题面：

题解：
将 ( s , e , p) 拆分为（s，p）和（e+1，-p）
按照第一键值升序排序，对于每一个（t，p）的二元组，在第 t 棵主席树上的abs（p）位置加上p。
查询时，在第 xi 棵主席树上查询前 ki 个数的和。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
#define y1 yy
using namespace std;
const int maxn=100100;
pair<int,int>p[maxn<<1];
int b[maxn],root[maxn],cnt;
struct node
{
    int lc,rc;
    int si;
    ll sum;
}t[maxn*44];

int _insert(int now,int pos,int l,int r)
{
    int p=++cnt;
    t[p]=t[now];
    if(l==r)
    {
        t[p].si+=pos>0?1:-1;
        t[p].sum=t[p].sum+b[abs(pos)]*(pos>0?1:-1);
        return p;
    }
    int mid=(l+r)>>1;
    if(abs(pos)<=mid) t[p].lc=_insert(t[now].lc,pos,l,mid);
    else t[p].rc=_insert(t[now].rc,pos,mid+1,r);
    t[p].si=t[t[p].lc].si+t[t[p].rc].si;
    t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
    return p;
}

ll ask(int p,int k,int l,int r)
{
    if(l==r) return t[p].sum/t[p].si*k;//注意可能不会全取
    int mid=(l+r)>>1;
    if(t[t[p].lc].si>=k) return ask(t[p].lc,k,l,mid);
    else return t[t[p].lc].sum+ask(t[p].rc,k-t[t[p].lc].si,mid+1,r);
}

int main(void)
{
    int m,n;
    int x,y,z;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        p[i*2-1].first=x,p[i*2-1].second=z;
        p[i*2].first=++y,p[i*2].second=-z;
        b[i]=z;
    }
    sort(b+1,b+m+1);
    int cm=unique(b+1,b+m+1)-(b+1);
    for(int i=1;i<=m;i++)
    {
        p[i*2-1].second=lower_bound(b+1,b+cm+1,p[i*2-1].second)-b;
        p[i*2].second=-p[i*2-1].second;
    }
    sort(p+1,p+m*2+1);
    int rt=0;
    for(int i=1;i<=m*2;i++)
    {
        while(rt<p[i].first)
            root[rt+1]=root[rt],rt++;
        root[rt]=_insert(root[rt],p[i].second,1,cm);
    }
    ll pre=1;
    int xi,ai,bi,ci;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&xi,&ai,&bi,&ci);
        int ki=1ll+((ll)ai*pre+(ll)bi)%ci;
        if(t[root[xi]].si<=ki) printf("%lld\n",pre=t[root[xi]].sum);
        else printf("%lld\n",pre=ask(root[xi],ki,1,cm));
    }
    return 0;

}