Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define pb emplace_back
- using namespace std;
- using ll = long long;
- const int maxn = 500010;
- struct node {
- bool fl = false, sm = false;
- int ans[2]{1, 1}, sym[2]{}, len[2]{}, sec[2]{1, 1};
- node(int v) {
- len[0] = len[1] = 1;
- sym[0] = sym[1] = v;
- sm = true;
- }
- int res() {
- return ans[0];
- }
- node(node a, node b) {
- bool rt = false;
- if (!a.len[0]) (*this) = b, rt = true;
- if (!b.len[0]) (*this) = a, rt = true;
- if (rt) return;
- for (int i : {0, 1})
- ans[i] = max(a.ans[i], b.ans[i]);
- sym[0] = a.sym[0], sym[1] = b.sym[1];
- len[0] = a.len[0], len[1] = b.len[1];
- sec[0] = a.sec[0], sec[1] = b.sec[1];
- if (a.sym[1] == b.sym[0]) {
- //cout << "MID SAME \n";
- {
- auto &v = ans[ a.sym[1]^1 ];
- v = max(v, a.sec[1] + b.len[0] );
- }
- {
- auto &v = ans[ a.sym[1] ];
- v = max(v, b.sec[0] + a.len[1] );
- }
- }
- else
- ans[a.sym[1]] = max(ans[a.sym[1]], a.len[1] + b.len[0]);
- if (a.sm)
- len[0] += b.sym[0] == a.sym[0] ? b.len[0] : 0, sec[0] = b.sec[0] + a.len[0];
- if (b.sm)
- len[1] += b.sym[0] == a.sym[1] ? a.len[1] : 0, sec[1] = a.sec[1] + b.len[0];
- if (a.sm && b.sm && a.sym[0] == b.sym[0]) {
- sm = true;
- //cout << "SAME " << a.len[0] + b.len[0] << '\n';
- len[0] = len[1] = a.len[0] + b.len[0];
- sym[0] = sym[1] = a.sym[0];
- }
- }
- void flip() {
- fl ^= 1;
- swap(ans[0], ans[1]);
- sym[0] ^= 1, sym[1] ^= 1;
- //swap(sym[0], sym[1]);
- }
- node(){}
- #define C(i) (i?'<':'>')
- void debug() {
- //cout << C(sym[0]) << ' ' << len[0] << ' ' << C(sym[1]) << ' ' << len[1] << '\n';
- //cout << len[0] << ' ' << len[1] << '\n';
- }
- }val[maxn<<1];
- int n, q;
- char w[maxn];
- void push(int i) {
- if (i < n && val[i].fl) {
- val[i].fl = false;
- val[i<<1].flip();
- val[i<<1|1].flip();
- }
- }
- void update(int i) {
- if (i < n) {
- push(i);
- val[i] = node(val[i<<1], val[i<<1|1]);
- }
- }
- void flip(int l, int r) {
- l += n, r += n;
- int sl = l>>1, sr = r>>1;
- for (;l < r;l>>=1, r>>=1) {
- if (l&1) val[l++].flip();
- if (r&1) val[--r].flip();
- }
- for (;sl;sl>>=1, sr>>=1)
- update(sl), update(sr);
- }
- int query(int l, int r) {
- l += n, r += n;
- for (int i = 20;i > 0;--i)
- push(l>>i), push(r>>i);
- node lr, rr;
- for (;l < r;l>>=1, r>>=1) {
- if (l&1) lr = node(lr, val[l++]);//,cout << "L ", lr.debug();
- if (r&1) rr = node(val[--r], rr);//,cout << "R ", rr.debug();
- }
- lr = node(lr, rr);
- lr.debug();
- return lr.res();
- }
- signed main(){
- ios_base::sync_with_stdio(0), cin.tie(0);
- cin >> n >> q >> w;
- for (int i = 0;i < n;++i)
- val[n+i] = node(w[i] == '<');
- for (int i = n-1;i >= 1;--i)
- val[i] = node(val[i<<1], val[i<<1|1]);
- while (q--) {
- int l, r;
- cin >> l >> r;
- --l, --r;
- ++r;
- flip(l, r);
- cout << query(l, r) << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement