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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| program bzoj_3932;
type op=record st,p:longint; flag:boolean; end;
var s:array[0..4900000]of record lc,rc,size:longint; sum:int64; end;
q:array[0..200000]of op;
n,m,x,a,b,c,k,i,j,maxp,tot:longint;
root:array[0..200000]of longint;
ans:int64;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:op;
begin
i:=l;
j:=r;
mid:=q[(l+r)>>1];
repeat
while q[i].st<mid.st do inc(i);
while q[j].st>mid.st do dec(j);
if i<=j then
begin
p:=q[i];
q[i]:=q[j];
q[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure insert(var t:longint;base,p,l,r:longint;flag:boolean);
var mid:longint;
begin
inc(tot);
t:=tot;
s[t]:=s[base];
if flag then inc(s[t].size) else dec(s[t].size);
if flag then inc(s[t].sum,p) else dec(s[t].sum,p);
if l=r then exit;
mid:=(l+r)>>1;
if p<=mid then insert(s[t].lc,s[base].lc,p,l,mid,flag) else insert(s[t].rc,s[base].rc,p,mid+1,r,flag);
end;
function query(t,l,r,p:longint):int64;
var mid:longint;
begin
if l=r then exit(l*min(s[t].size,p));
mid:=(l+r)>>1;
if p=s[s[t].lc].size then exit(s[s[t].lc].sum);
if p<=s[s[t].lc].size then exit(query(s[t].lc,l,mid,p)) else exit(s[s[t].lc].sum+query(s[t].rc,mid+1,r,p-s[s[t].lc].size));
end;
begin
readln(m,n);
maxp:=0;
for i:=1 to m do
begin
readln(a,b,c);
q[i<<1-1].st:=a;
q[i<<1-1].p:=c;
q[i<<1-1].flag:=true;
q[i<<1].st:=b+1;
q[i<<1].p:=c;
q[i<<1].flag:=false;
if c>maxp then maxp:=c;
end;
qsort(1,m<<1);
tot:=1;
for i:=1 to q[1].st do root[i]:=1;
for i:=1 to m<<1 do
begin
insert(root[q[i].st],root[q[i].st],q[i].p,1,maxp,q[i].flag);
if i<m<<1 then for j:=q[i].st to q[i+1].st do root[j]:=root[q[i].st];
end;
ans:=1;
for i:=1 to n do
begin
readln(x,a,b,c);
k:=1+(a*ans+b)mod c;
ans:=query(root[x],1,maxp,k);
writeln(ans);
end;
end.
|