#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
namespace Containers {
struct Segment {
long long l, r;
bool operator<(const Segment& rhs) const noexcept {
if (l == rhs.l) return r < rhs.r;
return l < rhs.l;
}
};
class DisjointSegmentContainer : public multiset<Segment> {
public:
vector<Segment> Add(Segment segm) {
auto intersecting = GetIntersecting(segm);
ll new_l = segm.l;
ll new_r = segm.r;
for (auto s : intersecting) {
new_l = min(new_l, s.l);
new_r = max(new_r, s.r);
this->erase(this->find(s));
}
this->insert({new_l, new_r});
return intersecting;
}
vector<Segment> GetIntersecting(Segment segm) {
vector<Segment> intersecting;
auto itr = this->insert(segm);
if (itr != this->begin()) {
auto prv = prev(itr);
while (prv->r >= segm.l) {
intersecting.push_back(*prv);
if (prv == this->begin()) {
break;
}
prv = prev(prv);
}
}
auto nxt = next(itr);
while (nxt != this->end() && nxt->l <= segm.r) {
intersecting.push_back(*nxt);
nxt = next(nxt);
}
this->erase(itr);
return intersecting;
}
void Remove(Segment segm) {
auto itr = this->find(segm);
if (itr == this->end()) {
assert(false);
}
this->erase(itr);
}
};
}
using SegmentContainer = Containers::DisjointSegmentContainer;
namespace Space2D {
struct Update2D {
int x1, x2;
int y1, y2;
Update2D(int x1, int x2, int y1, int y2) {
this->x1 = x1;
this->x2 = x2;
this->y1 = y1;
this->y2 = y2;
}
int value;
int updateId;
};
struct Update1D {
int x1, x2;
Update1D(Update2D u) {
this->x1 = u.x1;
this->x2 = u.x2;
this->value = u.value;
this->updateId = u.updateId;
}
int value;
int updateId;
};
struct NodeInfo {
int value = -1;
int updateId = -1;
static NodeInfo merge(NodeInfo a, NodeInfo b) {
return a.updateId > b.updateId ? a : b;
}
};
class SegTree1D {
struct Node {
int idl = -1, idr = -1;
NodeInfo lazy;
};
public:
SegTree1D(int minX, int maxX) {
this->minX = minX;
this->maxX = maxX;
makeNode();
}
inline int makeNode() {
int id = (int)tree.size();
tree.push_back({});
return id;
}
void set(Update1D u) {
set(0, minX, maxX, u);
}
NodeInfo query(int x) {
return query(0, minX, maxX, x);
}
private:
int set(int id, int x1, int x2, Update1D u) {
if (id == -1) {
id = makeNode();
}
if (u.x1 <= x1 && x2 <= u.x2) {
tree[id].lazy = {u.value, u.updateId};
} else {
int mid = (x1 + x2) / 2;
if (u.x1 <= mid) {
int idl = set(tree[id].idl, x1, mid, u);
tree[id].idl = idl;
}
if (mid < u.x2) {
int idr = set(tree[id].idr, mid + 1, x2, u);
tree[id].idr = idr;
}
}
return id;
}
NodeInfo query(int id, int x1, int x2, int x) {
if (id == -1) {
return {};
}
if (x1 == x2) {
return tree[id].lazy;
} else {
int mid = (x1 + x2) / 2;
if (x <= mid) {
auto info = query(tree[id].idl, x1, mid, x);
return NodeInfo::merge(info, tree[id].lazy);
} else {
auto info = query(tree[id].idr, mid + 1, x2, x);
return NodeInfo::merge(info, tree[id].lazy);
}
}
}
private:
vector<Node> tree;
int minX, maxX;
};
class SegTree2D {
struct Node {
int idl, idr;
SegTree1D tree;
Node(int minY, int maxY) : tree(minY, maxY) {
idl = idr = -1;
}
};
public:
SegTree2D(int minX, int maxX, int minY, int maxY) {
this->minX = minX;
this->maxX = maxX;
this->minY = minY;
this->maxY = maxY;
makeNode();
}
inline int makeNode() {
int id = (int)tree.size();
tree.push_back(Node(minY, maxY));
return id;
}
void set(Update2D u, int value) {
static int updateId = 0;
u.value = value;
u.updateId = ++updateId;
set(0, minX, maxX, u);
}
int query(int x, int y) {
return query(0, minX, maxX, x, y).value;
}
private:
int set(int id, int x1, int x2, Update2D u) {
if (id == -1) {
id = makeNode();
}
if (u.x1 <= x1 && x2 <= u.x2) {
tree[id].tree.set(u);
} else {
int mid = (x1 + x2) / 2;
if (u.x1 <= mid) {
int idl = set(tree[id].idl, x1, mid, u);
tree[id].idl = idl;
}
if (mid < u.x2) {
int idr = set(tree[id].idr, mid + 1, x2, u);
tree[id].idr = idr;
}
}
return id;
}
NodeInfo query(int id, int x1, int x2, int x, int y) {
if (id == -1) {
return {-1, -1};
}
if (x1 == x2) {
return tree[id].tree.query(y);
} else {
int mid = (x1 + x2) / 2;
NodeInfo info;
if (x <= mid) {
info = query(tree[id].idl, x1, mid, x, y);
} else {
info = query(tree[id].idr, mid + 1, x2, x, y);
}
// auto temp = tree[id].tree.query(y);
// cerr << x1 << " " << x2 << " " << temp.updateId << " " << temp.value << "\n";
return NodeInfo::merge(info, tree[id].tree.query(y));
}
}
private:
vector<Node> tree;
int minX, maxX;
int minY, maxY;
};
}
namespace std {
template<>
struct hash<pair<int, int>> {
size_t operator()(const pair<int, int>& p) const noexcept {
return (p.first << 16) ^ p.second;
}
};
}
class Fenwick2D {
public:
Fenwick2D(int maxX, int maxY) {
this->maxX = maxX;
this->maxY = maxY;
}
inline int getData(int x, int y) const {
auto itr = index.find({x, y});
return itr == index.end() ? 0 : data[itr->second];
}
inline int getIndex(int x, int y) {
auto itr = index.find({x, y});
if (itr == index.end()) {
int id = (int)data.size();
data.push_back(0);
index.insert(make_pair(make_pair(x, y), id));
return id;
}
return itr->second;
}
int query(int qx, int qy) const {
int answer = 0;
for (int x = qx; x > 0; x -= lsb(x)) {
for (int y = qy; y > 0; y -= lsb(y)) {
answer += getData(x, y);
}
}
return answer;
}
void update(int ux, int uy, int value) {
for (int x = ux; x <= maxX; x += lsb(x)) {
for (int y = uy; y <= maxY; y += lsb(y)) {
data[getIndex(x, y)] += value;
}
}
}
private:
int maxX, maxY;
unordered_map<pair<int, int>, int> index;
vector<int> data;
};
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
string str;
cin >> str;
str = " " + str;
vector<pair<ll, ll>> segments;
{
int i = 1;
while (i <= n) {
if (str[i] == '0') {
segments.push_back({i, i});
i++;
} else {
int j = i;
while (j <= n && str[j] == '1') {
j++;
}
segments.push_back({i, j});
i = j + 1;
}
}
if (segments.back().second != n + 1) {
segments.push_back({n + 1, n + 1});
}
}
SegmentContainer container;
Space2D::SegTree2D st(1, n + 1, 1, n + 1);
for (auto s : segments) {
container.Add({s.first, s.second});
st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
}
// cerr << st.query(1, 6);
Fenwick2D fen(n + 1, n + 1);
for (int qq = 1; qq <= q; qq++) {
string t;
cin >> t;
if (t == "query") {
int x, y;
cin >> x >> y;
int answer = fen.query(x, y);
// cerr << answer << "\n";
int lastId = st.query(x, y);
if (lastId != -1) {
answer += qq - lastId;
}
cout << answer << "\n";
} else {
int pos;
cin >> pos;
auto Remove = [&](Containers::Segment segm) {
int lastId = st.query(segm.l, segm.r);
assert(lastId != -1);
int value = qq - lastId;
// cerr << "Remove --> " << segm.l << " " << segm.r << " " << lastId << "\n";
fen.update(segm.l, segm.l, value);
fen.update(segm.r + 1, segm.l, -value);
fen.update(segm.l, segm.r + 1, -value);
fen.update(segm.r + 1, segm.r + 1, value);
st.set({segm.l, segm.r, segm.l, segm.r}, -1);
container.Remove(segm);
};
auto Add = [&](Containers::Segment segm) {
st.set({segm.l, segm.r, segm.l, segm.r}, qq);
// cerr << "Add --> " << segm.l << " " << segm.r << " " << qq << "\n";
container.Add(segm);
};
if (str[pos] == '1') {
auto intersecting = container.GetIntersecting({pos, pos});
assert(intersecting.size() == 1);
auto segm = intersecting[0];
Remove(segm);
Add({segm.l, pos});
Add({pos + 1, segm.r});
} else {
auto intersecting = container.GetIntersecting({pos, pos + 1});
assert(intersecting.size() == 2);
auto segm1 = intersecting[0];
auto segm2 = intersecting[1];
Remove(segm1);
Remove(segm2);
Add({segm1.l, segm2.r});
}
str[pos] = (str[pos] == '0' ? '1' : '0');
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:378:36: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
378 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~
street_lamps.cpp:378:45: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
378 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~~
street_lamps.cpp:378:55: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
378 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~
street_lamps.cpp:378:64: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
378 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:419:30: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
419 | st.set({segm.l, segm.r, segm.l, segm.r}, -1);
| ~~~~~^
street_lamps.cpp:419:38: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
419 | st.set({segm.l, segm.r, segm.l, segm.r}, -1);
| ~~~~~^
street_lamps.cpp:419:46: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
419 | st.set({segm.l, segm.r, segm.l, segm.r}, -1);
| ~~~~~^
street_lamps.cpp:419:54: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
419 | st.set({segm.l, segm.r, segm.l, segm.r}, -1);
| ~~~~~^
street_lamps.cpp: In lambda function:
street_lamps.cpp:424:30: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
424 | st.set({segm.l, segm.r, segm.l, segm.r}, qq);
| ~~~~~^
street_lamps.cpp:424:38: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
424 | st.set({segm.l, segm.r, segm.l, segm.r}, qq);
| ~~~~~^
street_lamps.cpp:424:46: warning: narrowing conversion of 'segm.Containers::Segment::l' from 'long long int' to 'int' [-Wnarrowing]
424 | st.set({segm.l, segm.r, segm.l, segm.r}, qq);
| ~~~~~^
street_lamps.cpp:424:54: warning: narrowing conversion of 'segm.Containers::Segment::r' from 'long long int' to 'int' [-Wnarrowing]
424 | st.set({segm.l, segm.r, segm.l, segm.r}, qq);
| ~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
4756 KB |
Output is correct |
| 2 |
Correct |
652 ms |
5632 KB |
Output is correct |
| 3 |
Correct |
1536 ms |
17064 KB |
Output is correct |
| 4 |
Execution timed out |
5116 ms |
351892 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
5078 ms |
440416 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
2076 ms |
171900 KB |
Output is correct |
| 6 |
Execution timed out |
5034 ms |
374420 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
402 ms |
4756 KB |
Output is correct |
| 9 |
Correct |
652 ms |
5632 KB |
Output is correct |
| 10 |
Correct |
1536 ms |
17064 KB |
Output is correct |
| 11 |
Execution timed out |
5116 ms |
351892 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
