#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define lb(a) ((a)&(-(a)))
const int maxn = 3e5 + 20;
const int maxb = 20;
string s , type[maxn];
int l[maxn] , r[maxn] , ind[maxn] , pos[maxn] , where[maxn];
int seg[maxb][maxn] , nq , fen[maxb][maxn];
bool cmp(int x , int y)
{
return l[x] < l[y];
}
void addFen(int p , int val , int h)
{
for(p += 5; p < maxn; p += lb(p))
fen[h][p] += val;
}
int getFen(int p , int h)
{
int res = 0;
for(p += 5; p > 0; p -= lb(p))
res += fen[h][p];
return res;
}
void build(int s = 0 , int e = nq , int v = 1 , int h = 0)
{
if(e - s < 2)
{
seg[h][s] = r[ind[s]];
return;
}
int m = (s + e) / 2;
build(s , m , 2 * v , h + 1);
build(m , e , 2 * v + 1 , h + 1);
merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s);
}
void add(int l , int r , int lx , int rx , int val , int s = 0 , int e = nq , int v = 1 , int h = 0)
{
if(l <= s && e <= r)
{
int L = lower_bound(seg[h] + s , seg[h] + e , lx) - seg[h];
int R = lower_bound(seg[h] + s , seg[h] + e , rx) - seg[h];
addFen(L , val , h);
addFen(R , -val , h);
return;
}
if(r <= s || e <= l)
return;
int m = (s + e) / 2;
add(l , r , lx , rx , val , s , m , 2 * v , h + 1);
add(l , r , lx , rx , val , m , e , 2 * v + 1 , h + 1);
}
int get(int p , int r , int s = 0 , int e = nq , int v = 1 , int h = 0)
{
int x = lower_bound(seg[h] + s , seg[h] + e , r) - seg[h];
int res = getFen(x , h);
if(e - s < 2)
return res;
int m = (s + e) / 2;
if(p < m)
return res + get(p , r , s , m , 2 * v , h + 1);
else
return res + get(p , r , m , e , 2 * v + 1 , h + 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n , q;
cin >> n >> q;
cin >> s;
for(int i = 0; i < q; i++)
{
cin >> type[i];
if(type[i] == "toggle")
{
cin >> pos[i];
pos[i]--;
}
else
{
cin >> l[i] >> r[i];
l[i]--;
r[i]--;
ind[nq++] = i;
}
}
sort(ind , ind + nq , cmp);
for(int i = 0; i < nq; i++)
where[ind[i]] = i;
build();
set<int> st;
st.insert(-1);
st.insert(n);
addFen(0 , q , 0);
for(int i = 0; i < n; i++)
if(s[i] == '0')
{
st.insert(i);
auto it = st.find(i);
it--;
int l0 = *it + 1, r0 = *st.upper_bound(i);
l[q] = l0; int L = lower_bound(ind , ind + nq , q , cmp) - ind;
l[q] = i; int R = upper_bound(ind , ind + nq , q , cmp) - ind;
add(L , R , i + 1 , r0 + 1 , -q);
}
for(int i = 0; i < q; i++)
{
if(type[i] == "toggle")
{
auto it = st.lower_bound(pos[i]);
it--;
int l0 = *it + 1, r0 = *st.upper_bound(pos[i]);
l[q] = l0; int L = lower_bound(ind , ind + nq , q , cmp) - ind;
l[q] = i; int R = upper_bound(ind , ind + nq , q , cmp) - ind;
if(s[pos[i]] == '0')
add(L , R , pos[i] + 1 , r0 + 1 , q - i - 1) , s[pos[i]] = '1' , st.erase(pos[i]);
else
add(L , R , pos[i] + 1 , r0 + 1 , -(q - i)) , s[pos[i]] = '0' , st.insert(pos[i]);
}
else
{
bool is = 1;
auto it = st.lower_bound(l[i]);
if(it != st.end() && *it < r[i])
is = 0;
cout << get(where[i] , r[i]) - (is? q - i - 1 : 0) << endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1135 ms |
38772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9984 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
10368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10240 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
10368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
