#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int MAXN = 3e5 + 12, INF = 1e9 + 7;
struct tree {
int t[MAXN * 4];
void upd(int v, int tl, int tr, int pos, int val){
t[v] += val;
if(tl == tr)
return;
int tm = (tl + tr) / 2;
if(pos <= tm)
upd(v * 2, tl, tm, pos, val);
else
upd(v * 2 + 1, tm + 1, tr, pos, val);
}
int getL(int v, int tl, int tr, int pos){
if(tl == tr)
return tl - (t[v] > 0);
int tm = (tl + tr) / 2;
if(pos <= tm){
return getL(v * 2, tl, tm, pos);
}
else{
int left = tm;
if(t[v * 2 + 1])
left = getL(v * 2 + 1, tm + 1, tr, pos);
if(left == tm && t[v * 2])
left = getL(v * 2, tl, tm, pos);
else if(left == tm)
left = tl - 1;
return left;
}
}
int getR(int v, int tl, int tr, int pos){
if(tl == tr)
return tl + (t[v] > 0);
int tm = (tl + tr) / 2;
if(pos > tm){
return getR(v * 2 + 1, tm + 1, tr, pos);
}
else{
int right = tm + 1;
if(t[v * 2])
right = getR(v * 2, tl, tm, pos);
if(right == tm + 1 && t[v * 2 + 1])
right = getR(v * 2 + 1, tm + 1, tr, pos);
else if(right == tm + 1)
right = tr + 1;
return right;
}
}
}city;
struct fenwick{
unordered_map< int, pair<ll, int> > fw[MAXN];
void upd(int x, int y, int vx, int vy){
for(int i = x;i < MAXN;i |= i + 1)
for(int j = y;j < MAXN;j |= j + 1)
fw[i][j].X += vx, fw[i][j].Y += vy;
}
pair<ll, int> get(int x, int y){
ll vx = 0;
int vy = 0;
for(int i = x;i >= 0;i = (i & (i + 1)) - 1){
for(int j = y;j >= 0;j = (j & (j + 1)) - 1){
if(fw[i].count(j))
vx += fw[i][j].X, vy += fw[i][j].Y;
}
}
return MP(vx, vy);
}
}fw;
int answer[MAXN], n, q, lamp[MAXN], cntC[MAXN];
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;i++){
char x;
cin >> x, lamp[i] = (x == '1');
if(x == '1'){
city.upd(1, 1, n + 1, i, 1);
cntC[i]++;
}
}
map< pair< int, int >, int > dict;
for(int i = 1, len = 0;i <= n + 1;i++){
if(cntC[i])
len++;
else{
if(len)
dict[MP(i - len, i - 1)] = 0, fw.upd(i - len, i - 1, 0, 1);//, cerr << i - len << " " << i - 1 << "\n";
len = 0;
}
}
for(int i = 1;i <= q;i++){
string tp;
cin >> tp;
if(tp[0] == 't'){
int x;
cin >> x;
if(lamp[x]){
int tl = city.getL(1, 1, n + 1, x) + 1, tr = city.getR(1, 1, n + 1, x) - 1;
int val = dict[MP(tl, tr)];
fw.upd(tl, tr, i - 2 * val, -1), cntC[x]--;
if(cntC[x] == 0)
city.upd(1, 1, n + 1, x, -1);
if(cntC[x] == 0){
tl = (x == 1 ? 0: city.getL(1, 1, n + 1, x - 1) + 1), tr = x - 1;
if(tl <= tr)
fw.upd(tl, tr, i, 1), dict[MP(tl, tr)] = i;
}
else{
tl = city.getL(1, 1, n + 1, x - 1) + 1, tr = city.getR(1, 1, n + 1, x + 1) - 1;
fw.upd(tl, tr, i, 1), dict[MP(tl, tr)] = i;
}
}
else{
int tl, tr;
cntC[x]++;
if(cntC[x] == 1){
tl = (x == 1 ? 0: city.getL(1, 1, n + 1, x - 1) + 1), tr = x - 1;
if(tl <= tr)
fw.upd(tl, tr, i - 2 * dict[MP(tl, tr)], -1);
}
else{
tl = city.getL(1, 1, n + 1, x - 1) + 1, tr = city.getR(1, 1, n + 1, x + 1) - 1;
fw.upd(tl, tr, i - 2 * dict[MP(tl, tr)], -1);
}
if(cntC[x] == 1)
city.upd(1, 1, n + 1, x, 1);
tl = city.getL(1, 1, n + 1, x) + 1, tr = city.getR(1, 1, n + 1, x) - 1;
//cerr << tl << " " << tr << " " << x << "z\n";
fw.upd(tl, tr, i, 1), dict[MP(tl, tr)] = i;
}
lamp[x] ^= 1;
}
else{
int l, r;
cin >> l >> r, r--;
pair<ll, int> v1 = fw.get(l, n + 1), v2 = fw.get(l, r - 1);
ll ans = (v1.Y - v2.Y) * 1ll * i - v1.X + v2.X;
cout << ans << "\n";
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
16716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2909 ms |
21712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
40 ms |
17856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
17552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
16716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
