#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
namespace Containers {
template<typename T>
struct Segment {
T l, r;
bool operator<(const Segment& rhs) const noexcept {
if (l == rhs.l) return r < rhs.r;
return l < rhs.l;
}
};
template<typename T>
class DisjointSegmentContainer : public multiset<Segment<T>> {
public:
vector<Segment<T>> Add(Segment<T> segm) {
auto intersecting = GetIntersecting(segm);
T new_l = segm.l;
T 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<T>> GetIntersecting(Segment<T> segm) {
vector<Segment<T>> 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<T> segm) {
auto itr = this->find(segm);
if (itr == this->end()) {
assert(false);
}
this->erase(itr);
}
};
}
using SegmentContainer = Containers::DisjointSegmentContainer<int>;
using Segment = Containers::Segment<int>;
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;
}
};
}
namespace UniqueIndexGenerator {
constexpr int SMALL_X = (int) 4e5;
template<typename _Derived, typename T = typename _Derived::type>
class BaseGenerator {
public:
inline int getIndex(T x, T y) const {
return reinterpret_cast<const _Derived*>(this)->getIndex(x, y);
}
inline int getOrAddIndex(T x, T y) {
return reinterpret_cast<_Derived*>(this)->getOrAddIndex(x, y);
}
protected:
inline int nextID() const noexcept {
static int ID = -1;
return ++ID;
}
};
template<typename T>
class SmallXGenerator : public BaseGenerator<SmallXGenerator<T>, T> {
public:
using type = T;
SmallXGenerator(int maxX, int maxY) {
index.resize(maxX + 1);
}
inline int getIndex(int x, int y) const {
auto itr = index[x].find(y);
return itr == index[x].end() ? -1 : itr->second;
}
inline int getOrAddIndex(int x, int y) {
auto itr = index[x].find(y);
if (itr == index[x].end()) {
int id = this->nextID();
index[x].insert({y, id});
return id;
}
return itr->second;
}
private:
vector<unordered_map<T, int>> index;
};
template<typename T>
class GeneralGenerator : public BaseGenerator<GeneralGenerator<T>, T> {
public:
using type = T;
GeneralGenerator(T maxX, T maxY) {}
inline int getIndex(T x, T y) const {
auto itr = index.find({x, y});
return itr == index.end() ? -1 : itr->second;
}
inline int getOrAddIndex(T x, T y) {
auto itr = index.find({x, y});
if (itr == index.end()) {
int id = this->nextID();
index.insert(make_pair(make_pair(x, y), id));
return id;
}
return itr->second;
}
private:
unordered_map<pair<T, T>, int> index;
};
}
template<typename _TGenerator>
class Fenwick2D {
using T = typename _TGenerator::type;
public:
Fenwick2D(T maxX, T maxY, UniqueIndexGenerator::BaseGenerator<_TGenerator>& uniqueGenerator)
: uniqueGenerator(uniqueGenerator) {
this->maxX = maxX;
this->maxY = maxY;
}
inline void reserve(int size) {
data.resize(size + 1);
}
inline T getData(T x, T y) const {
int id = uniqueGenerator.getIndex(x, y);
return id == -1 ? 0 : data[id];
}
inline int getOrAddIndex(T x, T y) {
int id = uniqueGenerator.getOrAddIndex(x, y);
if ((int)data.size() <= id) {
data.resize(id + 1);
}
return id;
}
T query(T qx, T qy) const {
T answer = 0;
for (T x = qx; x > 0; x -= lsb(x)) {
for (T y = qy; y > 0; y -= lsb(y)) {
answer += getData(x, y);
}
}
return answer;
}
void update(T ux, T uy, T value) {
for (T x = ux; x <= maxX; x += lsb(x)) {
for (T y = uy; y <= maxY; y += lsb(y)) {
data[getOrAddIndex(x, y)] += value;
}
}
}
private:
T maxX, maxY;
UniqueIndexGenerator::BaseGenerator<_TGenerator>& uniqueGenerator;
vector<T> 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);
UniqueIndexGenerator::SmallXGenerator<int> generator(n + 1, n + 1);
Fenwick2D<decltype(generator)> fen(n + 1, n + 1, generator);
fen.reserve(q * 17 * 17);
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 = [&](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 = [&](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:463:26: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
463 | container.Add({s.first, s.second});
| ~~^~~~~
street_lamps.cpp:463:35: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
463 | container.Add({s.first, s.second});
| ~~^~~~~~
street_lamps.cpp:464:36: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
464 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~
street_lamps.cpp:464:45: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
464 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~~
street_lamps.cpp:464:55: warning: narrowing conversion of 's.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
464 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~
street_lamps.cpp:464:64: warning: narrowing conversion of 's.std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
464 | st.set(Space2D::Update2D{s.first, s.second, s.first, s.second}, 0);
| ~~^~~~~~
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
467 ms |
341116 KB |
Output is correct |
| 2 |
Correct |
650 ms |
341692 KB |
Output is correct |
| 3 |
Correct |
1442 ms |
352232 KB |
Output is correct |
| 4 |
Runtime error |
364 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 5 |
Runtime error |
378 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2136 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1299 ms |
522812 KB |
Output is correct |
| 6 |
Runtime error |
343 ms |
524288 KB |
Execution killed with signal 9 |
| 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 |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
467 ms |
341116 KB |
Output is correct |
| 9 |
Correct |
650 ms |
341692 KB |
Output is correct |
| 10 |
Correct |
1442 ms |
352232 KB |
Output is correct |
| 11 |
Runtime error |
364 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
