Submission #67792384

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int N = 5e5 + 10;

struct Node{
	int l, r;
	char ch_l, ch_r;
	int prelen, suflen;
	int max_seglen;
}tr[N << 2];

struct SegTree{

	#define lc p<<1
	#define rc p<<1|1

	void pushup(int p){
		tr[p].ch_l = tr[lc].ch_l;
		tr[p].ch_r = tr[rc].ch_r;
		tr[p].prelen = tr[lc].prelen;
		if(tr[lc].prelen == tr[lc].r - tr[lc].l + 1 && tr[rc].ch_l == tr[lc].ch_r){
			tr[p].prelen += tr[rc].prelen;
		}
		tr[p].suflen = tr[rc].suflen;
		if(tr[rc].suflen == tr[rc].r - tr[rc].l + 1 && tr[rc].ch_l == tr[lc].ch_r){
			tr[p].suflen += tr[lc].suflen;
		}
		tr[p].max_seglen = max(tr[lc].max_seglen, tr[rc].max_seglen);
		if(tr[lc].ch_r == tr[rc].ch_l){
			tr[p].max_seglen = max(tr[p].max_seglen, tr[lc].suflen + tr[rc].prelen);
		}
	}

	void build(int p, int l, int r, auto& arr){
		tr[p] = {l, r, arr[l], arr[l], 1, 1, 1};
		if(l == r) return;
		int mid = l + r >> 1;
		build(lc, l, mid, arr);
		build(rc, mid + 1, r, arr);
		pushup(p);
	}

	void update(int p, int l, int r, char ch){
		if(tr[p].l == l && r == tr[p].r){
			tr[p].ch_l = tr[p].ch_r = ch;
			return;
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(l <= mid) update(lc, l, r, ch);
		if(r > mid) update(rc, l, r, ch);
		pushup(p);
	}

	Node query_max_seglen(int p, int l, int r){
		if(l <= tr[p].l && tr[p].r <= r){
			return tr[p];
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(r <= mid) return query_max_seglen(lc, l, r);
		if(l > mid) return query_max_seglen(rc, l, r);
		Node L = query_max_seglen(lc, l, r);
		Node R = query_max_seglen(rc, l, r);
		Node t;
		t.ch_l = L.ch_l;
		t.ch_r = R.ch_r;
		t.prelen = L.prelen;
		if(L.prelen == L.r - L.l + 1 && R.ch_l == L.ch_r){
			t.prelen += R.prelen;
		}
		t.suflen = R.suflen;
		if(R.suflen == R.r - R.l + 1 && R.ch_l == L.ch_r){
			t.suflen += L.suflen;
		}
		t.max_seglen = max(L.max_seglen, R.max_seglen);
		if(R.ch_l == L.ch_r){
			t.max_seglen = max(t.max_seglen, L.suflen + R.prelen);
		}
		return t;
	}
};

int n, q;
string str;

SegTree seg;

void solve()
{
	cin >> n >> q;
	cin >> str;
	str = " " + str;

	seg.build(1, 1, n, str);

	while(q --){
		int op;
		cin >> op;
		if(op == 1){
			int i;
			char x;
			cin >> i >> x;
			seg.update(1, i, i, x);
		}
		else{
			int l, r;
			cin >> l >> r;
			cout << seg.query_max_seglen(1, l, r).max_seglen << endl;
		}
	}
}


signed main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	// int T=1; cin>>T; while(T--)
	solve();
	return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void SegTree::update(int, int, int, char)’:
Main.cpp:59:35: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   59 |                 int mid = tr[p].l + tr[p].r >> 1;
      |                           ~~~~~~~~^~~~~~~~~
Main.cpp: In member function ‘Node SegTree::query_max_seglen(int, int, int)’:
Main.cpp:69:35: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   69 |                 int mid = tr[p].l + tr[p].r >> 1;
      |                           ~~~~~~~~^~~~~~~~~
Main.cpp: In instantiation of ‘void SegTree::build(int, int, int, auto:53&) [with auto:53 = std::__cxx11::basic_string<char>]’:
Main.cpp:104:11:   required from here
Main.cpp:48:29: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   48 |                 int mid = l + r >> 1;
      |                           ~~^~~

Judge Result