#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 300'000;
int n, q, s[N + 10];
int type[N + 10], a[N + 10], b[N + 10];
int ans[N + 10], val[N + 10], typeQuery[N + 10];
int x1[N + 10], x2[N + 10], y1[N + 10], y2[N + 10];
void readInput() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
s[i] = (c == '1');
}
for (int i = 1; i <= q; i++) {
string s;
cin >> s;
if (s[0] == 't') {
type[i] = 0;
cin >> a[i];
}
else {
type[i] = 1;
cin >> a[i] >> b[i];
b[i]--;
}
}
}
struct Segment {
set<int> s1[2], s2[2];
void init() {
for (int i = 1; i <= n; i++) {
s1[s[i]].insert(i);
s2[s[i]].insert(-i);
}
}
void toggle(int i) {
s1[s[i]].erase(i);
s2[s[i]].erase(-i);
s[i] ^= 1;
s1[s[i]].insert(i);
s2[s[i]].insert(-i);
}
int getNext(int idx, int t) {
auto au = s1[t].upper_bound(idx);
return au == s1[t].end()? n + 1: *au;
}
int getLast(int idx, int t) {
auto au = s2[t].upper_bound(-idx);
return au == s2[t].end()? 0: -(*au);
}
bool isPath(int a, int b) {
int k = getNext(a - 1, 0);
return b < k;
}
} seg;
struct Fenwick2D {
vector<int> fen[N + 10], vals[N + 10];
void updateRow(int x, int y, int val) {
int idx = lower_bound(vals[x].begin(), vals[x].end(), y) - vals[x].begin();
/*if (vals[x][idx] != y)
cout << "bad " << endl;*/
for (; idx < vals[x].size(); idx += idx & -idx)
fen[x][idx] += val;
}
void updatePoint(int x, int y, int val) {
if (x == 0 || y == 0)
return;
for (; x <= n; x += x & -x)
updateRow(x, y, val);
}
void update(int x1, int x2, int y1, int y2, int val) {
updatePoint(x2, y2, val);
updatePoint(x2, y1 - 1, -val);
updatePoint(x1 - 1, y2, -val);
updatePoint(x1 - 1, y2 - 1, val);
}
void addPoint(int x, int y) {
if (x == 0 || y == 0)
return;
for (; x <= n; x += x & -x)
vals[x].push_back(y);
for (; x; x -= x & -x)
vals[x].push_back(y);
}
void addQueryChange(int x1, int x2, int y1, int y2) {
addPoint(x2, y2);
addPoint(x2, y1 - 1);
addPoint(x1 - 1, y2);
addPoint(x1 - 1, y1 - 1);
}
void addQueryGet(int x, int y) {
addQueryChange(x, n, y, n);
}
void init() {
for (int i = 1; i <= n; i++) {
vals[i].push_back(0);
sort(vals[i].begin(), vals[i].end());
vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
fen[i].resize(vals[i].size() + 3);
}
}
int getRow(int x, int idx) {
if (idx == 0)
return 0;
int t = idx;
idx = lower_bound(vals[x].begin(), vals[x].end(), idx) - vals[x].begin();
/*if (vals[x][idx] != t)
cout << "no " << endl;*/
int res = 0;
for (; idx; idx -= idx & -idx)
res += fen[x][idx];
return res;
}
int get(int x, int l, int r) {
if (x == 0)
return 0;
int res = 0;
for (; x; x -= x & -x)
res += getRow(x, r) - getRow(x, l - 1);
return res;
}
int get(int x1, int x2, int y1, int y2) {
return get(x2, y1, y2) - get(x1 - 1, y1, y2);
}
int get(int x, int y) {
return get(x, n, y, n);
}
} fen;
void change(int idx, int idQuery, int d) {
int l = seg.getLast(idx, 0);
int r = seg.getNext(idx, 0);
fen.addQueryChange(l + 1, idx, idx, r - 1);
typeQuery[idQuery] = 0;
x1[idQuery] = l + 1;
x2[idQuery] = idx;
y1[idQuery] = idx;
y2[idQuery] = r - 1;
val[idQuery] = -d * idQuery;
//cout << l << ' ' << idx << ' ' << r << '\n';
}
void initQueryChange(int idx, int idQuery) {
if (!s[idx])
change(idx, idQuery, 1);
else
change(idx, idQuery, -1);
seg.toggle(idx);
}
void initQueryGet(int l, int r, int idQuery) {
typeQuery[idQuery] = 1;
x1[idQuery] = l;
y1[idQuery] = r;
val[idQuery] = (seg.isPath(l, r)? idQuery: 0);
fen.addQueryGet(l, r);
//cout << idQuery << ": " << seg.isPath(l, r) << '\n';
}
void init() {
seg.init();
for (int i = 1; i <= q; i++)
if (type[i] == 0)
initQueryChange(a[i], i);
else
initQueryGet(a[i], b[i], i);
fen.init();
}
void solve() {
for (int i = 1; i <= q; i++)
if (type[i] == 0)
fen.update(x1[i], x2[i], y1[i], y2[i], val[i]);
else
ans[i] = fen.get(x1[i], y1[i]) + val[i];
}
void writeOutput() {
for (int i = 1; i <= q; i++)
if (type[i])
cout << ans[i] << '\n';
cout.flush();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
init();
solve();
writeOutput();
return 0;
}
Compilation message
street_lamps.cpp: In member function 'void Fenwick2D::updateRow(int, int, int)':
street_lamps.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (; idx < vals[x].size(); idx += idx & -idx)
| ~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'int Fenwick2D::getRow(int, int)':
street_lamps.cpp:114:13: warning: unused variable 't' [-Wunused-variable]
114 | int t = idx;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
338 ms |
58800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
27484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
