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