#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10, inf=1e18;
struct BIT2d{
int n;
vector<pair<int, pair<int, int>>> t[N];
void init(int _n){
n=_n;
for (int i=1; i<=n; ++i) t[i].push_back({-1, {0, 0}});
}
void fake_update(int x, int y){
for (int i=x; i<=n; i+=i&(-i)) t[i].push_back({y, {0, 0}});
}
void compress(){
for (int i=1; i<=n; ++i){
sort(t[i].begin(), t[i].end());
t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
}
}
void update(int x, int y, int t1, int t2){
if (x>n || y>n) return;
for (int i=x; i<=n; i+=i&(-i)){
for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, make_pair(-inf, -inf)))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
t[i][j].second.first+=t1;
t[i][j].second.second+=t2;
}
}
}
pair<int, int> get(int x, int y){
pair<int, int> ans={0, 0};
for (int i=x; i; i-=i&(-i)){
for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y+1, make_pair(-inf, -inf)))-t[i].begin()-1; j; j-=j&(-j)){
ans.first+=t[i][j].second.first;
ans.second+=t[i][j].second.second;
}
}
return ans;
}
};
struct Event{
int lx, rx, ly, ry, idx;
Event (int _lx=0, int _rx=0, int _ly=0, int _ry=0, int _idx=0){
lx=_lx, rx=_rx, ly=_ly, ry=_ry, idx=_idx;
}
bool operator<(const Event &b){
if (rx==b.rx) return idx<b.idx;
return rx>b.rx;
}
};
int n, q, ans[N], is_query[N];
string s;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
vector<Event> v;
set<pair<int, int>> st;
map<pair<int, int>, int> mp;
cin >> n >> q >> s;
auto insert=[&](int t, int l, int r){
mp[{l, r}]=t;
st.emplace(l, r);
};
auto erase=[&](int tr, int l, int r){
int tl=mp[{l, r}];
v.emplace_back(l, r, tl, tr-1);
st.erase({l, r});
mp.erase({l, r});
};
s=" "+s;
for (int i=1; i<=n; ++i) if (s[i]=='1'){
int j=i;
while (j<n && s[j+1]=='1') ++j;
insert(1, i, j);
i=j;
}
for (int i=2; i<=q+1; ++i){
string type; cin >> type;
if (type[0]=='t'){
int x; cin >> x;
if (s[x]=='0'){
if (st.empty()){
insert(i, x, x);
}else{
auto it=st.lower_bound({x, x});
int l=x, r=x;
if (it!=st.end() && x+1==it->first){
r=it->second;
erase(i, it->first, it->second);
it=st.lower_bound({x, x});
}
if (it!=st.begin() && (--it)->second==l-1){
l=it->first;
erase(i, it->first, it->second);
}
insert(i, l, r);
}
}else{
auto it=st.lower_bound({x, (int)1e9}); --it;
int l=it->first, r=it->second;
erase(i, l, r);
if (l!=x) insert(i, l, x-1);
if (r!=x) insert(i, x+1, r);
}
s[x]^=1;
}else{
is_query[i]=1;
int l, r; cin >> l >> r; --r;
v.emplace_back(l, r, 1, i-1, i);
}
}
vector<pair<int, int>> tmp(st.begin(), st.end());
for (auto &i:tmp) erase(q+2, i.first, i.second);
sort(v.begin(), v.end());
BIT2d bit;
bit.init(N-1);
for (auto &i:v){
if (i.idx==0){
bit.fake_update(i.lx, i.ly);
bit.fake_update(i.lx, i.ry);
}
}
bit.compress();
for (auto &i:v){
if (i.idx==0){
// cout << "update " << i.lx << ' ' << i.ly << ' ' << 1 << ' ' << -i.ly+1 << '\n';
// cout << "update " << i.lx << ' ' << i.ry << ' ' << -1 << ' ' << i.ry << '\n';
bit.update(i.lx, i.ly, 1, -i.ly+1);
bit.update(i.lx, i.ry, -1, i.ry);
}else{
// cout << "query " << i.lx << ' ' << i.ry << '\n';
auto tmp=bit.get(i.lx, i.ry);
ans[i.idx]=tmp.first*(i.ry+1)+tmp.second;
}
}
for (int i=2; i<=q+1; ++i) if (is_query[i]) cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1596 ms |
204368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
19804 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
19548 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
19344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
