#include <bits/stdc++.h>
//#include "rainbow.h"
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
//#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18;
const int lg = 20;
mt19937 rng(time(0));
ll randll(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
ll n;
vll bit;
void add(int i, ll val) {
i ++;
for (; i <= n; i += i & -i)
bit[i] += val;
}
ll sum(int i) {
ll res = 0;
for (; i > 0; i -= i & -i)
res += bit[i];
return res;
}
ll range_sum(int l, int r) {
return sum(r+1) - sum(l);
}
int main(){
speed;
ll q;
cin >> n >> q;
ll baze = sqrt(q);
str s;
cin >> s;
set<pll> v;
ll l = -1;
for(int i = 0; i < n; i ++){
if(s[i] == '1'){
if(l == -1) l = i;
}
else{
if(l != -1){
v.insert({l, i-1});
l = -1;
}
}
}
if(l != -1) v.insert({l, n-1});
map<pll, ll> m;
vll p(n+7, -1);
vector<pair<pll, ll>> vi, qr;
vll res(q, 0);
vll p_;
for(int i = 0; i < q; i ++){
if((i+1) % baze == 0){
sort(qr);
bit.clear();
bit.resize(n+7, 0);
ll l = 0;
for(auto j : m){
while(l < qr.size() && qr[l].fr.fr < j.fr.fr){
res[qr[l].se] += range_sum(qr[l].fr.se, n-1);
l++;
}
add(j.fr.se, j.se);
}
for(auto j : vi){
m[j.fr] += j.se;
}
qr.clear();
vi.clear();
}
str s1;
cin >> s1;
if(s1 == "toggle"){
ll x;
cin >> x;
x --;
if(s[x] == '0'){
ll l = x, r = x;
if(v.size() && v.lower_bound({x, -1}) != v.begin() && (*--v.lower_bound({x, -1})).se == x-1){
pll p1 = *--v.lower_bound({x, -1});
v.erase(p1);
vi.pb({p1, i-p[p1.fr]});
l = p1.fr;
}
if(v.lower_bound({x, -1}) != v.end() && (*v.lower_bound({x, -1})).fr == x+1){
pll p1 = *v.lower_bound({x, -1});
v.erase(p1);
vi.pb({p1, i-p[p1.fr]});
r = p1.se;
}
p[l] = i;
v.insert({l, r});
s[x] = '1';
}
else{
pll p1 = *--v.upper_bound({x, INF});
v.erase(p1);
vi.pb({p1, i-p[p1.fr]});
if(p1.fr != x){
p[p1.fr] = i;
v.insert({p1.fr, x-1});
}
if(p1.se != x){
p[x+1] = i;
v.insert({x+1, p1.se});
}
s[x] = '0';
}
}
else{
/*bit.clear();
bit.resize(n+7, 0);*/
p_.pb(i);
ll l, r;
cin >> l >> r;
l --, r -= 2;
qr.pb({{l, r}, i});
for(auto j : vi){
if(j.fr.fr <= l && r <= j.fr.se) res[i] += j.se;
}
if(v.upper_bound({l, INF}) != v.begin() && v.size()){
pll p1 = *--v.upper_bound({l, INF});
if(p1.se >= r) res[i] += i-p[p1.fr];
}
}
}
sort(qr);
bit.clear();
bit.resize(n+7, 0);
l = 0;
for(auto j : m){
while(l < qr.size() && qr[l].fr.fr < j.fr.fr){
res[qr[l].se] += range_sum(qr[l].fr.se, n-1);
l++;
}
add(j.fr.se, j.se);
}
for(int i : p_){
cout << res[i] << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |