C++14(g++5.4) 解法, 执行用时: 568ms, 内存消耗: 155648K, 提交时间: 2019-09-28 22:05:21

#include <bits/stdc++.h>
  
using namespace std;
typedef long long ll;
const int maxn = 1e6+9;
  
int num;
int dl[maxn],dr[maxn],p[maxn],h[maxn],who[maxn];
ll sum[maxn*40],cnt[maxn*40];
int rt[maxn*40],lson[maxn*40],rson[maxn*40];
int cur;
  
void build(int &now,int l,int r,int L,int val){
    if(!now)now=++cur;
    sum[now]+=1ll*val*h[L];
    cnt[now]+=val;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(L<=mid)build(lson[now],l,mid,L,val);
    else build(rson[now],mid+1,r,L,val);
}
  
int rebuild(int x,int y){
    if(!x||!y)return x+y;
    int now=++cur;
    sum[now]=sum[x]+sum[y];
    cnt[now]=cnt[x]+cnt[y];
    lson[now]=rebuild(lson[x],lson[y]);
    rson[now]=rebuild(rson[x],rson[y]);
    return now;
}
  
ll query(int now,int l,int r,ll k){
    if(l==r){
        return 1ll*h[l]*min(k,cnt[now]);
    }
    int mid=(l+r)>>1;
    if(cnt[lson[now]]>=k)return query(lson[now],l,mid,k);
    else return sum[lson[now]]+query(rson[now],mid+1,r,k-cnt[lson[now]]);
}
  
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&dl[i],&dr[i],&p[i]);
        h[i]=p[i];
    }
    sort(h+1,h+1+n);
    num=unique(h+1,h+1+n)-h-1;
    for(int i=1;i<=n;i++){
        who[i]=lower_bound(h+1,h+1+num,p[i])-h;
    }
    for(int i=1;i<=n;i++){
        build(rt[dl[i]],1,num,who[i],1);
        build(rt[dr[i]+1],1,num,who[i],-1);
    }
    for(int i=1;i<=m;i++){
        rt[i]=rebuild(rt[i-1],rt[i]);
    }
    int x,a,b,c;
    ll ans=1;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&a,&b,&c);
        ll k=1+1ll*(1ll*a*ans%c+b)%c;
        ans=query(rt[x],1,num,k);
        printf("%lld\n",ans);
    }
    return 0;
}

C++ 解法, 执行用时: 376ms, 内存消耗: 121396K, 提交时间: 2021-09-12 13:58:35

#include<bits/stdc++.h>
#define P pair<int,int>
#define ie7a5 10000005
using namespace std;
int n,m;
long long ans;
int s;
int t;
int p;
int a,b,c;
vector<P>v[100005];
struct nodr
{
    int l;
    int r;
    int c;
    long long s;
}A[6400160];
int tot;
int st[100005];
int cg(int k,int s,int l,int r,int x,int y)
{
    A[k]=A[s];
    A[k].c+=y;
    A[k].s+=x*y;
    if(l>=r)
    {
        return k;
    }
    int mid=l+r>>1;
    if(x<=mid)
    {
        A[k].l=cg(tot++,A[s].l,l,mid,x,y);
    }
    else
    {
        A[k].r=cg(tot++,A[s].r,mid+1,r,x,y);
    }
    return k;
}
long long cx(int k,int s,int l,int r,int rk)
{
    if(l>=r)
    {
        return (long long)rk*l;
    }
    int mid=l+r>>1;
    int c=A[A[k].l].c-A[A[s].l].c;
    if(rk<=c)
    {
        return cx(A[k].l,A[s].l,l,mid,rk);
    }
    else
    {
        return cx(A[k].r,A[s].r,mid+1,r,rk-c)+A[A[k].l].s-A[A[s].l].s;
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %lld",&s,&t,&p);
        v[s].push_back(make_pair(p,1));
        v[t+1].push_back(make_pair(p,-1));
    }
    tot=1;
    for(int i=1;i<=100005;i++)
    {
        st[i]=st[i-1];
        for(auto it:v[i])
        {
            st[i]=cg(tot++,st[i],1,ie7a5,it.first,it.second);
        }
    }
    ans=1;
    while(m--)
    {
        scanf("%d %d %d %d",&t,&a,&b,&c);
        p=1+(a*ans+b)%c;
        if(p>=A[st[t]].c-A[st[0]].c)
        {
            ans=A[st[t]].s-A[st[0]].s;
        }
        else
        {
            ans=cx(st[t],st[0],1,ie7a5,p);
        }
        printf("%lld\n",ans);
    }
    return 0;
}