#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,add;
int n;
void init(int s){
n = s;
t.assign((s + 1) * 4,0);
add.assign((s + 1) * 4,0);
}
void inc(int v,int val){
add[v] += val;
t[v] += val;
}
void push(int v)
{
if(add[v]){
inc(v+v,add[v]);
inc(v+v+1,add[v]);
add[v] = 0;
}
}
void upd(int l,int r,int val,int v,int tl,int tr){
if(l > r ||tl >r || l > tr) return;
if(tl >= l && tr <= r){
inc(v,val);
}else{
push(v);
int tm = (tl + tr) >> 1;
upd(l,r,val,v+v,tl,tm);
upd(l,r,val,v+v+1,tm+1,tr);
t[v] = t[v + v] + t[v + v + 1];
}
}
int get(int l,int r,int v,int tl,int tr){
if(l > r || tl >r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
push(v);
int tm = (tl + tr) >> 1;
return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
};
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 l1,int r1,int val,int v = 1,int tl = 1,int tr = n){
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r){
int it = lower_bound(t[v].begin(),t[v].end(),l1) - t[v].begin() + 1;
int it1 = upper_bound(t[v].begin(),t[v].end(),r1) - t[v].begin();
b[v].upd(it,it1,val,1,1,b[v].n);
}else{
int tm = (tl + tr) >> 1;
upd(l,r,l1,r1,val,v+v,tl,tm);
upd(l,r,l1,r1,val,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,it + 1,1,1,b[v].n);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(l <= tm) get(l,r,v+v,tl,tm);
else 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);
upd(l,x,x,r,-i);
// 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;
}
}
}else{
del(z,x);
auto [l,r] = ins(o,x);
upd(l,x,x,r,-i);
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){
res += i;
re[i] += i;
}
}
cout << res << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
test();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
45 ms |
101328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5058 ms |
109608 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
45 ms |
101492 KB |
Output is correct |
| 2 |
Correct |
46 ms |
101712 KB |
Output is correct |
| 3 |
Correct |
61 ms |
101652 KB |
Output is correct |
| 4 |
Correct |
53 ms |
101968 KB |
Output is correct |
| 5 |
Execution timed out |
5041 ms |
151020 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
46 ms |
101972 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
101776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
45 ms |
101328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
