fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 3e5+5;
  7.  
  8. int n, q, f[N];
  9. string S;
  10.  
  11. int bit[N];
  12.  
  13. void update(int p, int v) {
  14.     for (; p <= n; p += p & -p) bit[p] += v;
  15. }
  16.  
  17. int get(int p) {
  18.     int sum = 0;
  19.     for (; p > 0; p -= p & -p) sum += bit[p];
  20.     return sum;
  21. }
  22.  
  23. void build(int i) {
  24.     if (i < 1 || i > n) return;
  25.     int cnt = 0;
  26.     if (i - 1 >= 1 && S[i - 1] == S[i]) cnt++;
  27.     if (i - 2 >= 1 && S[i - 2] == S[i]) cnt++;
  28.     update(i, cnt - f[i]);
  29.     f[i] = cnt;
  30. }
  31.  
  32. void solve() {
  33.     cin >> n >> q >> S;
  34.     S = " " + S;
  35.     for (int i = 1; i <= n; i++) build(i);
  36.     while (q--) {
  37.         int type, l, r; cin >> type >> l >> r;
  38.         if (type == 1) {
  39.             if (S[l] == S[r]) continue;
  40.             swap(S[l], S[r]);
  41.             for (int i = l; i <= l + 2; i++) build(i);
  42.             for (int i = r; i <= r + 2; i++) build(i);
  43.         } else {
  44.             if (l == r) {
  45.                 cout << "1\n";
  46.                 continue;
  47.             }
  48.             int sum = get(r) - get(l);
  49.             if (l - 1 >= 1 && l + 1 <= r && S[l - 1] == S[l + 1]) sum--;
  50.             cout << (sum == 0 ? "1\n" : "0\n");
  51.         }
  52.     }
  53. }
  54.  
  55. int main() {
  56.     ios_base::sync_with_stdio(0); cin.tie(0);
  57.  
  58.     #define TASK "APALIN"
  59.     if (fopen(TASK".INP", "r")) {
  60.         freopen(TASK".INP", "r", stdin);
  61.         freopen(TASK".OUT", "w", stdout);
  62.     }
  63.  
  64.     int tests = 1; // cin >> tests;
  65.     while (tests--) solve();
  66.  
  67.     #ifdef LOCAL
  68.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  69.     #endif
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5 4
ABCAB
2 1 5
1 3 4
2 1 5
2 3 5
stdout
copy 
1
0
1
https://ideone.com/GJEvmh
ĐTQG Cà Mau 2025 - Bài 1 - Phản đối xứng
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!