很清新的DS题，话说我好久没写过DS了……

首先我们考虑把一对路灯\(x,y\)间的答案看做点对\((x,y)\)，那么显然有一个性质，若\(l,r\)联通，则\(u,v(l\le u<v\le r)\)也联通

换句话说就是\((x,y)\)为最长的连续的1子序列的两个端点，那么每次它会对矩形\((x,x),(y,y)\)内的每个点都造成贡献

我们考虑类似于ODT那样用set维护每个最长的连续的1子序列，这样只需要在切换状态的时候把区间和贡献一起计算即可

很容易发现这里的时间是有可减性的，那么意味着我们只需要求出这个区间上次加入的时间，和当前时间的差值就是它的贡献

现在题目变成了二维平面内的区间修改，单点查询问题，可以CDQ分治+树状数组也可以大力树套树

反正都是\(O(n\log^2n)\)我就写了相对好写的树套树

#include<cstdio>#include<set>#define RI register int#define CI const int&using namespace std;const int N=300005;struct interval{ int l,r,t; inline interval(CI L=0,CI R=0,CI T=0) { l=L; r=R; t=T; } friend bool operator < (const interval& A,const interval& B) { return A.l<B.l; }}; char s[N],opt[10]; int n,q,x,y,lst; set <interval> S;typedef set <interval>:: iterator SI;class Tree_Array_Segment_Tree{ private: struct segment { int ch[2],v; }node[N*300]; int rt[N],tot; #define lc(x) node[x].ch[0] #define rc(x) node[x].ch[1] #define V(x) node[x].v #define TN CI l=1,CI r=n inline void _modify(int& now,CI beg,CI end,CI mv,TN) { if (!now) now=++tot; if (beg<=l&&r<=end) return (void)(V(now)+=mv); int mid=l+r>>1; if (beg<=mid) _modify(lc(now),beg,end,mv,l,mid); if (end>mid) _modify(rc(now),beg,end,mv,mid+1,r); } inline int _query(CI now,CI pos,TN) { if (!now) return 0; if (l==r) return V(now); int mid=l+r>>1; return (pos<=mid?_query(lc(now),pos,l,mid):_query(rc(now),pos,mid+1,r))+V(now); } #undef lc #undef rc #undef V #undef TN public: #define lowbit(x) (x&-x) inline void modify(CI l1,CI r1,CI l2,CI r2,CI mv) { for (RI x=l1;x<=n;x+=lowbit(x)) _modify(rt[x],l2,r2,mv); for (RI x=r1+1;x<=n;x+=lowbit(x)) _modify(rt[x],l2,r2,-mv); } inline int query(RI x,CI y,int ret=0) { for (;x;x-=lowbit(x)) ret+=_query(rt[x],y); return ret; } #undef lowbit}T;inline SI find(CI x){ return --S.upper_bound(interval(x));}inline void On(CI tim,CI x){ SI it; int l=x,r=x; if (s[x+1]==‘1‘) it=find(x+1),T.modify(it->l,it->r,it->l,it->r,tim-it->t),r=it->r,S.erase(it); if (s[x-1]==‘1‘) it=find(x-1),T.modify(it->l,it->r,it->l,it->r,tim-it->t),l=it->l,S.erase(it); S.insert(interval(l,r,tim)); s[x]=‘1‘;}inline void Off(CI tim,CI x){ SI it=find(x); int l=it->l,r=it->r,t=it->t; T.modify(l,r,l,r,tim-t); S.erase(it); if (l!=x) S.insert(interval(l,x-1,tim)); if (r!=x) S.insert(interval(x+1,r,tim)); s[x]=‘0‘;}inline int Ext(CI tim,CI l,CI r){ if (s[l]==‘0‘) return 0; SI it=find(l); return r<=it->r?tim-it->t:0;}int main(){ RI i; for (scanf("%d%d%s",&n,&q,s+1),i=1;i<=n;++i) if (s[i]==‘0‘) { if (lst+1<=i-1) S.insert(interval(lst+1,i-1,0)); lst=i; } if (lst!=n) S.insert(interval(lst+1,n,0)); for (i=1;i<=q;++i) { scanf("%s%d",opt,&x); if (opt[0]==‘t‘) { if (s[x]==‘0‘) On(i,x); else Off(i,x); } else scanf("%d",&y),printf("%d\n",T.query(x,y-1)+Ext(i,x,y-1)); } return 0;}