题目描述一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 n1 个停车站点它们将街道划分成了 n 条路段。每一路段都拥有一个路灯。当第 i 个路灯亮起它将照亮连接第 i 与第 i1 个站点的路段。否则这条路段将是黑暗的。安全起见出租车只能在被照亮的路段上行驶。换言之出租车能从站点 a 出发到达站点 b(ab) 的条件是连接站点 a 与 a1a1 与 a2……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∣n1≤i≤n1≤ab≤n1。详细子任务附加限制与分值如下表子任务附加限制分值1n, q≤100202对于所有 query a b 事件满足 ab−1203对于所有 toggle i 事件第 i 个路灯将被点亮204所有 toggle 事件都发生在第一个 query 事件之前205无特殊限制20代码实现#include iostream #include cmath #include cstring #include algorithm #include set using namespace std; const int N300100; int n,q,x,y; int st[N2]; char ch[N],op[10]; namespace t2{ #define mid (lr1) #define lb(x) ((x)(-(x))) int rt[N1],cnt; struct node{ int l,r,sum; }tr[N7]; void upd(int p, int l, int r, int pos, int k){ if(!p) pcnt; tr[p].sum k; if(l r) return; if(pos mid) upd(tr[p].l, l, mid, pos, k); else upd(tr[p].r, mid1, r, pos, k); } int qry(int p, int l, int r, int L, int R){ if(!p || LR || lR || rL) return 0; if(Ll rR) return tr[p].sum; return qry(tr[p].l, l, mid, L, R) qry(tr[p].r, mid1, r, L, R); } void add(int x, int y, int k){ for(;xn1;xlb(x)) upd(rt[x], 1, n1, y, k); } int query(int x, int y){ int res0; for(;x;x-lb(x)) res qry(rt[x], 1, n1, 1, y); return res; } } namespace st_set{ #define it setnd::iterator struct nd{ int l,r; bool operator (const nd b) const { return r b.r; } }; setnd s; void init(){ for(int i1;in;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(x21,y21,k); add(x1,y21,-k); add(x21,y1,-k); } int main(){ scanf(%d%d,n,q); n; scanf(%s,ch1); init(); for(int i1;in-1;i){ st[i] ch[i]-0; if(st[i]) merge(s.lower_bound(nd{0,i})-l, i, i1, i1); } for(it is.begin();i!s.end();i) add_diff(i-l,i-l,i-r,i-r,q); for(int i1;iq;i){ scanf(%s,op1); if(op[1]q){ scanf(%d%d,x,y); int resquery(x,y); if(same(x,y)) res - q-i; coutres\n; } if(op[1]t){ scanf(%d,x); it iter s.lower_bound(nd{0,x}); int x1iter-l, x2x, y1x1; if(st[x]){ int y2iter-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; }