#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define lo(x,y) lower_bound(x.begin(),x.end(),y)-x.begin()
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
#define N (1<<19)
ll q,typ[N],L[N],R[N],S[N],T[N],VAL[N];
typedef struct segtree2D{
typedef struct segtree{//区間加算、区間和
ll *dat,*laz,*wid;
ll n;
void init(vector<ll> values){//values[i+1]-values[i]の長さのものが|values|-1個並んでる
n=values.size();//配列外参照を防ぐため+1
dat=new ll[2*n];
laz=new ll[2*n];
wid=new ll[2*n];
rep(i,2*n)dat[i]=laz[i]=wid[i]=0;
for(int i=0;i<n-1;i++)wid[i+n]=values[i+1]-values[i];
for(int i=n-1;i>0;i--)wid[i]=wid[i*2]+wid[i*2+1];
}
ll eval(ll k){
if(k<n){
laz[k*2]+=laz[k];
laz[k*2+1]+=laz[k];
}
dat[k]+=laz[k]*wid[k],laz[k]=0;
return dat[k];
}
void add(ll l,ll r,ll val){//[l,r),非再起注意
l+=n,r+=n;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)laz[a++]+=val;
if(b&1)laz[--b]+=val;
}
for(ll a=l,b=r;a+b;a>>=1,b>>=1){
dat[a/2]=eval(a)+eval(a^1);
dat[b/2]=eval(b)+eval(b^1);
}
}
ll sum(ll l,ll r){//[l,r),非再起注意
l+=n,r+=n;
for(ll d=20;~d;d--){
eval(l>>d);
eval(r>>d);
}
ll res=0;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)res+=eval(a),a++;
if(b&1)b--,res+=eval(b);
}
return res;
}
}segtree;
segtree seg[2*N];
vector<ll> values[2*N];
vector<ll> solve(){
rep(i,q){
if(typ[i]==0){//[s,s]*[l,r)にvalを加算
for(ll x=S[i]+N;x;x>>=1){
values[x].push_back(L[i]);
values[x].push_back(R[i]);
}
}
else{//[s,t)*[l,r)の総和を求める
for(ll a=S[i]+N,b=T[i]+N;a<b;a>>=1,b>>=1){
if(a&1){
values[a].push_back(L[i]);
values[a].push_back(R[i]);
a++;
}
if(b&1){
b--;
values[b].push_back(L[i]);
values[b].push_back(R[i]);
}
}
}
}
rep(i,2*N){
sort(all(values[i]));
seg[i].init(values[i]);
}
vector<ll> fans;
rep(i,q){
if(typ[i]==0){//[s,s]*[l,r)にvalを加算
for(ll x=S[i]+N;x;x>>=1){
ll LL=lo(values[x],L[i]);
ll RR=lo(values[x],R[i]);
seg[x].add(LL,RR,VAL[i]);
}
}
else{//[s,t)*[l,r)の総和を求める
ll res=0;
for(ll a=S[i]+N,b=T[i]+N;a<b;a>>=1,b>>=1){
if(a&1){
ll LL=lo(values[a],L[i]);
ll RR=lo(values[a],R[i]);
res+=seg[a].sum(LL,RR);
a++;
}
if(b&1){
b--;
ll LL=lo(values[b],L[i]);
ll RR=lo(values[b],R[i]);
res+=seg[b].sum(LL,RR);
}
}
fans.push_back(res);
}
}
return fans;
}
}segtree2D;
segtree2D seg;
void register_upd(ll t,ll l,ll r,ll val){
typ[q]=0,L[q]=l,R[q]=r,S[q]=t,T[q]=-1,VAL[q]=val;
q++;
}
vector<ll> querysid;
void register_sum(ll s,ll t,ll l,ll r,ll id){
typ[q]=1,L[q]=l,R[q]=r,S[q]=s,T[q]=t;
querysid.push_back(id);
q++;
}
typedef struct rng{//[l,r)では[t,t]*[l,r)が1になっている、
ll l,r,t;
bool operator<(const rng&key)const{
return this->l<key.l;
}
}rng;
set<rng> rngs;//rngの集合、1→nの方向に走査する
void EXAM1(){
ll res=0;
for(auto e:rngs)res+=e.r-e.l;
cerr<<"EXAM:"<<res<<endl;
}
int main(){
ll n,m;
string s;
cin>>n>>m>>s;
vector<P> zerorng[N];//zerorng[i]:=ランプiが消えている区間[fi,sc)の集合
vector<P> querys[N];//querys[b]:=右端がbで、a=fiで、id=scのクエリの集合
{//zerorngとquerysを求める
ll mas[N];//mas[i]:=ランプiが最後に消されたときの時間、現在光っている時は不要
for(int i=1;i<=n;i++)if(s[i-1]=='0')mas[i]=0;
rep(i,m){
string com;
cin>>com;
if(com=="toggle"){
ll x; cin>>x;
if(s[x-1]=='0'){
zerorng[x].push_back(make_pair(mas[x],i+1));
s[x-1]='1';
}
else s[x-1]='0',mas[x]=i;
}
if(com=="query"){
ll a,b; cin>>a>>b;
querys[b-1].push_back(make_pair(a,i));
}
}
for(int i=1;i<=n;i++){
if(s[i-1]=='0'){
zerorng[i].push_back(make_pair(mas[i],m));
}
}
}
q=0;
rngs.insert((rng){0,m,0});
register_upd(0,0,m,+1);
EXAM1();
for(int i=1;i<=n;i++){
for(auto p:zerorng[i]){//ランプが消えている区間のところで、2DSegtreeを更新する。添字がずれている可能性あり
rng x=(rng){p.first,p.second,i};
{//元々あったrngを消して、更新クエリを2Dsegtreeに投げる
auto it=rngs.lower_bound(x);
while(it!=rngs.end()&&it->l<p.second){
if(it->r<=p.second){//[p.fi,p.sc)に完全に含まれている
register_upd(it->t,it->l,it->r,-1);
it=rngs.erase(it);
}
else{//p.fi<=it->l<p.second<it->r
register_upd(it->t,it->l,p.second,-1);
rng news=(rng){p.second,it->r,it->t};
rngs.erase(it);
rngs.insert(news);
break;
}
}
it=rngs.lower_bound(x);
if(it!=rngs.begin()){
it--;
if(it->l<=p.first&&p.second<=it->r){//元々あったものの中に、追加するものを完全に含んでいるものがあった
register_upd(it->t,p.first,p.second,-1);
rngs.erase(it);
}
else{//左側で重なっているもの
register_upd(it->t,p.first,it->r,-1);
rng news=(rng){it->l,p.first,it->t};
rngs.erase(it);
rngs.insert(news);
}
}
}
{//新しいrngをいれて、更新クエリを2DSegtreeに投げる
cerr<<"upd:"<<p.first<<" "<<p.second<<" "<<i<<endl;
rngs.insert((rng){p.first,p.second,i});
register_upd(i,p.first,p.second,+1);
}
EXAM1();
}
for(auto p:querys[i]){//取得クエリを2DSegtreeに投げる
cerr<<"sum:"<<p.first<<" "<<0<<" "<<p.second+1<<" "<<p.second<<endl;
register_sum(p.first,N-1,0,p.second+1,p.second);
}
}
vector<ll> fans=seg.solve();
vector<P> ans;
for(int i=0;i<fans.size();i++){
ans.push_back(make_pair(querysid[i],fans[i]));
}
sort(all(ans));
for(auto t:ans)cout<<t.first+1-t.second<<"\n";
}
Compilation message
street_lamps.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("O3")
street_lamps.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize("unroll-loops")
street_lamps.cpp:19:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
#pragma gcc target("avx2,see4")
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:235:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<fans.size();i++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
181112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5072 ms |
77272 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
187896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
186872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
181112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
