#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=3e5+9;
vector<int>node[maxn];
vector<long long>bit[maxn];
int n,q;
void fakeupdate(int x,int y){
for(;x<=n;x+=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void fakeget(int x,int y){
for(;x>=1;x-=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void build(){
for1(i,1,n){
sort(all(node[i]));
auto it=unique(all(node[i]));
node[i].resize(distance(node[i].begin(),it));
bit[i].resize(sz(node[i]));
}
}
void update(int x,int y,int val){
for(;x<=n;x+=(x-(x&(x-1)))){
for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy<sz(node[x]);yy+=(yy-(yy&(yy-1)))){
bit[x][yy]+=val;
}
}
}
long long get(int x,int y){
long long sum=0;
for(;x>=1;x-=(x-(x&(x-1)))){
for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy>=1;yy-=(yy-(yy&(yy-1)))){
sum+=bit[x][yy];
}
}
return sum;
}
struct line{
int l,r,t;
bool operator <(const line &p)const{
return r<p.r;
}
};
struct query{
int type,x,y;
}b[maxn];
void fakerect(int x1,int y1,int x2,int y2){
fakeget(x1-1,y1-1);
fakeget(x2,y2);
fakeget(x2,y1-1);
fakeget(x1-1,y2);
}
long long getrect(int x1,int y1,int x2,int y2){
return get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n>>q;
string s;
cin>>s;
s=" "+s;
for1(i,1,n)node[i].pb(0);
multiset<line>nt;
for1(i,1,n){
if (s[i]=='0')continue;
else {
int p=i;
for1(j,i,n){
if (s[j]!=s[i])break;
p=j;
}
nt.insert({i,p,1});
i=p;
}
}
string t=s;
for1(i,1,q){
cin>>b[i].type;
if (b[i].type==1){
cin>>b[i].x>>b[i].y;
if (b[i].x>b[i].y)swap(b[i].x,b[i].y);
if (b[i].x==b[i].y)continue;
b[i].y--;
//small than x and large than y
fakerect(1,b[i].y,b[i].x,n);
}
else {
cin>>b[i].x;
if (s[b[i].x]=='1'){
s[b[i].x]='0';
auto it=nt.lower_bound({b[i].x,b[i].x,-1});
line temp=(*it);
fakeupdate(temp.l,temp.r);
nt.erase(it);
if (temp.l<b[i].x){
nt.insert({temp.l,b[i].x-1,i});
}
if (temp.r>b[i].x){
nt.insert({b[i].x+1,temp.r,i});
}
}
else {
s[b[i].x]='1';
auto it=nt.upper_bound({b[i].x,b[i].x,-1});
line nw={b[i].x,b[i].x,i};
if (it!=nt.begin()){
it--;
line temp=(*it);
if (temp.r+1==b[i].x){
nt.erase(it);
fakeupdate(temp.l,temp.r);
nw.l=temp.l;
}
}
it=nt.upper_bound({b[i].x,b[i].x,-1});
if (it!=nt.end()){
line temp=(*it);
if (temp.l==b[i].x+1){
nt.erase(it);
fakeupdate(temp.l,temp.r);
nw.r=temp.r;
}
}
nt.insert(nw);
}
}
}
build();
s=t;
nt.clear();
for1(i,1,n){
if (s[i]=='0')continue;
else {
int p=i;
for1(j,i,n){
if (s[j]!=s[i])break;
p=j;
}
nt.insert({i,p,0});
i=p;
}
}
for1(i,1,q){
if (b[i].type==1){
//cout<<b[i].x<<" "<<b[i].y<<'\n';
if (b[i].x>b[i].y){
cout<<i<<'\n';
continue;
}
//small than x and large than y
long long ans=getrect(1,b[i].y,b[i].x,n);
auto it=nt.lower_bound({b[i].x,b[i].y,-1});
if (it!=nt.end()){
auto temp=(*it);
if (temp.r>=b[i].y&&temp.l<=b[i].x){
ans+=i-temp.t;
//cout<<temp.l<<" "<<temp.r<<" "<<b[i].x<<" "<<b[i].y<<" "<<temp.t<<" "<<ans<<'\n';
}
}
cout<<ans<<'\n';
}
else {
if (s[b[i].x]=='1'){
s[b[i].x]='0';
auto it=nt.lower_bound({b[i].x,b[i].x,-1});
line temp=(*it);
update(temp.l,temp.r,i-temp.t);
nt.erase(it);
if (temp.l<b[i].x){
nt.insert({temp.l,b[i].x-1,i});
}
if (temp.r>b[i].x){
nt.insert({b[i].x+1,temp.r,i});
}
}
else {
s[b[i].x]='1';
auto it=nt.upper_bound({b[i].x,b[i].x,-1});
line nw={b[i].x,b[i].x,i};
if (it!=nt.begin()){
it--;
line temp=(*it);
if (temp.r+1==b[i].x){
nt.erase(it);
update(temp.l,temp.r,i-temp.t);
nw.l=temp.l;
}
}
it=nt.upper_bound({b[i].x,b[i].x,-1});
if (it!=nt.end()){
line temp=(*it);
if (temp.l==b[i].x+1){
nt.erase(it);
update(temp.l,temp.r,i-temp.t);
nw.r=temp.r;
}
}
nt.insert(nw);
}
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen("temp.INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
15708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
