Contestant^. Rank 132. Rating +86 (+336 -250).
A. Don't Try to Count
题意
给定两个字符串 \(s, t\)，定义操作为将 \(s\) 本身拼接到 \(s\) 后面，操作非独立。
输出最小的操作次数，使 \(s\) 中包含子串 \(t\)。
思路
显然，数据范围小的离谱，那么我们直接暴力。
我们暴力拼接，然后用合适的复杂度下的字符串匹配即可。
可以发现，需要拼接的次数是很少的，此处用了最多 \(10\) 次，但应该不用这么多。
至于匹配，可以用 \(\mathtt{strstr}\) 函数，底层是用 \(\mathtt{KMP}\) 算法实现的，可以跑的飞快。
时间复杂度：\(O(不大)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
if(strstr(s.c_str(), t.c_str())){
cout << 0 << '\n';
return;
}
for(int i=0;i<10;i++) {
s = s + s;
if(strstr(s.c_str(), t.c_str())){
cout << i + 1 << '\n';
return;
}
}
cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}当然拼个 \(25\) 次就炸了
B. Three Threadlets
题意
给定 \(3\) 根铁丝，定义一次操作为选定任意一根铁丝，并将其裁成任意整数长度的两段。
判断是否可以在最多 \(3\) 次操作内，将铁丝裁成长度相等的若干段。
思路
显然，我们可以贪心地将铁丝裁成等于当前最短的铁丝，如果最后所有铁丝的长度相等，那么操作就是可行的。
时间复杂度：\(O(1)?\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
vector<int> a(3);
for(int i=0;i<3;i++){
int x;
cin >> x;
a[i] = x;
}
bool f = true;
for(int i=1;i<a.size();i++){
if(a[i] != a[0]) f = false;
}
if(f){
cout << "YES\n";
return;
}
for(int i=1;i<=3;i++){
sort(all(a));
int now = a[a.size() - 1];
a.pop_back();
a.pb(a[0]), a.pb(now - a[0]);
f = true;
for(int j=1;j<a.size();j++){
if(a[j] != a[0]) f = false;
}
if(f){
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}乱猜的，但好像也挺显然的（
C. Perfect Square
题意
给定一个字符方阵，定义一次操作为选定一个字符，并将其按字母表顺序 非循环 右移一格（\(z \rightarrow z\)）。
输出最小的操作数，使给定方阵顺时针旋转 \(90°\) 后，和原方阵相等。
思路
首先，对于 \((i, j)\)，可以简单计算得到，顺时针旋转 \(90°\) 后，坐标为 \((j, n - i + 1)\)。
我们来考虑位于方阵左上半部分的点 \(A(i, j)\)：对于点 \(A\)，它关于中心竖线的对称点就是它旋转 \(90°\) 后的点 \(A'\)。
显然，因为给定的是方阵，那么 \(A'\) 旋转 \(90°\) 后的点就是其关于中心横线的对称点。
如上操作 \(4\) 次，我们可以发现，题目条件变成了：
对于每个点，其旋转 \(90k°\) 后的点都要和该点相等。
那么，我们只需枚举左上半矩阵，然后对于每个点，计算这对应 \(4\) 个点对应的字符需要修改多少次才能相等。
至于如何计算，因为不是循环右移，那么我们肯定是修改为最大值更好，那么我们简单计算一下即可。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<string> a(n + 1);
for(int i=1;i<=n;i++) {
cin >> a[i];
a[i] = " " + a[i];
}
int ans = 0;
for(int i=1;i<=n/2;i++){
for(int j=1;j<=n/2;j++){
int x = i, y = j;
int mx = a[x][y] - 'a', sum = mx;
for(int k=1;k<=3;k++){
int t = x;
x = y;
y = n - t + 1;
mx = max(mx, (int)(a[x][y] - 'a'));
sum += (a[x][y] - 'a');
}
ans += mx * 4 - sum;
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}好难解释，太抽象了（x
D. Divide and Equalize
题意
给定一个长为 \(n\) 的序列 \(a\)，定义一次操作为选定两个数 \(a, b\)，若 \(d\) 为 \(a\) 的因数，那么 \(a := \frac{a}{d}, b := b \cdot d\)。
判断任意次操作后，序列所有数是否相等。
思路
首先，根据简单的观察，我们可以发现，操作不影响所有数的乘积。
那么我们只要把总乘积分为 \(n\) 个相等的数的乘积即可。
暴力分是不可行的，但是根据算术基本定理，每个数都可以分解为若干个质因数幂的乘积。
那么，上面的观察等价于：对于每一个质因子，将其均分到 \(n\) 个数中。
因此，我们只需对每个数分解质因数，然后统计所有数中，每个质因子的个数，然后判断其是否是 \(n\) 的倍数即可。
至于分解因数，这里我使用了更快的 \(\mathtt{Miller~Rabin}\)；线性筛之后分解也是可以的。
时间复杂度：\(O(n + p)\) 或更小
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
struct MATH {
private:
struct PRIME {
int Check_Num = 0, Max_Factor = 0;
vector<pii> Dec;
private:
void Get_Fac(int Num) { //寻找 Num 的最大因子
if (Num <= Max_Factor || Num < 2) return;
if (Miller_Rabin(Num)) return void(Max_Factor = max(Max_Factor, Num));
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Get_Fac(Num), Get_Fac(Fac);
}
void Decomposition(int Num) { // 分解 Num 的质因子
if (Num < 2) return;
if (Miller_Rabin(Num)) {
pair<int, int> Now = {Num, 0};
while (Check_Num % Num == 0) Now.second++, Check_Num /= Num;
if (Now.second) Dec.pb(Now);
return;
}
int Fac = Num;
while (Fac >= Num) Fac = Pollard_Rho(Num);//寻 找 因 子
while (!(Num % Fac)) Num /= Fac;
return Decomposition(Num), Decomposition(Fac);
}
public:
__int128 test[16] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(__int128 P) { //检测 P 是不是质数, 严格保证答案正确
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Next;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (j = 1; j <= 15; j++) {
Next = qp(test[j], Tem, P);
if (Next <= 1 || Next == P - 1) continue;
for (i = 0; i < k; ++i) {
Next = Next * Next % P;
if (Next == P - 1 && i != k - 1) {
Next = 1;
break;
}
if (Next == 1) return false;
}
if (Next != 1) return false;
}
return true;
}
static bool RMiller_Rabin(__int128 P, int test_time = 8) { //检测 P 是不是质数, 基于随机检验
if (P < 3 || P % 2 == 0) return P == 2;
static int i, j;
static __int128 Tem, k, Rand_Num, Now;
Tem = P - 1, k = 0;
while (Tem % 2 == 0) Tem >>= 1, ++k;
for (i = 1; i <= test_time; ++i) {
Rand_Num = rand() % (P - 2) + 2, Now = qp(Rand_Num, Tem, P);
if (Now == 1) continue;
for (j = 0; j < k; ++j) {
if (Now == P - 1) break;
Now = Now * Now % P;
}
if (j >= k) return false;
}
return true;
}
static int Pollard_Rho(int x) {
static int s, t, c, Div, Val;
Val = 1, s = t = 0;
static int Step, Goal;
Step = 0, Goal = 1;
c = (int) rand() % (x - 1) + 1;
for (Goal = 1;; Goal <<= 1, s = t, Val = 1) { // 倍增优化
for (Step = 1; Step <= Goal; ++Step) {
t = ((__int128) t * t + c) % x, Val = (__int128) Val * abs(t - s) % x;
if (!(Step % 127)) {
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
Div = __gcd(Val, x);
if (Div > 1) return Div;
}
}
void Get_Max_Fac(int Num) { return Max_Factor = 0, Get_Fac(Num); } //获得 Num 的最大因子 测 试: Luogu P4718
void Dec_Factor(int Num) { return Dec.clear(), Check_Num = Num, Decomposition(Num); } //分解 Num 的本质不同质因子 测 试: Prime Land
int Get_Phi(int Num) { //计算 φ(Num)
if (Num == 1) return 0;
Dec_Factor(Num);
for (auto &Now: Dec) Num = Num / Now.first * (Now.first - 1);
return Num;
}
}pm;
public:
static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
static __int128 ans;
ans = 1, x %= m;
for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
return ans;
}
//ax+by=gcd(a,b),返回gcd
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x; x = y; y = t - (a / b) * y;
return d;
}
//x (mod Mi) = Ai
int exCRT(int n, int M[], int A[]) {
int a = A[1], m = M[1], ta, tm, x, y, d, l, t;
for (int i = 2; i <= n; i++) {
tm = M[i], ta = A[i];
d = exgcd(m, tm, x, y);
l = m * tm / d;
if ((ta - a) % d != 0) return -1;
t = tm / d;
x *= ((ta - a) / d);
x = (x % t + t) % t;
a += m * x;
m = l;
}
return a;
}
//欧拉函数，小于等于n和n互质的数的个数
int phi(int n) {
return pm.Get_Phi(n);
}
bool vis[N];
int pri[N], cnt;
//线性筛
void linear_prime(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[cnt++] = i;
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = true;
if (i % pri[j] == 0)break;
}
}
}
int inv_ex(int n, int m = mod) {
int x, y, ans = exgcd(n, m, x, y);
if (ans == 1) return (x % m + m) % m;
else return -1;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }
//p为1e5以内质数，求c(n, m) % p
int lucas(int n, int m, int p) {
if (m == 0) return 1;
return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}
int C(int m, int n, int p) {
int a = 1, b = 1;
if (m < n) return 0;
while (n) {
a = (a * m) % p, b = (b * n) % p;
m--, n--;
}
return a * inv_ex(b, p) % p;
}
void get_phi(int n, int phi[]) {
for (int i = 0; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++)
if (phi[i] == i) for (int j = 2; j <= n; j++) phi[j] = phi[j] / i * (i - 1);
}
//线性求逆元
void get_inv(int n, int inv[], int p = mod) {
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = inv[i] = (p - p / i * inv[p % i] % p) % p;
}
//线性求阶乘，逆元，阶乘逆元
void get_fact_inv(int n, int fac[], int Inv[], int fac_inv[], int p = mod) {
fac[0] = fac_inv[0] = Inv[0] = fac[1] = fac_inv[1] = Inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % p;
Inv[i] = (p - p / i * Inv[p % i] % p) % p;
fac_inv[i] = fac_inv[i - 1] * Inv[i] % p;
}
}
vector<pii> factorize(int x) { return pm.Dec_Factor(x), pm.Dec; }
int max_factor(int x){ return pm.Get_Max_Fac(x), pm.Max_Factor; }
bool miller_rabin(__int128 P){ return pm.Miller_Rabin(P); }
void random_miller_rabin(__int128 P, int test_time = 8){ pm.RMiller_Rabin(P, test_time); }
int pollard_pho(int x) { return pm.Pollard_Rho(x); }
template<class T> T ex_sqrt(T x) { //返回精度更高的sqrt
T sqrtX = sqrt(x) - 1;
while (sqrtX + 1 <= x / (sqrtX + 1)) sqrtX++;
return sqrtX;
}
}math;
void solve() {
int n;
cin >> n;
map<int, int> cnt;
for(int i=1;i<=n;i++){
int a;
cin >> a;
vector<pii> fact = math.factorize(a);
for(auto [x, y] : fact) cnt[x] += y;
}
bool f = true;
for(auto [x, y] : cnt){
if(y % n != 0) f = false;
}
cout << (f ? "YES\n" : "NO\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}板子也是长的离谱
E. Block Sequence
题意
给定一个序列 \(a\)，定义一次操作为从序列中选择任意一个数，并将其删除。
输出最小的操作数，使序列可以拆分为若干段 "cnt cnt个数"。
思路
首先，对于每个数，它有删除和不删除的两个状态，这类似于子序列，从而我们考虑用动态规划解决此题。
因为从前往后不好推导状态，我们不知道前面删除了多少数，从而我们考虑从后往前递推。
我们不妨令 \(dp[i][j]\) 为 \(a_{i, n}\) 中第 \(i\) 位选或者不选对应的最小删除个数。
对于第 \(i\) 位，如果该位不选，那么类似于非连续子序列，我们从上一位递推，\(dp[i][0] = \min(dp[i + 1][0], dp[i + 1][1]) + 1\)；
如果该位要选，那么我们就需要从 \(i + a[i] + 1\) 递推，从而有 \(dp[i][1] = \min(dp[i + a[i] + 1][1], dp[i + a[i] + 1][1]\)。
至于上述递推为何成立，因为我们在递推 \(dp[i][0]\) 的时候，我们类似于把这个数从序列中剔除了，此时不影响后面 "\(+a[i] + 1\)" 的操作是否准确。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
vector<vector<int>> dp(n + 2, vector<int>(2, inf));
dp[n][0] = 1;
dp[n + 1][0] = 0;
for(int i=n-1;i>=1;i--){
dp[i][0] = min(dp[i + 1][0], dp[i + 1][1]) + 1;
if(i + a[i] > n) continue;
dp[i][1] = min(dp[i + a[i] + 1][0], dp[i + a[i] + 1][1]);
}
cout << min(dp[1][0], dp[1][1]) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}也是赛时对着非连续子序列的递推方式一顿爆改过去了（
F. Minimum Maximum Distance
题意
给定一棵树，以及一个序列 \(a\)，\(a_i\) 代表第 \(i\) 个被标记的点。
现在，遍历树上的所有点，对于每一个点 \(i\)，记 \(f_i\) 为该点到所有被标记的点的最短路的长度的最大值。
输出 \(f_i\) 的最小值。
思路
首先，可以证明的是，我们只需考虑距离最远的两个被标记的点，类似于 "树的直径"。
类比树的直径，我们可以跑 \(3\) 次 \(\mathtt{bfs}\) 求出这两个点，以及每个点到所有点的距离。
我们记距离为 \(dist_1, dist_2\)，那么对于每个点，它到所有被标记的点的最大距离就是 \(\max(dist_1[i], dist_2[i])\)，最后我们取最小值即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
vector<bool> st(n + 1);
for(int i=1;i<=k;i++){
int cur;
cin >> cur;
st[cur] = true;
}
vector<vector<int>> e(n + 1);
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
vector<int> dist(n + 1);
auto bfs = [&](int s) {
dist.assign(n + 1, -1);
queue<int> q;
q.ep(s);
dist[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(auto y : e[x]){
if(dist[y] == -1){
dist[y] = dist[x] + 1;
q.ep(y);
}
}
}
int p = -1;
for(int i=1;i<=n;i++){
if(st[i] && (p == -1 || dist[i] > dist[p])) p = i;
}
return p;
};
int a = bfs(1),
s = bfs(a);
auto re = dist;
bfs(s);
int ans = inf;
for(int i=1;i<=n;i++) ans = min(ans, max(dist[i], re[i]));
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}也是在赛时没想到这个结论的（x
G. Anya and the Mysterious String
题意
给定一个字符串 \(s\)，定义询问如下：
\(1~l~r~x\)，将 \(s_{l ,r}\) 内的所有字符按字母表顺序循环右移 \(x\) 位；
\(2~l~r\)，判断 \(s_{l,r}\) 中是否包含回文串
现在，给定 \(q\) 个询问，执行对应的操作。
思路
首先，我们考虑下面的贪心：
既然我们只需判断是否包含回文串，那么我们只需考虑区间内是否包含长度为 \(2, 3\) 的回文串即可。
为何呢？因为如果有比它更长的，它也会包含长度为 \(2\) 或 \(3\) 的回文串。
那么，问题简化为判断长度为 \(2\) 或 \(3\) 的回文串是否在区间内即可。
对于区间修改，因为我们是整体右移的，可以发现，操作对区间内是否包含回文串不造成任何影响，而只会对端点处的造成影响。
那么，我们考虑下面的分类讨论：
对于长度为 \(2\) 的回文串，我们只需考虑修改后，\(s[l - 1]\) 和 \(s[l]\) 是否相等，以及 \(s[r]\) 和 \(s[r + 1]\) 是否相等即可；
对于长度为 \(3\) 的回文串，我们只需考虑以某个点为回文中心，它的相邻两侧字符是否相等即可。
此处需要考虑 \(4\) 个情况，即回文中心分别为 \(l-1, l, r, r + 1\) 的时候的判断。
当然，因为我们还对区间进行了修改，并且区间内修改的值是相等的，从而我们可以考虑差分数组，然后进行前缀和即可。
如上，我们可以使用 \(3\) 个树状数组完成本题，分别维护差分数组，区间内长度为 \(2, 3\) 的回文串的个数。
注意边界的判断。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
template<class Info = int>
struct BinaryIndexTree {
int n;
vector<Info> info;
BinaryIndexTree() : n(0) {}
explicit BinaryIndexTree(int _n, Info _v = Info()) : info(_n + 1, _v), n(_n) {}
inline static int lowbit(int x) { return x & (-x); }
void pointUpdate(int pos, Info _info) {
for (int i = pos; i <= n; i += lowbit(i)) info[i] = info[i] + _info;
}
Info rangeQuery(int r) {
Info ans{};
for (int i = r; i > 0; i -= lowbit(i)) ans = ans + info[i];
return ans;
}
Info rangeQuery(int l, int r) {
return rangeQuery(r) - rangeQuery(l - 1);
}
};
struct Info{
int val = 0;
};
Info operator+(const Info &a, const Info &b) {
Info c;
c.val = ((a.val + b.val) % 26 + 26) % 26;
return c;
}
Info operator-(const Info &a, const Info &b) {
return a + Info{-b.val};
}
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
s = " " + s;
BinaryIndexTree<> two(n), three(n);
BinaryIndexTree<Info> d(n + 1); //d 差分
for(int i=1;i<=n;i++){
d.pointUpdate(i, {s[i] - 'a'});
d.pointUpdate(i + 1, {-(s[i] - 'a')});
if(i < n && s[i] == s[i + 1]) two.pointUpdate(i, 1);
if(i < n - 1 && s[i] == s[i + 2]) three.pointUpdate(i, 1);
}
while(m --){
int op;
cin >> op;
if(op == 1) {
int l, r, x;
cin >> l >> r >> x;
if(r - l + 1 >= 1) {
if(l > 1 && d.rangeQuery(l - 1).val == d.rangeQuery(l).val) two.pointUpdate(l - 1, -1);
if(r < n && d.rangeQuery(r).val == d.rangeQuery(r + 1).val) two.pointUpdate(r, -1);
if(l > 2 && d.rangeQuery(l - 2).val == d.rangeQuery(l).val) three.pointUpdate(l - 2, -1);
if(r < n - 1 && d.rangeQuery(r).val == d.rangeQuery(r + 2).val) three.pointUpdate(r, -1);
}
if(r - l + 1 >= 2) {
if(l > 1 && d.rangeQuery(l - 1).val == d.rangeQuery(l + 1).val) three.pointUpdate(l - 1, -1);
if(r < n && d.rangeQuery(r - 1).val == d.rangeQuery(r + 1).val) three.pointUpdate(r - 1, -1);
}
d.pointUpdate(l, {x});
d.pointUpdate(r + 1, {-x});
//维护端点
if(r - l + 1 >= 1) {
if(l > 1 && d.rangeQuery(l - 1).val == d.rangeQuery(l).val) two.pointUpdate(l - 1, 1);
if(r < n && d.rangeQuery(r).val == d.rangeQuery(r + 1).val) two.pointUpdate(r, 1);
if(l > 2 && d.rangeQuery(l - 2).val == d.rangeQuery(l).val) three.pointUpdate(l - 2, 1);
if(r < n - 1 && d.rangeQuery(r).val == d.rangeQuery(r + 2).val) three.pointUpdate(r, 1);
}
if(r - l + 1 >= 2) {
if(l > 1 && d.rangeQuery(l - 1).val == d.rangeQuery(l + 1).val) three.pointUpdate(l - 1, 1);
if(r < n && d.rangeQuery(r - 1).val == d.rangeQuery(r + 1).val) three.pointUpdate(r - 1, 1);
}
}else{
int l, r;
cin >> l >> r;
if(two.rangeQuery(l, r - 1) > 0 || three.rangeQuery(l, r - 2) > 0){
cout << "NO\n";
}else{
cout << "YES\n";
}
}
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}其实应该有点裸的数据结构题（x
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论