#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
int fw[300005];
void update(int x, int v) {
for (; x<300005; x+=x&(-x)) fw[x] += v;
}
int sum(int x) {
int res = 0;
for(; x; x-=x&(-x)) res += fw[x];
return res;
}
int query(int x, int y){
return sum(y)-sum(x-1);
}
int n,q;
string s;
int ans[300005];
typedef pair<pii,pii>pi2;
vector<pi2>storage[300005];
vector<pi2>que[300005];
vector<pii>undo;
void dnc(int l, int r){
if(r<=l){
sort(storage[l].begin(),storage[l].end());
sort(que[l].begin(),que[l].end());
return;
}
vector<pi2>lstorage;
vector<pi2>lque;
int mid=(l+r)/2;
for(auto it:storage[l]){
if(it.second.first<=mid){
lstorage.push_back(it);
}
else if(it.second.first>mid){
storage[mid+1].push_back(it);
}
}
for(auto it:que[l]){
if(it.second.first<=mid){
lque.push_back(it);
}
else que[mid+1].push_back(it);
}
storage[l]=lstorage;
que[l]=lque;
lstorage.resize(0);
lque.resize(0);
dnc(l,mid);
dnc(mid+1,r);
//show3(l,l,mid,mid,r,r);
//cout << "storage" << endl;
//for(auto it:storage[l]){
//cout << it.first.first << " " << it.first.second << " " << it.second.first << " " << it.second.second << endl;
//}
vector<pi2>hold;
vector<pi2>hold2;
int cur=0;
for(auto it:que[mid+1]){
int lft=it.first.first;
int rgt=it.first.second;
int index=it.second.second;
while(cur<(int)storage[l].size()){
if(storage[l][cur].first.first<=lft){
int val=(storage[l][cur].second.first-l+1)*storage[l][cur].second.second;
update(storage[l][cur].first.second,val);
undo.push_back({storage[l][cur].first.second,-val});
cur++;
}
else{
break;
}
}
int inc=query(rgt,n);
ans[index]+=inc;
//show2(index,index,add,inc);
}
for(auto it:undo){
update(it.first,it.second);
}
undo.clear();
merge(storage[l].begin(),storage[l].end(),storage[mid+1].begin(),storage[mid+1].end(),back_inserter(hold));
merge(que[l].begin(),que[l].end(),que[mid+1].begin(),que[mid+1].end(),back_inserter(hold2));
storage[l].resize(0);
storage[mid+1].resize(0);
que[l].resize(0);
que[mid+1].resize(0);
storage[l]=hold;
que[l]=hold2;
hold.resize(0);
hold2.resize(0);
}
void solve(){
cin >> n >> q;
cin >> s;
s="0"+s+"0";
string temp;
int l,r;
int ptr=0;
set<pair<pii,int>>se;
for(int x=1;x<=n;x++){
if(s[x]=='1'){
int cur=x;
for(int y=x;y<=n;y++){
if(s[y]=='0') break;
cur=y;
}
se.insert({{cur,x},1LL});
x=cur;
}
}
for(int x=2;x<=q+1;x++){
cin >> temp;
if(temp=="toggle"){
cin >> l;
if(s[l]=='1'){
//turn off
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold=*it;
storage[0].push_back({{hold.first.second,hold.first.first},{x-1,1}});
storage[0].push_back({{hold.first.second,hold.first.first},{hold.second-1,-1}});
if(hold.first.second<l){
se.insert({{l-1,hold.first.second},x});
}
if(hold.first.first>l){
se.insert({{hold.first.first,l+1},x});
}
se.erase(se.find(hold));
s[l]='0';
}
else{
//turn on
if(s[l-1]=='1'&&s[l+1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold,hold2;
hold=*it;
it--;
hold2=*it;
storage[0].push_back({{hold.first.second,hold.first.first},{x-1,1}});
storage[0].push_back({{hold.first.second,hold.first.first},{hold.second-1,-1}});
storage[0].push_back({{hold2.first.second,hold2.first.first},{x-1,1}});
storage[0].push_back({{hold2.first.second,hold2.first.first},{hold2.second-1,-1}});
se.insert({{hold.first.first,hold2.first.second},x});
se.erase(se.find(hold));
se.erase(se.find(hold2));
}
else if(s[l-1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
it--;
pair<pii,int>hold=*it;
storage[0].push_back({{hold.first.second,hold.first.first},{x-1,1}});
storage[0].push_back({{hold.first.second,hold.first.first},{hold.second-1,-1}});
se.insert({{l,hold.first.second},x});
se.erase(se.find(hold));
}
else if(s[l+1]=='1'){
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold=*it;
storage[0].push_back({{hold.first.second,hold.first.first},{x-1,1}});
storage[0].push_back({{hold.first.second,hold.first.first},{hold.second-1,-1}});
se.insert({{hold.first.first,l},x});
se.erase(se.find(hold));
}
else{
se.insert({{l,l},x});
}
s[l]='1';
}
}
else{
cin >> l >> r;
r--;
auto it=se.lower_bound({{l,0LL},0LL});
pair<pii,int>hold=*it;
if(hold.first.second<=l&&hold.first.first>=r){
ans[ptr]+=x;
}
que[0].push_back({{l,r},{x,ptr++}});
}
}
for(auto it:se){
storage[0].push_back({{it.first.second,it.first.first},{q+1,1}});
storage[0].push_back({{it.first.second,it.first.first},{it.second-1,-1}});
}
se.clear();
//for(auto it:storage[0]){
//cout << it.first.first << " " << it.first.second << " " << it.second.first << " " << it.second.second << endl;
//}
dnc(0,q+1);
for(int x=0;x<ptr;x++){
cout << ans[x] << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
506 ms |
150788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
15196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
15260 KB |
Output is correct |
| 2 |
Correct |
5 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
5 ms |
15192 KB |
Output is correct |
| 4 |
Correct |
5 ms |
15452 KB |
Output is correct |
| 5 |
Correct |
462 ms |
149536 KB |
Output is correct |
| 6 |
Correct |
503 ms |
169888 KB |
Output is correct |
| 7 |
Correct |
538 ms |
195068 KB |
Output is correct |
| 8 |
Correct |
606 ms |
234708 KB |
Output is correct |
| 9 |
Incorrect |
398 ms |
171460 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
