#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 node{
pair<ll, int> val = MP(0LL, 0);
node* p[2] = {nullptr, nullptr};
node* getp(int v){
if(!p[v])
p[v] = new node();
return p[v];
}
void upd(int tl, int tr, int pos, ll vx, int vy){
val.X += vx, val.Y += vy;
if(tl == tr)
return;
int tm = (tl + tr) / 2;
if(pos <= tm)
getp(0)->upd(tl, tm, pos, vx, vy);
else
getp(1)->upd(tm + 1, tr, pos, vx, vy);
}
pair<ll, int> get(int tl, int tr, int l, int r){
//cerr << tl << " " << tr << " " << l << " " << r << " " << val.Y << "\n";
if(tl > r || l > tr)
return MP(0LL, 0);
if(tl >= l && r <= tr)
return val;
int tm = (tl + tr) / 2;
pair<ll, int> left = (p[0] ? p[0]->get(tl, tm, l, r): MP(0LL, 0));
pair<ll, int> right = (p[1] ? p[1]->get(tm + 1, tr, l, r): MP(0LL, 0));
return MP(left.X + right.X, left.Y + right.Y);
}
};
node BIT[MAXN];
int n;
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)
BIT[i].upd(1, n, y, vx, vy);
}
pair<ll, int> get(int x, int l, int r){
ll vx = 0;
int vy = 0;
for(int i = x;i >= 0;i = (i & (i + 1)) - 1){
pair<ll, int> tmp = BIT[i].get(1, n, l, r);
vx += tmp.X, vy += tmp.Y;
}
return MP(vx, vy);
}
}fw;
int answer[MAXN], 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, 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;
}
}
//cerr << fw.get(1, 1, 2).Y << "\n";
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, x) + 1, tr = city.getR(1, 1, n, x) - 1;
//int val = dict[MP(tl, tr)];
fw.upd(tl, tr, -i, -1), cntC[x]--;
if(cntC[x] == 0)
city.upd(1, 1, n, x, -1);
if(cntC[x] == 0){
tl = (x == 1 ? 0: city.getL(1, 1, n, 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, x - 1) + 1, tr = (x == n ? n: city.getR(1, 1, n, x + 1) - 1);
if(tl <= tr)
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, x - 1) + 1), tr = x - 1;
if(tl <= tr)
fw.upd(tl, tr, -i, -1);
}
else{
tl = city.getL(1, 1, n, x - 1) + 1, tr = (x == n ? n: city.getR(1, 1, n, x + 1) - 1);
if(tl <= tr)
fw.upd(tl, tr, -i, -1);
}
if(cntC[x] == 1)
city.upd(1, 1, n, x, 1);
tl = city.getL(1, 1, n, x) + 1, tr = city.getR(1, 1, n, 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, r, n);
//cerr << l << " " << r << " " << n << "\n";
ll ans = v1.Y * 1ll * i - v1.X;
cout << ans << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
467 ms |
18244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
18500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
