YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

时间限制:5000MS      内存限制:524288KB

难度:\(7.0\)

  • 题目描述

一辆自动驾驶的士正在 \(Innopolis\) 的街道上行驶。该街道上有 \(n+1\) 个停车站点,它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起,它将照亮连接第 \(i\) 与第 \(i+1\)个站点的路段。否则这条路段将是黑暗的。

出于安全性的考虑,自动驾驶的士只能行驶在被照亮的路段上。换言之,的士能从站点 \(a\) 出发到达站点 \(b\) \((a<b)\) 的条件是:连接站点 \(a\) 与 \(a+1\),\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。

在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。

现在给定 \(0\) 时刻时,街道上路灯的初始状态。之后 \(1,2,\cdots,q\) 时刻,每时刻会发生下列两种事件之一:

\(toggle i\):切换第 \(i\) 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。

\(query a b\):自动驾驶的士部门的负责人想知道,从 \(0\) 时刻起到当前时刻,有多少个时刻满足:自动驾驶的士能够从站点 \(a\) 出发到达站点 \(b\) 。

请你帮助自动驾驶的士部门的负责人回答他们的问题。

  • 输入格式

第一行包含两个整数 \(n\) 和 \(q\) \((1 \leq n,q \leq 300000)\) —- 表示路灯的数量与时刻数。

第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\), \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起; \(s_i\) 为 \(0\) 表示第 \(i\) 个路灯初始时熄灭。

接下来 \(q\) 行每行描述一个时刻的事件。第 \(i\) 行描述时刻 \(i\) 所发生的事件。

\(toggle i\) \((1 \leq i \leq n)\):该时刻切换了第 \(i\) 个路灯的状态。

\(query a b\) \((1 \leq a < b \leq n+1)\):计算从 \(0\) 时刻起到该时刻,共有多少个时刻满足的士能从站点 \(a\) 出发到达站点 \(b\) 。

至少有一个时刻的事件是 \(query\) 。

  • 输出格式

对于每个 \(query\) 的事件,输出一行单个整数,表示该问题的答案。

  • 样例输入

  • 样例输出

 

 

 


 

 

 

// 原 2019.07.13

本题有多种做法

对于一个询问 \(a, b\) ,它的答案就是所有经过时刻中区间 \([a, b]\) 内的值全为 \(1\) 的情况数。

所以可以考虑维护极大连通 \(1\) 的子段, 设其出现时间为 \(t\) ,那么就会有一个三元组 \(\left(l,r,t\right)\) 。

对于一个询问 \(a,b\) 以及时刻 \(i\) ,要求的就是满足 \(a \geq l, \; b \leq r, \; i \geq t\) 并且没有被删除的三元组 \(\left(l,r,t\right)\) 的个数

问题转化为三维偏序,可以大力树套树 或者 直接上CDQ维护。

同样,增加/删除/询问 这三种操作的顺序要搞清楚。

关于维护极大连通 \(1\) 的子段,可以使用 ODT 。

不过本题中也可以不使用。

既然维护区间有点难度,那就可以维护所有 \(0\) 的点的位置,跑一遍初始化后同样可以快速找到需要 删除/增加 的区间。

(后注:这是因为本题中修改是单点修改,可以不需要区间推平(assign)这个操作。)

不过值得注意的是,本题中三元组对答案的贡献与普通偏序问题稍有区别。

满足条件并且没有被删除的三元组 \(\left(l, r, t\right)\) 对询问 \(\left(a, b, i\right)\) 的贡献为 \(i-t\)

不过注意到无论在 \(x\) 时刻是增加还是删除一个三元组,对该询问的贡献都只是加上或者减去 \(i-x\)

(出现时间为 \(t_1\) ,消失时间为 \(t_2\),那么有 \(ans=t_2-t_1=+(i-t_1)-(i-t_2)\),其余情况同理)

所以CDQ的时候开两个树状数组分别存 \(\sum 1\) 和 \(\sum x\) 即可。

时间复杂度 \(O\left(n \log^2 n\right)\) 。

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注