酷暑一夏1

不忘初心,方得始终


Vijos 1881闪烁的繁星 题解

题目

有n颗星星,每颗星星或亮或暗,刚开始都是亮着的,每次选择一颗星星改变它的状态,每次改变后求最大的相邻星星状态不同的长度。

题解

处理这道题,我们使用线段树,在向上传递时,在父亲节点中把两个子节点的值合并处理。这样不断向上传递到达根节点合并完毕后即可获得结果。
此处的合并处理,目的在于将两个子节点拼接起来,例如左右儿子代表的01串分别为10101|00000,那么显然,只计入左儿子和只计入右儿子所得结果都是片面的,只有将其拼接才能获得一个全面的结果。
在这里对于每个节点,记录其所代表的01串的最左最右端的值,最左向右和最右向左的最大连续长度,以如下思路进行拼接

1 最左向右和最右向左的最大连续长度分别处理
2 判断某侧儿子(取决于1中更新的是哪个值)是否整串符合要求
2.1 是,判断左儿子的最右端和右儿子的最左端能否拼接
2.1.1 是,则拼接(将长度相加,脑补一下即可)
2.2 不是,则直接复制该侧儿子的信息即可

此处分类讨论情况巨繁杂,需谨慎处理!

代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<cstdio>
#include<algorithm>
#define ls pos<<1
#define rs (pos<<1)+1
#define MID (tree[pos].l+tree[pos].r)>>1
const int MAXN=200000+5;
struct Tree{int l,r,left,right,lv,rv,is,len,ans;};
//l,r means a RANGE
//left,right means a LENGTH
//lv,rv means a VALUE
Tree tree[MAXN*4];int n,q,ask;
void UpReload(int pos)
{
//Update Left
if(tree[ls].is)
{
if(tree[rs].lv!=tree[ls].rv)
{
if(tree[rs].is)
{
tree[pos].is=1;
tree[pos].left=tree[pos].len;
}
else
{
tree[pos].is=0;
tree[pos].left=tree[ls].len+tree[rs].left;
}
}
else
{
if(tree[rs].lv!=tree[ls].rv)
{
tree[pos].left=tree[ls].len+tree[rs].left;
tree[pos].is=0;
}
else
{
tree[pos].is=0;
tree[pos].left=tree[ls].len;
}
}
}
else
{
tree[pos].is=0;
tree[pos].left=tree[ls].left;
}
//Update Right
if(tree[rs].is)
{
if(tree[ls].is)
{
if(tree[ls].rv!=tree[rs].lv)
{
tree[pos].is=1;
tree[pos].right=tree[pos].len;
}
else
{
tree[pos].is=0;
tree[pos].right=tree[rs].len;
}
}
else
{
if(tree[ls].rv!=tree[rs].lv)
{
tree[pos].is=0;
tree[pos].right=tree[rs].len+tree[ls].right;
}
else
{
tree[pos].is=0;
tree[pos].right=tree[rs].len;
}
}
}
else
{
tree[pos].is=0;
tree[pos].right=tree[rs].right;
}
//General Updates
tree[pos].rv=tree[rs].rv;
tree[pos].lv=tree[ls].lv;
int ans1=-1;
if(tree[ls].rv!=tree[rs].lv)
{
ans1=tree[ls].right+tree[rs].left;
}
ans1=std::max(ans1,std::max(std::max(tree[ls].left,tree[ls].right),std::max(tree[rs].left,tree[rs].right)));
tree[pos].ans=std::max(std::max(tree[ls].ans,tree[rs].ans),std::max(std::max(tree[pos].left,tree[pos].right),ans1));
// printf("Range=%d~%d\nLeft=%d\nRight=%d\nAnswer=%d\n",tree[pos].l,tree[pos].r,tree[pos].left,tree[pos].right,tree[pos].ans);
}
void BuildTree(int l,int r,int pos)
{
tree[pos].l=l;tree[pos].r=r;tree[pos].len=r-l+1;
if(l==r)
{
tree[pos].lv=tree[pos].rv=tree[pos].left=tree[pos].right=tree[pos].is=1;
return;
}
int mid=MID;
BuildTree(l,mid,ls);BuildTree(mid+1,r,rs);
UpReload(pos);
}
void Update(int target,int pos)
{
if(tree[pos].l==tree[pos].r)
{
tree[pos].lv=tree[pos].rv=!tree[pos].rv;
return;
}
int mid=MID;
if(target<=mid) Update(target,ls); else Update(target,rs);
UpReload(pos);
}
int main()
{
scanf("%d %d",&n,&q);
BuildTree(1,n,1);
for(int i=1;i<=q;i++)
{
scanf("%d",&ask);
Update(ask,1);
printf("%d\n",tree[1].ans);
}
return 0;
}
最近的文章

CodeForces近期比赛题解

注意此处比赛分别为Round462, 463, 464, 466,均为Div2 Round462A题面Tommy有n个灯笼,BanBan有m个灯笼,Tommy拿走一个灯笼,分别从Tommy的和BanBan的选择一个灯笼,求最大乘积,假设双方都使用最优决策。 题解枚举Tommy拿走的灯笼,及Tommy …

于  CodeForces, 比赛 继续阅读
更早的文章

牛客练习赛9 A,B,D 题解

A题目珂朵莉想每天都给威廉送礼物,于是她准备了n个自己的本子她想送最多的天数,使得每天至少送一个本子,但是相邻两天送的本子个数不能相同珂朵莉最多送几天礼物呢 题解很明显,符合要求的最小整数有1和2,只要1,2,1,2,1,2,…这样算下去就好了 代码1234567891011121314151617 …

于  NowCoder, 比赛, 牛客练习赛 继续阅读