이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
street_lamps.c:9:2: error: unknown type name 'T'
9 | T *l, *r;
| ^
street_lamps.c: In function 'node':
street_lamps.c:13:2: error: unknown type name 'T'; use 'struct' keyword to refer to the type
13 | T *t = (T *) calloc(1, sizeof *t);
| ^
| struct
street_lamps.c:13:10: error: 'T' undeclared (first use in this function)
13 | T *t = (T *) calloc(1, sizeof *t);
| ^
street_lamps.c:13:10: note: each undeclared identifier is reported only once for each function it appears in
street_lamps.c:13:13: error: expected expression before ')' token
13 | T *t = (T *) calloc(1, sizeof *t);
| ^
street_lamps.c:15:3: error: request for member 'x' in something not a structure or union
15 | t->x = 0;
| ^~
street_lamps.c:16:3: error: request for member 'l' in something not a structure or union
16 | t->l = t->r = NULL;
| ^~
street_lamps.c:16:10: error: request for member 'r' in something not a structure or union
16 | t->l = t->r = NULL;
| ^~
street_lamps.c:17:9: warning: returning 'int *' from a function with incompatible return type 'struct T *' [-Wincompatible-pointer-types]
17 | return t;
| ^
street_lamps.c: In function 'st_update':
street_lamps.c:30:9: warning: assignment to 'int *' from incompatible pointer type 'struct T *' [-Wincompatible-pointer-types]
30 | t->l = node();
| ^
street_lamps.c:31:14: warning: passing argument 1 of 'st_update' from incompatible pointer type [-Wincompatible-pointer-types]
31 | st_update(t->l, l, m, i, x);
| ~^~~
| |
| int *
street_lamps.c:20:26: note: expected 'struct T *' but argument is of type 'int *'
20 | void st_update(struct T *t, int l, int r, int i, int x) {
| ~~~~~~~~~~^
street_lamps.c:34:9: warning: assignment to 'int *' from incompatible pointer type 'struct T *' [-Wincompatible-pointer-types]
34 | t->r = node();
| ^
street_lamps.c:35:14: warning: passing argument 1 of 'st_update' from incompatible pointer type [-Wincompatible-pointer-types]
35 | st_update(t->r, m + 1, r, i, x);
| ~^~~
| |
| int *
street_lamps.c:20:26: note: expected 'struct T *' but argument is of type 'int *'
20 | void st_update(struct T *t, int l, int r, int i, int x) {
| ~~~~~~~~~~^
street_lamps.c:37:33: error: request for member 'x' in something not a structure or union
37 | t->x = (t->l == NULL ? 0 : t->l->x) + (t->r == NULL ? 0 : t->r->x);
| ^~
street_lamps.c:37:64: error: request for member 'x' in something not a structure or union
37 | t->x = (t->l == NULL ? 0 : t->l->x) + (t->r == NULL ? 0 : t->r->x);
| ^~
street_lamps.c: In function 'st_query':
street_lamps.c:50:19: warning: passing argument 1 of 'st_query' from incompatible pointer type [-Wincompatible-pointer-types]
50 | return st_query(t->l, l, m, ql, qr) + st_query(t->r, m + 1, r, ql, qr);
| ~^~~
| |
| int *
street_lamps.c:40:24: note: expected 'struct T *' but argument is of type 'int *'
40 | int st_query(struct T *t, int l, int r, int ql, int qr) {
| ~~~~~~~~~~^
street_lamps.c:50:50: warning: passing argument 1 of 'st_query' from incompatible pointer type [-Wincompatible-pointer-types]
50 | return st_query(t->l, l, m, ql, qr) + st_query(t->r, m + 1, r, ql, qr);
| ~^~~
| |
| int *
street_lamps.c:40:24: note: expected 'struct T *' but argument is of type 'int *'
40 | int st_query(struct T *t, int l, int r, int ql, int qr) {
| ~~~~~~~~~~^
street_lamps.c: In function 'main':
street_lamps.c:121:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
street_lamps.c:124:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%s", cc);
| ^~~~~~~~~~~~~~~
street_lamps.c:131:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | scanf("%s", s);
| ^~~~~~~~~~~~~~
street_lamps.c:135:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d%d", &l, &r), l--, r--;
| ^~~~~~~~~~~~~~~~~~~~~
street_lamps.c:143:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~