#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 20, MOD = (int)1e9+7;
struct bit{
vector<int> t;
int n;
void init(int s){
n = s;
t.assign(s + 1,0);
}
void upd(int pos,int val,int n){
while(pos <= n){
t[pos] += val;
pos += pos & -pos;
}
}
int get(int i){
int ret = 0;
while(i >= 1){
ret += t[i];
i -= i & -i;
}
return ret;
}
int get(int l,int r){
return get(r) - get(l - 1);
}
};
vector<pair<int,int>> qr;
int n,q,a[N];
vector<int> t[N * 4],f[N];
bit b[N * 4];
void build(int v = 1,int tl = 1,int tr = n){
if(tl == tr){
t[v] = f[tl];
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
b[v].init((int)t[v].size());
}else{
int tm = (tl + tr) >> 1;
build(v+v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
b[v].init((int)t[v].size());
}
}
void del(set<pair<int,int>> &st,int pos){
auto it = st.upper_bound({pos,(int)1e9});
it--;
auto [l,r] = *it;
st.erase(it);
if(l != pos){
st.insert({l,pos-1});
}
if(r != pos){
st.insert({pos+1,r});
}
}
pair<int,int> ins(set<pair<int,int>> &st,int pos){
if(st.empty()){
st.insert({pos,pos});
return {pos,pos};
}
auto it = st.upper_bound({pos,(int)1e9});
if(it == st.end() || (*it).first != pos + 1){
if(it == st.begin()){
st.insert({pos,pos});
return {pos,pos};
}
it--;
if((*it).second + 1 != pos){
st.insert({pos,pos});
return {pos,pos};
}
int L = (*it).first;
st.insert({L,pos});
st.erase(it);
return {L,pos};
}
int R = (*it).second;
if(it == st.begin()){
st.erase(it);
st.insert({pos,R});
return {pos,R};
}
it--;
if((*it).second + 1 != pos){
it++;
st.erase(it);
st.insert({pos,R});
return {pos,R};
}
int L = (*it).first;
auto it1 = it;
it1++;
st.erase(it1);
st.erase(it);
st.insert({L,R});
return {L,R};
}
void upd(int l,int r,int x,int v = 1,int tl = 1,int tr = n){
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r){
int val = r;
if(t[v].empty() || t[v][0] > val) return;
int it = upper_bound(t[v].begin(),t[v].end(),val) - t[v].begin();it--;
b[v].upd(it + 1,x,(int)b[v].n);
}else{
int tm = (tl + tr) >> 1;
upd(l,r,x,v+v,tl,tm);
upd(l,r,x,v+v+1,tm+1,tr);
}
}
int res =0 ;
void get(int l,int r,int v = 1,int tl = 1,int tr = n){
int it = lower_bound(t[v].begin(),t[v].end(),r) - t[v].begin();
res += b[v].get(it + 1,b[v].n);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
get(l,r,v+v,tl,tm);
get(l,r,v+v+1,tm+1,tr);
}
int re[N];
void test(){
cin >> n >> q;
for(int i = 1;i <= n;i++){
char x;
cin >> x;
a[i] = (x - '0');
}
qr.push_back({-1,-1});
for(int i = 1;i <= q;i++)
{
string tp;cin >> tp;
if(tp == "toggle"){
int x;
cin >> x;
qr.push_back({x,-1});
}else{
int l,r;
cin >> l >> r;
r--;
f[l].push_back(r);
qr.push_back({l,r});
}
}
for(int i = 1;i <= n;i++){
sort(f[i].begin(),f[i].end());
}
build();
set<pair<int,int>> o,z;
int lst = 1;
for(int i = 2;i <= n + 1;i++){
if(i == n + 1 || a[i] != a[lst]){
if(a[lst]){
o.insert({lst,i - 1});
}else{
z.insert({lst,i - 1});
}
lst = i;
}
}
for(int i = 1;i <= q;i++){
auto [L,R] = qr[i];
if(R == -1){
int x = L;
if(a[x]){
auto it = o.upper_bound({x,1e9});
it--;
int l = (*it).first,r = (*it).second;
del(o,x);
ins(z,x);
// cout << l << ' ' << r << ' ' << x << '\n';
for(int j = i + 1;j <= q;j++){
if(qr[j].second != -1 && qr[j].first >= l && qr[j].first <= x && qr[j].second >= x && qr[j].second <= r){
re[j] += i;
// cout << i << "x\n";
}
}
}else{
del(z,x);
auto [l,r] = ins(o,x);
// cout << l << ' ' << r << "x\n";
// for(auto [x,y]:o){
// cout << x << ' ' << y << '\n';
// }
for(int j = i + 1;j <= q;j++){
if(qr[j].second != -1 && qr[j].first >= l && qr[j].first <= x && qr[j].second >= x && qr[j].second <= r){
// cout << i << "-\n";
re[j] -= i;
}
}
}
a[x] ^= 1;
}else{
res = 0;
// get(L,R);
auto it = o.upper_bound({L,1e9});
if(it != o.begin()){
it--;
if((*it).second >= R){
re[i] += i;
}
}
cout << re[i] << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
test();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
73052 KB |
Output is correct |
| 2 |
Correct |
32 ms |
73052 KB |
Output is correct |
| 3 |
Correct |
31 ms |
73052 KB |
Output is correct |
| 4 |
Correct |
31 ms |
73048 KB |
Output is correct |
| 5 |
Correct |
31 ms |
73304 KB |
Output is correct |
| 6 |
Correct |
32 ms |
73048 KB |
Output is correct |
| 7 |
Correct |
31 ms |
73052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5096 ms |
81496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
73308 KB |
Output is correct |
| 2 |
Correct |
32 ms |
73300 KB |
Output is correct |
| 3 |
Correct |
35 ms |
73300 KB |
Output is correct |
| 4 |
Correct |
33 ms |
73308 KB |
Output is correct |
| 5 |
Execution timed out |
5100 ms |
102900 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
73296 KB |
Output is correct |
| 2 |
Correct |
33 ms |
73300 KB |
Output is correct |
| 3 |
Correct |
33 ms |
73444 KB |
Output is correct |
| 4 |
Correct |
32 ms |
73148 KB |
Output is correct |
| 5 |
Correct |
1410 ms |
161828 KB |
Output is correct |
| 6 |
Execution timed out |
5017 ms |
147780 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
73052 KB |
Output is correct |
| 2 |
Correct |
32 ms |
73052 KB |
Output is correct |
| 3 |
Correct |
31 ms |
73052 KB |
Output is correct |
| 4 |
Correct |
31 ms |
73048 KB |
Output is correct |
| 5 |
Correct |
31 ms |
73304 KB |
Output is correct |
| 6 |
Correct |
32 ms |
73048 KB |
Output is correct |
| 7 |
Correct |
31 ms |
73052 KB |
Output is correct |
| 8 |
Execution timed out |
5096 ms |
81496 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
