#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;
const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
#define FAST ios_base::sync_with_stdio(0)
#define FASTIN cin.tie(0)
#define FASTOUT cout.tie(0)
#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)
#define pr(x) cout << x << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": " << endl; for(auto it : v) cout << it << " "; cout << endl;
#define wprvv(v) cout << #v << ": " << endl; for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define rep(i,s,e) for(ll i = s; i < e; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
/*
Solution:
Each moment we have segments of reachable nodes.
We will store them in a set.
We will also store their start time.
Each time we get a flip, we change (at most) 2 segments.
So we can take them out and make (at most) 2 other segments.
Each time we get a query of (a, b), we have to find the number of segments (x, y) that fufill:
x <= a <= b <= y
This can be done using persistent segment tree ig.
*/
const ll bval = 0;
struct tr {
ll l, r, m, v = bval;
tr* lp = nullptr, * rp = nullptr;
tr(tr* t) : l(t->l), r(t->r), m(t->m), v(t->v), lp(t->lp), rp(t->rp) {}
tr() {}
tr(ll l, ll r) : l(l), r(r), m((l + r) / 2) {
if (l + 1 >= r) return;
lp = new tr(l, m);
rp = new tr(m, r);
}
void pull() {
v = lp->v + rp->v;
}
tr* up(ll i, ll x) {
tr* t = new tr();
t->l = l, t->r = r, t->m = m, t->v = v;
t->lp = lp;
t->rp = rp;
if (l + 1 >= r) {
t->v += x;
//v = x;
return t;
}
if (i < m) {
t->lp = lp->up(i, x);
}
else {
t->rp = rp->up(i, x);
}
t->pull();
return t;
}
ll q(ll f, ll t) {
if (t <= l || f >= r) return bval;
if (f <= l && r <= t) return v;
return lp->q(f, t) + rp->q(f, t);
}
};
vector<tr*> roots;
ll n, q;
vb arr;
/*
Our set. {{start, end}, insertion time}
*/
set< pair<pair<ll, ll>, ll> > segs;
vector<pair<pll, ll>> done;
void pr_seg(pair<pll, ll> p)
{
cout << "start: " << p.first.first << ", end: " << p.first.second << ", insertion time: " << p.second << endl;
}
void insert_per(set<pair<pll, ll>>::iterator &p, ll time)
{
ll s = p->first.first;
ll e = p->first.second;
ll v = time - p->second;
roots[s]->up(e, v);
}
void unite_case(ll i, ll time)
{
arr[i] = 1;
//segs.insert({ { i, i }, time });
ll s = i, e = i;
auto right = segs.lower_bound({ {s, e}, (ll)0 });
bool erright = false, erleft = false;
if (right != segs.end()) {
if (right->first.first == e + 1) {
erright = true;
// TODO: insert it in the segment
//done.push_back(*right);
//done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
insert_per(right, time);
e = right->first.second;
}
}
auto left = segs.end();
if (right != segs.begin())
{
left = prev(right);
if (left != segs.end()) {
if (left->first.second == s - 1) {
erleft = true;
// TODO: insert it in the segment
//done.push_back(*left);
//done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
insert_per(left, time);
s = left->first.first;
}
}
}
//wpr(s);
//wpr(e);
segs.insert({ { s, e }, time });
if (erright) {
segs.erase(right);
}
if (erleft) {
segs.erase(left);
}
}
void divide_case(ll i, ll time)
{
arr[i] = 0;
auto cur = segs.lower_bound({ {i+1, 0}, (ll)0 });
if (cur == segs.begin()) return;
cur = prev(cur);
ll s = cur->first.first;
ll e = cur->first.second;
if (e < i) return;
// TODO: insert it in the segment
if(s <= i - 1) segs.insert({ {s, i - 1}, time });
if(i + 1 <= e) segs.insert({ {i+1, e}, time });
//done.push_back(*cur);
//done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
insert_per(cur, time);
segs.erase(cur);
}
void pr_segs()
{
for (auto &it : segs) {
pr_seg(it);
}
}
void solve()
{
cin >> n >> q;
roots.push_back(new tr(0, n));
rep(i, 1, n) {
//pr("hiiii");
roots.push_back(new tr(roots[roots.size() - 1]));
}
//wpr(roots.size());
arr.resize(n);
rep(i, 0, n) {
char c;
cin >> c;
arr[i] = c - '0';
}
//wprv(arr);
{
ll i = 0;
while (i < n) {
if (arr[i] == 0) {
i++;
continue;
}
ll s = i;
while (i+1 < n && arr[i+1] == 1) {
i++;
}
//s.insert({ {s, i}, (ll)0 });
segs.insert({ {s, i}, (ll)0 });
i++;
}
}
rep(t, 1, q + 1) {
string type;
cin >> type;
if (type == "toggle") {
ll i; cin >> i; i--;
if (arr[i] == 0) unite_case(i, t);
else divide_case(i, t);
}
else {
ll a, b;
cin >> a >> b;
a--, b -= 2;
ll res = 0;
auto it = segs.upper_bound({ {b+1, 0}, 0 });
if (it != segs.begin()) {
it = prev(it);
if (it != segs.end()) {
//pr("printing it:");
//pr_seg(*it);
if (it->first.first <= a && it->first.second >= b) {
res += t - it->second;
}
}
}
//wpr(a);
//wpr(roots.size());
res += roots[a]->q(0, b+1);
//pr("printing done:");
/*
for (auto& v : done) {
//pr_seg(v);
if (v.first.first <= a && v.first.second >= b) {
res += v.second;
}
}
*/
//pr("---------------------------");
pr(res);
}
//pr_segs();
}
}
int main()
{
FAST;
FASTIN; FASTOUT;
solve();
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
7 1000
1011011
7 1000
0000000
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
463 ms |
65640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1096 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
