Advertisement
Kevin_Zhang

Untitled

Jul 1st, 2020
439
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. using namespace std;
  4. using ll = long long;
  5. const int maxn = 500010;
  6. struct node {
  7.     bool fl = false, sm = false;
  8.     int ans[2]{1, 1}, sym[2]{}, len[2]{}, sec[2]{1, 1};
  9.     node(int v) {
  10.         len[0] = len[1] = 1;
  11.         sym[0] = sym[1] = v;
  12.         sm = true;
  13.     }
  14.     int res() {
  15.         return ans[0];
  16.     }
  17.     node(node a, node b) {
  18.         bool rt = false;
  19.         if (!a.len[0]) (*this) = b, rt = true;
  20.         if (!b.len[0]) (*this) = a, rt = true;
  21.         if (rt) return;
  22.         for (int i : {0, 1})
  23.             ans[i] = max(a.ans[i], b.ans[i]);
  24.         sym[0] = a.sym[0], sym[1] = b.sym[1];
  25.         len[0] = a.len[0], len[1] = b.len[1];
  26.         sec[0] = a.sec[0], sec[1] = b.sec[1];
  27.  
  28.         if (a.sym[1] == b.sym[0]) {
  29.             //cout << "MID SAME \n";
  30.             {
  31.                 auto &v = ans[ a.sym[1]^1 ];
  32.                 v = max(v, a.sec[1] + b.len[0] );
  33.             }
  34.             {
  35.                 auto &v = ans[ a.sym[1] ];
  36.                 v = max(v, b.sec[0] + a.len[1] );
  37.             }
  38.         }
  39.         else
  40.             ans[a.sym[1]] = max(ans[a.sym[1]], a.len[1] + b.len[0]);
  41.         if (a.sm)
  42.             len[0] += b.sym[0] == a.sym[0] ? b.len[0] : 0, sec[0] = b.sec[0] + a.len[0];
  43.         if (b.sm)
  44.             len[1] += b.sym[0] == a.sym[1] ? a.len[1] : 0, sec[1] = a.sec[1] + b.len[0];
  45.         if (a.sm && b.sm && a.sym[0] == b.sym[0]) {
  46.             sm = true;
  47.             //cout << "SAME " << a.len[0] + b.len[0] << '\n';
  48.             len[0] = len[1] = a.len[0] + b.len[0];
  49.             sym[0] = sym[1] = a.sym[0];
  50.         }
  51.     }
  52.     void flip() {
  53.         fl ^= 1;
  54.         swap(ans[0], ans[1]);
  55.         sym[0] ^= 1, sym[1] ^= 1;
  56.         //swap(sym[0], sym[1]);
  57.     }
  58.     node(){}
  59. #define C(i) (i?'<':'>')
  60.     void debug() {
  61.         //cout << C(sym[0]) << ' ' << len[0] << ' ' << C(sym[1]) << ' ' << len[1] << '\n';
  62.         //cout << len[0] << ' ' << len[1] << '\n';
  63.     }
  64. }val[maxn<<1];
  65.  
  66. int n, q;
  67. char w[maxn];
  68. void push(int i) {
  69.     if (i < n && val[i].fl) {
  70.         val[i].fl = false;
  71.         val[i<<1].flip();
  72.         val[i<<1|1].flip();
  73.     }
  74. }
  75. void update(int i) {
  76.     if (i < n) {
  77.         push(i);
  78.         val[i] = node(val[i<<1], val[i<<1|1]);
  79.     }
  80. }
  81. void flip(int l, int r) {
  82.     l += n, r += n;
  83.     int sl = l>>1, sr = r>>1;
  84.     for (;l < r;l>>=1, r>>=1) {
  85.         if (l&1) val[l++].flip();
  86.         if (r&1) val[--r].flip();
  87.     }
  88.     for (;sl;sl>>=1, sr>>=1)
  89.         update(sl), update(sr);
  90. }
  91. int query(int l, int r) {
  92.     l += n, r += n;
  93.     for (int i = 20;i > 0;--i)
  94.         push(l>>i), push(r>>i);
  95.  
  96.     node lr, rr;
  97.     for (;l < r;l>>=1, r>>=1) {
  98.         if (l&1) lr = node(lr, val[l++]);//,cout << "L ", lr.debug();
  99.         if (r&1) rr = node(val[--r], rr);//,cout << "R ", rr.debug();
  100.     }
  101.     lr = node(lr, rr);
  102.     lr.debug();
  103.     return lr.res();
  104. }
  105.  
  106. signed main(){
  107.     ios_base::sync_with_stdio(0), cin.tie(0);
  108.     cin >> n >> q >> w;
  109.     for (int i = 0;i < n;++i)
  110.         val[n+i] = node(w[i] == '<');
  111.     for (int i = n-1;i >= 1;--i)
  112.         val[i] = node(val[i<<1], val[i<<1|1]);
  113.     while (q--) {
  114.         int l, r;
  115.         cin >> l >> r;
  116.         --l, --r;
  117.         ++r;
  118.         flip(l, r);
  119.         cout << query(l, r) << '\n';
  120.     }
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement