//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct BIT{
int n;
vector<int>arr;
vector<int>have;
void in(int x){ have.push_back(x); }
void build(){
sort(have.begin(),have.end());
have.resize(unique(have.begin(),have.end())-have.begin());
n=have.size();
arr.resize(n+3);
}
int idx(int x){
if (have.empty()) return 0;
return upper_bound(have.begin(),have.end(),x)-have.begin();
}
void modify(int p,int c){
if (p==0) return;
for (;p<=n;p+=(p&-p))
arr[p]+=c;
}
int query(int p){
int ans=0;
for (;p>0;p-=(p&-p))
ans+=arr[p];
return ans;
}
};
struct BBIT{
int n;
vector<BIT>arr;
void init(int _n){
n=_n;
arr.resize(n+3);
}
void need_use(int a,int b){
for (;a<=n;a+=(a&-a))
arr[a].in(b);
}
void modify(int a,int b,int c){
for (;a<=n;a+=(a&-a))
arr[a].modify(arr[a].idx(b)+1,c);
}
int query(int a,int b){
int ans=0;
for (;a>0;a-=(a&-a))
ans=(ans+arr[a].query(arr[a].idx(b)));
return ans;
}
}bit;
struct Query{
int op,a,b;
Query(int i,int j,int k):op(i),a(j),b(k){}
};
int n,q,last_time[N];
bool arr[N];
set<pair<pii,int> >all;
vector<Query>qry;
vector<pair<pii,int> >change[N];
void add_need(int a,int b,int t){
if (a>b) return;
all.insert({{a,b},t});
// add (a~b,a~b)
bit.need_use(a,a); bit.need_use(a,b+1);
bit.need_use(b+1,a); bit.need_use(b+1,b+1);
}
signed main(){
fast
cin>>n>>q;
bit.init(n);
int l=1,val=-1;
for (int i=1;i<=n;i++){
char c; cin>>c;
arr[i]=c-'0';
if (arr[i]==val) continue;
else {
if (val==1) all.insert({{l,i-1},0});
val=arr[i]; l=i;
}
}
all.insert({{l,n},0});
for (int i=1;i<=q;i++){
string str;
int a=0,b=0; cin>>str;
if (str=="toggle"){
cin>>a;
qry.push_back(Query(1,a,a));
}
else {
cin>>a>>b; b--;
qry.push_back(Query(2,a,b));
}
}
for (int i=1;i<=q;i++){
if (qry[i-1].op==1){
int p=qry[i-1].a;
if (arr[p]==1){
auto it=all.upper_bound(pair<pii,int>(pii(p,1e9),1e9)); it--;
auto [j,t]=(*it);
change[i].push_back({{j.x,j.y},i-t});
all.erase(it);
add_need(j.x,p-1,i);
add_need(p+1,j.y,i);
}
else {
auto it=all.upper_bound(pair<pii,int>(pii(p,p),1e9));
pii now={p,p};
if (it!=all.end()){
if ((*it).x.x==p+1){
now.y=(*it).x.y;
change[i].push_back({(*it).x,i-(*it).y});
add_need((*it).x.x,(*it).x.y,(*it).y);
it=all.erase(it);
}
}
if (it!=all.begin()){
it=prev(it);
if ((*it).x.y==p-1){
now.x=(*it).x.x;
change[i].push_back({(*it).x,i-(*it).y});
add_need((*it).x.x,(*it).x.y,(*it).y);
it=all.erase(it);
}
}
all.insert({now,i});
}
arr[p]^=1;
}
else {
int a=qry[i-1].a,b=qry[i-1].b;
auto it=all.upper_bound(pair<pii,int>(pii(a,1e9),1e9));
if (it==all.begin()){
last_time[i]=i;
continue;
}
it--;
if ((*it).x.x<=a&&(*it).x.y>=b) last_time[i]=(*it).y;
else last_time[i]=i;
}
}
for (int i=0;i<=n+1;i++)
bit.arr[i].build();
for (int i=1;i<=q;i++){
if (qry[i-1].op==1){
for (auto [j,t]:change[i]){
// cout<<"change "<<j.x<<' '<<j.y<<" "<<t<<'\n';
bit.modify(j.x,j.x,t);
bit.modify(j.x,j.y+1,-t);
bit.modify(j.y+1,j.x,-t);
bit.modify(j.y+1,j.y+1,t);
}
}
else {
cout<<bit.query(qry[i-1].a,qry[i-1].b)+i-last_time[i]<<'\n';
}
}
}
/*
5 7
11111
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
302 ms |
42924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
