為什么不試試手寫bitset呢QAQ

存在字符x對應(yīng)二進制第x-'A'位為1

這樣就是線段樹維護區(qū)間或了

#include"cstdio" #include"cstring" #include"iostream" #include"algorithm" using namespace std;const int MAXN=1<<19; const int siz=3;int n,m; char ch[MAXN]; int tag[MAXN<<1],tree[MAXN<<1];void build(int k,int l,int r) {tag[k]=-1;if(l==r){tree[k]=1<<(ch[l]-'A');return;}int i=k<<1,mid=l+r>>1;build(i,l,mid);build(i|1,mid+1,r);tree[k]=tree[i]|tree[i|1];return; }void po(int k,int l,int r) {if(l==r||tag[k]==-1) return;int i=k<<1;tree[i]=tree[i|1]=1<<tag[k];tag[i]=tag[i|1]=tag[k];tag[k]=-1;return; }void cchg(int k,int l,int r,int le,int ri,int x) {po(k,l,r);if(le<=l&&r<=ri){tree[k]=1<<x;tag[k]=x;return;}int i=k<<1,mid=l+r>>1;if(le<=mid) cchg(i,l,mid,le,ri,x);if(mid<ri) cchg(i|1,mid+1,r,le,ri,x);tree[k]=tree[i]|tree[i|1];return; }int cask(int k,int l,int r,int le,int ri) {po(k,l,r);if(le<=l&&r<=ri) return tree[k];int ans=0;int i=k<<1,mid=l+r>>1;if(le<=mid) ans|=cask(i,l,mid,le,ri);if(mid<ri) ans|=cask(i|1,mid+1,r,le,ri);return ans; }int count(int x) {int sum=0;while(x) ++sum,x&=x-1;return sum; }int main() {scanf("%d",&n);scanf("%s",ch+1);build(1,1,n);scanf("%d",&m);while(m--){char p,c;int l,r;scanf("\n%c%d%d",&p,&l,&r);if(p=='A'){scanf("\n%c",&c);cchg(1,1,n,l,r,(int)c-'A');}else{if(l==1||r==n){int ct=cask(1,1,n,l,r);if(count(ct)==1) puts("Yes");else puts("No");}else{int ct=cask(1,1,n,l,r),tp1=cask(1,1,n,l-1,l-1),tp2=tp1|cask(1,1,n,r+1,r+1);if(count(ct)==1&&count(tp2)==2) puts("Yes");else puts("No");}}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AH2002/p/10058770.html

總結(jié)

以上是生活随笔為你收集整理的矿洞：坍塌的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。