Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <iomanip>
- #include <queue>
- #include <cmath>
- #include <algorithm>
- #include <tuple>
- #include <iomanip>
- #include <stdio.h>
- #include <numeric>
- #include <map>
- #include <bitset>
- #include <set>
- #include <stack>
- #include <queue>
- /*
- #pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")
- #pragma GCC optimize("section-anchors")
- #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
- #pragma GCC optimize("vpt")
- #pragma GCC optimize("rename-registers")
- #pragma GCC optimize("move-loop-invariants")
- #pragma GCC optimize("unswitch-loops")
- #pragma GCC optimize("function-sections")
- #pragma GCC optimize("data-sections")
- #pragma GCC optimize("branch-target-load-optimize")
- #pragma GCC optimize("branch-target-load-optimize2")
- #pragma GCC optimize("btr-bb-exclusive")
- */
- #define int long long
- #define ll long long
- #define ull unsigned long long
- #define all(a) a.begin(), a.end()
- #define pii pair<int, int>
- #define pb push_back
- #define ld long double
- using namespace std;
- //const int INF = 1e13;
- //const int mod = 2600000069;
- //const int p = 179;
- struct zeroes {
- int left, right, ans, size;
- zeroes(int ans_, int left_, int right_, int size_) {
- ans = ans_;
- left = left_;
- right = right_;
- size = size_;
- }
- zeroes() {
- ans = 0;
- left = 0;
- right = 0;
- size = 0;
- }
- };
- zeroes merge(zeroes a, zeroes b) {
- zeroes c;
- c.size = a.size + b.size;
- c.ans = max(a.ans, max(b.ans, a.right + b.left));
- c.right = b.right;
- c.left = a.left;
- if (a.size == a.left && b.size == b.left) {
- c.left = c.size;
- c.right = c.size;
- }
- if (a.left == a.size) {
- c.left = a.size + b.left;
- }
- if (b.right == b.size) {
- c.right = b.size + a.right;
- }
- c.ans = max(c.ans, max(c.left, c.right));
- return c;
- }
- vector<zeroes> t;
- vector<int> a;
- void build(int v, int l, int r) {
- if (r - l == 1) {
- if (a[l] == 0) {
- t[v] = zeroes(1, 1, 1, 1);
- } else {
- t[v] = zeroes(0, 0, 0, 1);
- }
- return;
- }
- int mid = (l + r) / 2;
- build(2 * v + 1, l, mid);
- build(2 * v + 2, mid, r);
- t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
- }
- zeroes get_ans(int v, int l, int r, int askl, int askr) {
- if (l >= askr || r <= askl) {
- return zeroes();
- }
- if (l >= askl && r <= askr) {
- return t[v];
- }
- int mid = (l + r) / 2;
- return merge(get_ans(2 * v + 1, l, mid, askl, askr), get_ans(2 * v + 2, mid, r, askl, askr));
- }
- void update(int v, int l, int r, int pos, int val) {
- if (r - l == 1) {
- if (val == 0) {
- t[v] = zeroes(1, 1, 1, 1);
- } else {
- t[v] = zeroes(0, 0, 0, 1);
- }
- return;
- }
- int mid = (l + r) / 2;
- if (pos < mid) {
- update(2 * v + 1, l, mid, pos, val);
- } else {
- update(2 * v + 2, mid, r, pos, val);
- }
- t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- t.resize(4 * n);
- a.resize(n);
- for (int i = 0; i < n; i++) cin >> a[i];
- build(0, 0, n);
- int q;
- cin >> q;
- string type;
- int l, r;
- while (q--) {
- cin >> type >> l >> r;
- --l;
- if (type == "QUERY") {
- cout << get_ans(0, 0, n, l, r).ans << "\n";
- } else {
- update(0, 0, n, l, r);
- }
- }
- }
- /*
- 5
- 328 0 0 0 0
- 5
- QUERY 1 3
- UPDATE 2 832
- QUERY 3 3
- QUERY 2 3
- UPDATE 2 0
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement