糖果自动管理系统

来历

建议这里
备用

题目

【题意】
糖果自动管理系统能管理N堆糖果。初始时,所有堆糖果数目为0。
(1)I a b c(1≤a≤b≤N,0 < c≤100),ACM将在堆a至堆b之间(包含a和b)每堆糖果加c个。
(2)C a b(1≤a≤b≤N),将会选择a到b堆之间糖果数最多的清空。选择编号小的。给出一系列的操作,对于每个C操作,输出堆的糖果数。
【输入】
第一行为两个整数N,M(0< N,M≤10^5),N表示糖果堆的数目,M表示操作的次数。
【输出】
对于每个C操作,输出小朋友能得到的糖果的数目。
【输入样例】
5 4
I 1 5 1
C 2 3
I 2 2 4
C 2 3
【输出样例】
1
4

代码

不完整,通用部分可以参考这里

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
void update(int x)
{
f[f[x].tl].c+=f[x].lazy;
f[f[x].tr].c+=f[x].lazy;
f[f[x].tl].lazy+=f[x].lazy;
f[f[x].tr].lazy+=f[x].lazy;
f[x].lazy=0;
}
void make(int x,int l,int r,int k)
{
if(f[x].l==l and r==f[x].r)
{
f[x].c+=k;
f[x].lazy+=k;
return;
}
……
if(r<=mid) make(fl,l,r,k);
else if(l>mid) make(fr,l,r,k);
else
{
make(fl,l,mid,k);
make(fr,mid+1,r,k);
}
if(f[fl].c>=f[fr].c)
{
f[x].mc=f[fl].mc;
f[x].c=f[fl].c;
}
else
{
f[x].mc=f[fr].mc;
f[x].c=f[fr].c;
}
}
int fc,fmc;
void qesc(int x,int l,int r)
{
if(f[x].l==l and f[x].r==r)
{
fc=f[x].c;
fmc=f[x].mc;
return;
}
if(r<=mid) qesc(fl,l,r);
else if(l>mid) qesc(fr,l,r);
else
{
qesc(fl,l,mid);
int ac=fc,amc=fmc;
qesc(fr,mid+1,r);
if(ac>=fc)
{
fc=ac;
fmc=amc;
}
}
}
int main()
{
num=0;br(1,n);
for(int i=1;i<=m;i++)
{
scanf("%s%d%d",ch,&a,&b);
if(ch[0]=='C')
{
qesc(1,a,b);
printf("%d\n",fc);
make(1,fmc,fmc,-fc);
}
else
{
scanf("%d",&d);make(1,a,b,d);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/739e.html
转载请注明出处,谢谢!