| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 551374 | ala2 | 가로등 (APIO19_street_lamps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define all(X) begin(X), end(X)
struct BIT {
vector<int> a; int n, sum = 0;
BIT(int N) : a((n=N)+1) {}
void add(int i, int v) {
sum += v;
for(++i; i <= n; i += i&-i) a[i] += v;
}
int get(int i) {
int v = 0;
for(++i; i >= 1; i -= i&-i) v += a[i];
return v;
}
int suf(int i) { // [i...)
return sum - get(i-1); }
};
const int Z = 3e5+1;
int lg[Z+1];
int lowerB(const vi &a, const int &v) {
int i = -1;
for(int j = lg[size(a)]; j/= 2; )
if(i+j < size(a) && a[i+j] < v) i += j;
return i + 1;
}
struct CompoundBIT {
int n;
vector<vi> a;
vector<BIT*> b;
CompoundBIT(int N) : n(N), a(N), b(N) {}
void addVal(int i, int v) {
for(++i; i < n; i += i&-i) a[i].push_back(v);
}
void build() {
for(int i = 1; i < n; i++) {
sort(all(a[i]));
b[i] = new BIT(size(a[i]));
}
}
void update(int i, int v, int w) {
for(++i; i < n; i += i&-i)
b[i]->add(lowerB(a[i], v), w);
}
int query(int i, int v) {
int x = 0;
for(++i; i > 0; i -= i&-i)
x += b[i]->suf(lowerB(a[i], v));
return x;
}
} cb(Z);
int N, Q;
string _inp;
int qL[Z], qR[Z];
bitset<Z> qType, state;
set<array<int, 2>> intervals;
vector<array<int, 3>> iAt[Z];
array<int, 2> iFound[Z];
map<int, int> last[Z];
void addInterval(int l, int r, int i) {
if(r < l) return;
cb.addVal(l, r);
intervals.insert({l, r});
iAt[i].push_back({l, r, 1});
}
void remInterval(int l, int r, int i) {
if(r < l) return;
intervals.erase({l, r});
iAt[i].push_back({l, r, 0});
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
for(int i=0; i<=Z; ++i)
lg[i] = 2<<__lg(i);
cin >> N >> Q;
cin >> _inp;
for(int i = 0; i < N; ++i)
state[i] = _inp[i] - '0';
for(int i = 0; i < N; ++i) if(state[i]) {
int l = i;
while(i < N && state[i]) ++i;
addInterval(l, i-1, 0);
}
for(int i = 1; i <= Q; ++i) {
cin >> _inp >> qL[i]; --qL[i];
if((qType[i] = _inp[0] == 'q')) {
cin >> qR[i];
qR[i] -= 2;
auto f = intervals.upper_bound({qL[i], Z});
if(!empty(intervals) && f != begin(intervals))
iFound[i] = *--f;
else
iFound[i][0] = Z;
} else {
auto f = intervals.upper_bound({qL[i], Z});
int v = qL[i];
if(state[v]) {
auto [l, r] = *--f;
remInterval(l, r, i);
addInterval(l, v-1, i);
addInterval(v+1, r, i);
} else {
int l = v, r = v;
if(v + 1 < N && state[v+1]) r = (*f)[1];
if(v + 0 > 0 && state[v-1]) l = (*--f)[0];
remInterval(v+1, r, i);
remInterval(l, v-1, i);
addInterval(l, r, i);
}
state[v] = !state[v];
}
}
cb.build();
for(int i = 0; i <= Q; ++i) {
for(auto &[l, r, toAdd] : iAt[i]) {
if(toAdd) last[l][r] = i;
else cb.update(l, r, i - last[l][r]);
}
if(qType[i]) {
int res = cb.query(qL[i], qR[i]);
auto [l, r] = iFound[i];
if(l <= qL[i] && qR[i] <= r)
res += i - last[l][r];
cout << res << '\n';
}
}
}