【主席树】任务查询系统

线段树

传送门：BZOJ3932

诶最近智力有点低下，好几发才过。

做法：建立一颗可持久化的权值线段树，以优先级为权值，由于是在时间上区间修改，因此可以运用差分的思想，把在时间$[S_i,E_i]$加上优先级$P_i$改为 在$S_i$加$P_i$ 和 在$E_i+1$减$P_i$ 两个子操作，然后在改时间时求下前缀和即可。

注意：中间空白的时间要继承上一个（相当于前缀和）

看代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
int n,m,l,r,s,tot,tot2,xb,t;
int root[800030],num[8000030],ls[8000030],rs[8000030];
LL x,y,z,k,ans,sum[8000030];
struct task{int t,num,sum,id;}a[800030];
bool cmp1(task x,task y){return x.sum<y.sum;}
bool cmp2(task x,task y){return x.t<y.t;}
void build(int &cur,int l,int r){
    cur=++tot2;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls[cur],l,mid); build(rs[cur],mid+1,r);
}
LL query(int cur,int l,int r,LL k){
    if (k<=0) return 0;
    if (k>=num[cur]) return sum[cur];
    if (l==r) return (LL)sum[cur]/num[cur]*k;
    int mid=(l+r)>>1;
    return query(ls[cur],l,mid,k)+query(rs[cur],mid+1,r,k-num[ls[cur]]);
}
void modify(int &cur,int l,int r,int i){
    sum[++tot2]=sum[cur]+(LL)a[i].sum*a[i].num; num[tot2]=num[cur]+a[i].num;
    ls[tot2]=ls[cur]; rs[tot2]=rs[cur]; cur=tot2;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (a[i].id<=mid) modify(ls[cur],l,mid,i);
    if (a[i].id>mid) modify(rs[cur],mid+1,r,i);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&l,&r,&s);
        a[++tot]=(task){l,1,s,0};
        if (r!=n) a[++tot]=(task){r+1,-1,s,0};
    }
    
    sort(a+1,a+tot+1,cmp1);
    int xb=0;
    for (int i=1;i<=tot;i++){a[i].id=(a[i].sum!=a[i-1].sum)?++xb:xb;}
    sort(a+1,a+tot+1,cmp2);
    build(root[0],1,xb); a[tot+1].t=m;
    for (int i=1;i<=a[1].t && i<=m;i++) root[i]=root[0];
    for (int i=1;i<=tot;i++){
        modify(root[a[i].t],1,xb,i);            
        for (int j=a[i].t+1;j<=a[i+1].t && j<=m;j++) root[j]=root[a[i].t];
    }
    
    ans=1;
    for (int i=1;i<=m;i++){
        scanf("%d%lld%lld%lld",&t,&x,&y,&z);
        k=1+(x*ans+y)%z;
        ans=query(root[t],1,xb,k);
        printf("%lld\n",ans);
    }
    
    return 0;
}