| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 447871 | AmShZ | Street Lamps (APIO19_street_lamps) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//khodaya khodet komak kon
# include <bits/stdc++.h>
/*
# pragma GCC optimize("Ofast,unroll-loops")
# pragma comment(linker, "/stack:200000000")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
*/
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;
int n, q;
gp_hash_table <int, int> fen[xn];
string S;
set <int> st;
bool fl[xn];
void mofen(int x, int y, int val){
int ly = y;
for (x += 5; x < xn; x += x & - x){
y = ly;
for (y += 5; y < xn; y += y & - y)
fen[x][y] += val;
}
}
int gefen(int x, int y){
int res = 0, ly = y;
for (x += 5; 0 < x; x -= x & - x){
y = ly;
for (y += 5; 0 < y; y -= y & - y)
if (fen[x].find(i) != fen[x].end())
res += fen[x][y];
}
return res;
}
void upd(int l1, int r1, int l2, int r2, int val){
mofen(l1, l2, val);
mofen(l1, r2 + 1, - val);
mofen(r1 + 1, l2, - val);
mofen(r1 + 1, r2 + 1, val);
}
int main(){
fast_io;
cin >> n >> q >> S;
S = '.' + S;
st.insert(0);
st.insert(n + 1);
int last = n + 1;
for (int i = n; 1 <= i; -- i){
if (S[i] == '0')
last = i, st.insert(i);
fl[i] = S[i] - '0';
upd(i - 1, i - 1, i - 1, last - 1, q);
}
for (int i = 1; i <= q; ++ i){
int l, r, ind;
cin >> S;
if (S[0] == 't'){
cin >> ind;
if (!fl[ind]){
int y = *st.lower_bound(ind + 1);
int x = *prev(st.lower_bound(ind));
upd(x, ind - 1, ind, y - 1, q - i);
st.erase(ind);
}
else{
int y = *st.lower_bound(ind + 1);
int x = *prev(st.lower_bound(ind));
upd(x, ind - 1, ind, y - 1, i - q);
st.insert(ind);
}
fl[ind] ^= 1;
}
else{
cin >> l >> r;
int ans = gefen(l - 1, r - 1);
if (r <= *st.lower_bound(l))
ans -= q - i;
cout << ans << endl;
}
}
return 0;
}