P4979 矿洞：坍塌题解

题面

开一棵线段树，区间内合并左右儿子的时候，如果颜色相同则赋成此颜色，否则直接赋成 \(0\)，第三个操作只需要区间 \([l,r]\) 答案不为 \(0\) 且两边颜色不一样即可。比较简单，复杂度 \(O(n\log n)\)。

点击查看代码

#include<iostream>#include<cstdio>using namespace std;const int N=5e5+13;int n,m;char in[N];struct SegTree{int l,r,dat,set;}t[N<<2];#define ls p<<1#define rs p<<1|1#define mid ((t[p].l+t[p].r)>>1)inline void refresh(int p){t[p].dat=(t[ls].dat==t[rs].dat?t[ls].dat:0);}void build(int p,int l,int r){t[p].l=l,t[p].r=r;if(l==r){t[p].dat=in[l]-'A'+1;return;}build(ls,l,mid),build(rs,mid+1,r);refresh(p);}inline void pushup(int p,int x){t[p].dat=t[p].set=x;}inline void pushdown(int p){if(!t[p].set) return;pushup(ls,t[p].set),pushup(rs,t[p].set);t[p].set=0;}void update(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r) return pushup(p,x);pushdown(p);if(l<=mid) update(ls,l,r,x);if(r>mid) update(rs,l,r,x);refresh(p);}int query(int p,int l,int r){if(l<=t[p].l&&t[p].r<=r) return t[p].dat;pushdown(p);if(r<=mid) return query(ls,l,r);if(l>mid) return query(rs,l,r);int lc=query(ls,l,r),rc=query(rs,l,r);return lc==rc?lc:0;}#undef ls#undef rs#undef midint main(){scanf("%d%s",&n,in+1);build(1,1,n);scanf("%d",&m);while(m--){int l,r;char op,c;cin>>op;scanf("%d%d",&l,&r);if(op=='A') cin>>c,update(1,l,r,c-'A'+1);else puts(query(1,l,r)&&(l==1||r==n||query(1,l-1,l-1)!=query(1,r+1,r+1))?"Yes":"No");}return 0;}

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。