《P5445 [APIO2019] 路灯》

题目描述

一辆自动驾驶的出租车正在 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,…,q 时刻，每时刻会发生下列两种事件之一：

• toggle i：切换第 i 个路灯的状态。具体地说，若路灯原来亮起，则现在将熄灭；若路灯原来熄灭，则现在将亮起。

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

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

输入格式

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

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

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

• toggle i：该时刻切换了第 i 个路灯的状态。

• query a b：计算从 0 时刻起到该时刻，共有多少个时刻满足：出租车能从站点 a 出发到达站点 b。

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

输出格式

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

输入输出样例

输入 #1复制

5 7 11011 query 1 2 query 1 2 query 1 6 query 3 4 toggle 3 query 3 4 query 1 6

输出 #1复制

1 2 0 0 1 2

说明/提示

对于全部数据，1≤n,q≤3×105，∣s∣=n，1≤i≤n，1≤a<b≤n+1。

详细子任务附加限制与分值如下表

代码实现：

#include <iostream> #include <cmath> #include <cstring> #include <algorithm> #include <set> using namespace std; const int N=300100; int n,q,x,y; int st[N<<2]; char ch[N],op[10]; namespace t2{ #define mid (l+r>>1) #define lb(x) ((x)&(-(x))) int rt[N<<1],cnt; struct node{ int l,r,sum; }tr[N<<7]; void upd(int &p, int l, int r, int pos, int k){ if(!p) p=++cnt; tr[p].sum += k; if(l == r) return; if(pos <= mid) upd(tr[p].l, l, mid, pos, k); else upd(tr[p].r, mid+1, r, pos, k); } int qry(int p, int l, int r, int L, int R){ if(!p || L>R || l>R || r<L) return 0; if(L<=l && r<=R) return tr[p].sum; return qry(tr[p].l, l, mid, L, R) + qry(tr[p].r, mid+1, r, L, R); } void add(int x, int y, int k){ for(;x<=n+1;x+=lb(x)) upd(rt[x], 1, n+1, y, k); } int query(int x, int y){ int res=0; for(;x;x-=lb(x)) res += qry(rt[x], 1, n+1, 1, y); return res; } } namespace st_set{ #define it set<nd>::iterator struct nd{ int l,r; bool operator < (const nd &b) const { return r < b.r; } }; set<nd> s; void init(){ for(int i=1;i<=n;i++) s.insert(nd{i,i}); } void merge(int x1,int x2,int y1,int y2){ s.erase(nd{x1,x2}); s.erase(nd{y1,y2}); s.insert(nd{x1,y2}); } void split(int x1,int x2,int y1,int y2){ s.erase(nd{x1,y2}); s.insert(nd{x1,x2}); s.insert(nd{y1,y2}); } bool same(int x,int y){ return s.lower_bound(nd{0,x})->l == s.lower_bound(nd{0,y})->l; } } using namespace t2; using namespace st_set; void add_diff(int x1,int y1,int x2,int y2,int k){ add(x1,y1,k); add(x2+1,y2+1,k); add(x1,y2+1,-k); add(x2+1,y1,-k); } int main(){ scanf("%d%d",&n,&q); n++; scanf("%s",ch+1); init(); for(int i=1;i<=n-1;i++){ st[i] = ch[i]-'0'; if(st[i]) merge(s.lower_bound(nd{0,i})->l, i, i+1, i+1); } for(it i=s.begin();i!=s.end();i++) add_diff(i->l,i->l,i->r,i->r,q); for(int i=1;i<=q;i++){ scanf("%s",op+1); if(op[1]=='q'){ scanf("%d%d",&x,&y); int res=query(x,y); if(same(x,y)) res -= q-i; cout<<res<<'\n'; } if(op[1]=='t'){ scanf("%d",&x); it iter = s.lower_bound(nd{0,x}); int x1=iter->l, x2=x, y1=x+1; if(st[x]){ int y2=iter->r; add_diff(x1,y1,x2,y2,i-q); split(x1,x2,y1,y2); } else{ int y2=(++iter)->r; add_diff(x1,y1,x2,y2,q-i); merge(x1,x2,y1,y2); } st[x]^=1; } } return 0; }