| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 535699 | lunchbox | 가로등 (APIO19_street_lamps) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#define N 300000
#define L 18
struct T {
int x;
T *l, *r;
};
struct T *node() {
T *t = (T *) calloc(1, sizeof *t);
t->x = 0;
t->l = t->r = NULL;
return t;
}
void st_update(struct T *t, int l, int r, int i, int x) {
int m;
if (l == r) {
t->x += x;
return;
}
m = (l + r) / 2;
if (i <= m) {
if (t->l == NULL)
t->l = node();
st_update(t->l, l, m, i, x);
} else {
if (t->r == NULL)
t->r = node();
st_update(t->r, m + 1, r, i, x);
}
t->x = (t->l == NULL ? 0 : t->l->x) + (t->r == NULL ? 0 : t->r->x);
}
int st_query(struct T *t, int l, int r, int ql, int qr) {
int m;
if (t == NULL)
return 0;
if (ql <= l && r <= qr)
return t->x;
if (qr < l || ql > r)
return 0;
m = (l + r) / 2;
return st_query(t->l, l, m, ql, qr) + st_query(t->r, m + 1, r, ql, qr);
}
struct T *ft1[N + 1];
int ft2[N], n;
void ft1_update(int i, int j, int x) {
if (j > n)
return;
while (i <= n) {
st_update(ft1[i], 0, n, j, x);
i |= i + 1;
}
}
int ft1_query(int i, int j) {
int sum = 0;
while (i >= 0) {
sum += st_query(ft1[i], 0, n, 0, j);
i &= i + 1, i--;
}
return sum;
}
void ft2_update(int i, int x) {
while (i < n) {
ft2[i] += x;
i |= i + 1;
}
}
int ft2_query(int i) {
int sum = 0;
while (i >= 0) {
sum += ft2[i];
i &= i + 1, i--;
}
return sum;
}
int find_left(int i) {
int i_ = i, x = ft2_query(i - 1);
for (int m = 1 << L; m >= 1; m >>= 1)
if (i_ - m >= 0 && x - ft2_query(i_ - m - 1) == i - (i_ - m))
i_ -= m;
return i_;
}
int find_right(int i) {
int i_ = i, x = ft2_query(i - 1);
for (int m = 1 << L; m >= 1; m >>= 1)
if (i_ + m <= n && ft2_query(i_ + m - 1) - x == (i_ + m) - i)
i_ += m;
return i_;
}
void update(int l, int l_, int r, int r_, int x) {
ft1_update(l, r, x);
ft1_update(l, r_ + 1, -x);
ft1_update(l_ + 1, r, -x);
ft1_update(l_ + 1, r_ + 1, x);
}
int main() {
static char cc[N];
int q;
scanf("%d%d", &n, &q);
for (int i = 0; i <= n; i++)
ft1[i] = node();
scanf("%s", cc);
for (int i = 0; i < n; i++)
if (cc[i] == '1')
ft2_update(i, +1);
for (int h = 1; h <= q; h++) {
static char s[8];
scanf("%s", s);
if (s[0] == 'q') {
int l, r, sum;
scanf("%d%d", &l, &r), l--, r--;
sum = ft1_query(l, r);
if (ft2_query(r - 1) - ft2_query(l - 1) == r - l)
sum += h;
printf("%d\n", sum);
} else {
int i;
scanf("%d", &i), i--;
if (cc[i] == '1') {
update(find_left(i), i, i + 1, find_right(i + 1), +h);
ft2_update(i, -1);
cc[i] = '0';
} else {
update(find_left(i), i, i + 1, find_right(i + 1), -h);
ft2_update(i, +1);
cc[i] = '1';
}
}
}
return 0;
}