#3146. 「APIO 2019」路灯

题目描述

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

安全起见，出租车只能在被照亮的路段上行驶。换言之，出租车能从站点 \(a\) 出发到达站点 \(b\ (a < b)\) 的条件是：连接站点 \(a\) 与 \(a + 1\)，\(a + 1\) 与 \(a + 2\)，……，\(b − 1\) 与 \(b\) 的路段都被照亮。

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

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

- \(\texttt{toggle}\ i\)：切换第 \(i\) 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

- \(\texttt{query}\ a\ b\)：出租车部门的负责人想知道，从 \(0\) 时刻起到当前时刻，有多少个时刻满足：出租车能够从站点 \(a\) 出发到达站点 \(b\)。

请你帮助出租车部门的负责人回答他们的问题。

输入格式

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

第二行包含一个字符串 \(s\) 表示路灯的初始状态，\(s_i\) 为 1 表示第 \(i\) 个路灯初始时亮起；\(s_i\) 为 0 表示第 \(i\) 个路灯初始时熄灭。

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

- \(\texttt{toggle}\ i\)：该时刻切换了第 \(i\) 个路灯的状态。

- \(\texttt{query}\ a\ b\)：计算从 \(0\) 时刻起到该时刻，共有多少个时刻满足：出租车能从站点 \(a\) 出发到达站点 \(b\)。

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

输出格式

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

数据范围与提示

对于全部数据，\(1\le n,q\le 3\times 10^5,|s|=n,1\le i\le n,1\le a<b\le n+1\)。

我们将所有出现过的极大连续\(1\)序列都处理出来，表示为\((lp,rq,l,r)\)表示每个序列的左右端点和出现时间。可以用\(set\)维护线段的方式处理。

对于第\(i\)个询问\((l_i,r_i)\)，一个线段\((lp,rq,l,r)\)对它的答案有贡献的条件是\(lp\leq l_i,r_i\leq rp,l\geq i\)，贡献是\(\min\{i,r\}-l+1\)。

可以发现这是个三维偏序问题，可以用\(CDQ\)+线段树解决。

代码：

#include
    
     #define ll long long#define N 300005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;char s[N];struct interval {    int lp,rp;    int l,r;    interval() {}    interval(int _lp,int _rp,int _l,int _r) {lp=_lp,rp=_rp,l=_l,r=_r;}    bool operator <(const interval &a)const {return rp
     
      <<2];set
      
       pos;set
       
        ::iterator it;int id[N],R[N];int tot;int ans[N];struct query {    int l,r,tim,id;}q[N];int qt;struct node {    int op,id,r;    node() {}    node(int _op,int _id,int _r) {        op=_op,id=_id,r=_r;    }};bool cmpr(const node &a,const node &b) {    if(a.r!=b.r) return a.r>b.r;    return a.op
        
         >1;    build(v<<1,l,mid),build(v<<1|1,mid+1,r);}void Modify(int v,int l,int r,int f) {    if(tr[v].l>r||tr[v].r
         
          r||tr[v].r
          
           >1; solve(l,mid),solve(mid+1,r); int tag=l; for(int i=mid+1;i<=r;i++) { if(st[i].op==1) continue ; while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) { Modify(1,t[st[tag].id].l,t[st[tag].id].r,1); tag++; } ans[st[i].id]+=query(1,1,q[st[i].id].tim); } for(int i=l;i