BZOJ 3932

还是太naive…

传送门

题目说每次从$S_i$到$E_i$多了一个优先级,但是主席树怎么知道啥时候要多啥时候要少,所以对于每个任务,拆成从$S_i$到最后多一个优先级,从$E_i+1$到最后少一个优先级

然后把所有拆过的操作按照开始时间递增排序,而每个任务会对它的开始时间及之后的$root$数组产生影响,所以把每个任务依次插到主席树里就行了

我来扯一扯我的坎坷经历…

刚开始写得挺开心…写呀写呀写完了…样例一遍过,然后往BZOJ上一交…卧槽0ms TLE 你™逗我?

然后以为BZOJ评测机抽了,又来了三发…还是一样的结果…无奈求助Orz lzy,得知是空间开得太大了把评测机吓尿了

然后求助Orz ZYK查了查哪里有问题,然后被科普了线段树中不记录左右端点的写法,于是乎改了改又交上去卧槽占了600M…

继续求助ZYK大爷…然后发现我开了一棵25000000大小的线段树……………………原谅我too yong too simple不会算内存…

这个是因为我一直以为主席树需要在$root[0]$建出来一整棵树…于是就开了这么大然后建啊建啊…但这道题并不需要$root[0]$的信息…所以就不用建了…

然后又改啊改啊 其实没改多久 然后交了上去…发现才用了100多M…QAQ

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.