题解 CF1476D 【Journey】

来一发并不怎么正常的 $O(n\log n)$ 做法。 显然，如果你可以通过一条边到达相邻的点，那么这条边反向之后你还可以再走回来，反之，你既不能走过去，也不能走回来。 由于从一个点出发经过若干点回到原点一定经过偶数条边，所以如果初始一条边可以通过，那么在**任何时刻**都可以从**任何方向**通过，反之则**任何时刻**不能从**任何方向**通过。 由于从一个点出发经过若干点回到原点一定经过偶数条边，我们还可以得出我们从某点出发向一个方向走，再回到原点，道路的方向和初始时是相同的，所以不需要考虑两边先后顺序。 那么我们直接分两边计算贡献，一直走到走不过去就好了。 接下来我们需要考虑什么样的序列可以产生贡献，因为每走一步道路方向都会改变，那么我们只要序列交替出现 `L` 和 `R` 就好了。 立即有了一个 naive 的做法：每个点向两边暴力延伸。然而这会被卡。 考虑优化算法，看到最长不重复的子串，容易想到用线段树维护。（之前有一个题目叫“好一个一中腰鼓”，考的就是这个东西，可惜这题现在没掉了，不过我写了一篇题解，不懂怎么用线段树维护的可以先看一下→[传送门](https://www.luogu.com.cn/blog/FrozaFerrari/solution-p2253)） 其实这一题会比刚才提到的那一题更简单一些，因为我们查询的时候要的都是包含左（右）端点的最长合法子串，于是我们并不需要维护区间最大值。 查询的时候直接合并答案就好了。 ```cpp #include<iostream> #include<cstdio> using namespace std; int t,n,ql[300005<<2][2],qr[300005<<2][2],len[300005<<2],ans; char c[300005]; struct element { int q[2],len; element() { q[0]=q[1]=len=0; } }; inline int ls(int k) { return k<<1; } inline int rs(int k) { return k<<1|1; } inline void push_up(int k) { len[k]=len[ls(k)]+len[rs(k)]; ql[k][0]=ql[ls(k)][0]; ql[k][1]=ql[ls(k)][1]; qr[k][0]=qr[rs(k)][0]; qr[k][1]=qr[rs(k)][1]; if(ql[ls(k)][0]==len[ls(k)]) ql[k][0]+=ql[rs(k)][len[ls(k)]&1]; if(ql[ls(k)][1]==len[ls(k)]) ql[k][1]+=ql[rs(k)][(len[ls(k)]&1)^1]; if(qr[rs(k)][0]==len[rs(k)]) qr[k][0]+=qr[ls(k)][len[rs(k)]&1]; if(qr[rs(k)][1]==len[rs(k)]) qr[k][1]+=qr[ls(k)][(len[rs(k)]&1)^1]; } void build(int k,int l,int r) { if(l==r) { len[k]=1; ql[k][c[l]=='R']=qr[k][c[l]=='R']=1; ql[k][c[l]=='L']=qr[k][c[l]=='L']=0; return; } int mid=(l+r)>>1; build(ls(k),l,mid); build(rs(k),mid+1,r); push_up(k); } element query1(int node,int l,int r,int k) { if(r<=node) { element res; res.len=len[k]; res.q[0]=qr[k][0]; res.q[1]=qr[k][1]; return res; } int mid=(l+r)>>1; element res,tmp; tmp=query1(node,l,mid,ls(k)); if(mid<node) res=query1(node,mid+1,r,rs(k)); if(!res.len&&!res.q[0]&&!res.q[1]) return tmp; if(res.q[0]==res.len) { res.q[0]+=tmp.q[res.len&1]; res.len+=tmp.len; } if(res.q[1]==res.len) { res.q[1]+=tmp.q[(res.len&1)^1]; res.len+=tmp.len; } return res; } element query2(int node,int l,int r,int k) { if(l>=node) { element res; res.len=len[k]; res.q[0]=ql[k][0]; res.q[1]=ql[k][1]; return res; } int mid=(l+r)>>1; element res,tmp; tmp=query2(node,mid+1,r,rs(k)); if(mid>=node) res=query2(node,l,mid,ls(k)); if(!res.len&&!res.q[0]&&!res.q[1]) return tmp; if(res.q[0]==res.len) { res.q[0]+=tmp.q[res.len&1]; res.len+=tmp.len; } if(res.q[1]==res.len) { res.q[1]+=tmp.q[(res.len&1)^1]; res.len+=tmp.len; } return res; } int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(register int i=1;i<=n;++i) { c[i]=getchar(); if(c[i]!='L'&&c[i]!='R') c[i]=getchar(); } build(1,1,n); for(register int i=1;i<=n+1;++i) { ans=1; if(i^1) ans+=query1(i-1,1,n,1).q[0]; if(i^(n+1)) ans+=query2(i,1,n,1).q[1]; printf("%d ",ans); } puts(""); } return 0; } ```