fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int len;
  6.     int cnt;
  7.     string pref;
  8.     string suff;
  9.     bool lazy;
  10.     Node(): len(0), cnt(0), pref(""), suff(""), lazy(false) {}
  11. };
  12.  
  13. int N;
  14. string S;
  15. vector<Node> seg;
  16.  
  17. bool is_fish3(const string &t){
  18.     return (t == "><>" || t == "<><");
  19. }
  20.  
  21. string flip_str(const string &t){
  22.     string r = t;
  23.     for(char &c: r) c = (c == '>' ? '<' : '>');
  24.     return r;
  25. }
  26.  
  27. Node merge_node(const Node &L, const Node &R){
  28.     if(L.len == 0) return R;
  29.     if(R.len == 0) return L;
  30.     Node res;
  31.     res.len = L.len + R.len;
  32.     res.cnt = L.cnt + R.cnt;
  33.     string mid = L.suff + R.pref;
  34.     int ls = (int)L.suff.size();
  35.     int ms = (int)mid.size();
  36.     for(int i = 0; i + 3 <= ms; ++i){
  37.         if(i < ls && i+2 >= ls){
  38.             if(is_fish3(mid.substr(i,3))) res.cnt++;
  39.         }
  40.     }
  41.     if(L.len >= 2) res.pref = L.pref;
  42.     else {
  43.         res.pref = L.pref + R.pref;
  44.         if((int)res.pref.size() > 2) res.pref = res.pref.substr(0,2);
  45.     }
  46.     if(R.len >= 2) res.suff = R.suff;
  47.     else {
  48.         res.suff = L.suff + R.suff;
  49.         if((int)res.suff.size() > 2) res.suff = res.suff.substr((int)res.suff.size()-2);
  50.     }
  51.     res.lazy = false;
  52.     return res;
  53. }
  54.  
  55. void apply_flip(Node &v){
  56.     if(v.len == 0) return;
  57.     v.pref = flip_str(v.pref);
  58.     v.suff = flip_str(v.suff);
  59.     v.lazy = !v.lazy;
  60. }
  61.  
  62. void push(int idx){
  63.     if(seg[idx].lazy){
  64.         apply_flip(seg[idx<<1]);
  65.         apply_flip(seg[idx<<1|1]);
  66.         seg[idx].lazy = false;
  67.     }
  68. }
  69.  
  70. void build(int idx, int l, int r){
  71.     if(l == r){
  72.         seg[idx].len = 1;
  73.         seg[idx].cnt = 0;
  74.         seg[idx].pref = seg[idx].suff = string(1, S[l]);
  75.         seg[idx].lazy = false;
  76.         return;
  77.     }
  78.     int m = (l + r) >> 1;
  79.     build(idx<<1, l, m);
  80.     build(idx<<1|1, m+1, r);
  81.     seg[idx] = merge_node(seg[idx<<1], seg[idx<<1|1]);
  82. }
  83.  
  84. void update_flip(int idx, int l, int r, int ql, int qr){
  85.     if(ql > r || qr < l) return;
  86.     if(ql <= l && r <= qr){
  87.         apply_flip(seg[idx]);
  88.         return;
  89.     }
  90.     push(idx);
  91.     int m = (l + r) >> 1;
  92.     update_flip(idx<<1, l, m, ql, qr);
  93.     update_flip(idx<<1|1, m+1, r, ql, qr);
  94.     seg[idx] = merge_node(seg[idx<<1], seg[idx<<1|1]);
  95. }
  96.  
  97. int main(){
  98.     ios::sync_with_stdio(false);
  99.     cin.tie(nullptr);
  100.     cin >> N;
  101.     cin >> S;
  102.     int Q; cin >> Q;
  103.     if(N == 0){
  104.         while(Q--){
  105.             int t; cin >> t;
  106.             if(t == 1){
  107.                 int l,r; cin >> l >> r;
  108.             } else cout << 0 << '\n';
  109.         }
  110.         return 0;
  111.     }
  112.     seg.assign(4 * N + 5, Node());
  113.     build(1, 0, N-1);
  114.     while(Q--){
  115.         int t; cin >> t;
  116.         if(t == 1){
  117.             int l, r; cin >> l >> r;
  118.             --l; --r;
  119.             update_flip(1, 0, N-1, l, r);
  120.         } else {
  121.             cout << seg[1].cnt << '\n';
  122.         }
  123.     }
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
><>><>
6
2
1 4 6
2
1 1 2
1 2 3
2
stdout
copy 
2
4
1
https://ideone.com/carN3R
language:
C++ (gcc 8.3)
created:
2 days 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!