#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("O2")
/*#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = /*long long*/ int;
using ld = long double;
#define F first
#define S second
#define pb push_back
//#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=3e5+10,LN=20,M=3.5e7+10,SQ=350,BS=737,inf=1e9+10;
const ll INF=1e15;
const ld ep=1e-7;
const int MH=1000696969,MOD=1000000007,MD=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
ll ans=1;
while (y != 0) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
ll n,q;
string s;
set<ll> st={0};
gp_hash_table<ll,ll> f[N];
inline void upd(ll l, const ll &r, const ll &x){
l++;
r++;
while(l<N){
for(ll i=r; i<N; i+=i&-i) f[l][i]+=x;
l+=l&-l;
}
}
inline void ADD(const ll &a, const ll &b, const ll &c, const ll &d, const ll &x){
upd(a,b,x);
upd(a,d+1,-x);
upd(c+1,b,-x);
upd(c+1,d+1,x);
}
inline ll get(ll l, const ll &r, ll x=0){
l++;
r++;
while(l){
for(ll i=r; i; i-=i&-i) if(f[l].find(i)!=f[l].end()) x+=f[l][i];
l-=l&-l;
}
return x;
}
int main(){
fast_io;
cin >> n >> q >> s;
st.insert(n+1);
for(ll i=1; i<=n; i++){
if(s[i-1]=='0') st.insert(i);
}
for(ll i=1; i<=q; i++){
string t;
cin >> t;
if(t[0]=='t'){
ll x;
cin >> x;
ll l=*(--st.lower_bound(x))+1,r=*st.upper_bound(x);
if(st.count(x)){
st.erase(x);
ADD(l,x+1,x,r,-i);
}else{
st.insert(x);
ADD(l,x+1,x,r,i);
}
}else{
ll l,r;
cin >> l >> r;
cout << get(l,r)+(st.lower_bound(l)==st.lower_bound(r)?i:0) << '\n';
}
}
return 0;
}
Compilation message
street_lamps.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
street_lamps.cpp:19:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+15' to '2147483647' [-Woverflow]
19 | const ll INF=1e15;
| ^~~~
street_lamps.cpp: In function 'void upd(ll, const ll&, const ll&)':
street_lamps.cpp:44:5: error: increment of read-only reference 'r'
44 | r++;
| ^
street_lamps.cpp: In function 'll get(ll, const ll&, ll)':
street_lamps.cpp:58:5: error: increment of read-only reference 'r'
58 | r++;
| ^
