【P4979 矿洞：坍塌】题解

斜揽残箫 · 2021-06-05 09:41:37 · 题解

Solution

先说句闲话，本来看到这个题目想写线段树的，但是发现暴力有 70，就先写了暴力，结果暴力直接过了，数据好水，那就宣传一下这道题能写暴力吧 /cy。

下面的 x,y 与题目中的相同。

替换的时候直接从 x \to y 枚举一遍，换一下就行。

查询的话也是从 x + 1\to y 枚举一遍，判断 a_{i - 1} = a_i，如果发现不相等直接跳出，输出 No，否则输出 Yes。

最后的时候判断一下 x - 1 与 y + 1 是否相等，相等的话就输出 No，否则输出 Yes。

开始的时候把 a_{n + 1} 与 a_0 设为不一样的数就不用特别判断 x = 1 \ \ \And\And \ \ y = n 的情况了。

要吸氧才能过。

Code

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxk = 5e5 + 10;
int n,m;
char s[Maxk];
int a[Maxk];
struct Node{
  int l_;
  int r_;
  int tag_; 
}t[Maxk << 2];
inline int read()
{
    int s = 0, f = 0;char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}
signed main()
{
  n = read();
  cin >> s + 1;
  for(int i = 1;i <= n;i ++) a[i] = s[i] - 'A' + 1;
  a[n + 1] = 7; 
  m = read();
  for(int i = 1;i <= m;i ++) {
    char z;cin >> z;
    if(z == 'A') {
      int x = read(),y = read();
      char op;cin >> op;
      for(int j = x;j <= y;j ++) a[j] = op - 'A' + 1;
    }
    else {
      int x = read(),y = read();
      bool f = false;
      for(int j = x + 1;j <= y;j ++) if(a[j - 1] != a[j]) {f = true;break;}
      if(a[x - 1] == a[y + 1]) f = true;
      if(f) puts("No");
      else puts("Yes");
    }
  }
  return 0; 
}