This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cstring> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
const int N=20005; | |
const int PP=150; | |
const int INF=1000000000; | |
int Tc,n,Q,per,m; | |
int CC; | |
int Time[N]; | |
int Sum[N]; | |
char Str[105]; | |
int Tr[N]; | |
struct Node{ | |
int F[55]; | |
int pre[55]; | |
int T; | |
int l,r; | |
void push_down(){ | |
bool flag=false; | |
for (int i=0;i<=per;i++) | |
if (F[i]){ | |
flag=true; | |
break; | |
} | |
if (flag) | |
for (int i=l;i<=r;i++){ | |
int c=T-Time[i]; | |
if (c>per) c=per; | |
Time[i]=pre[c]; | |
Sum[i]+=F[c]; | |
} | |
T=CC; | |
for (int i=0;i<=per;i++){ | |
F[i]=0; | |
pre[i]=CC-i; | |
} | |
} | |
}S[PP]; | |
void Build(){ | |
for (int i=1;i<=n;i++){ | |
if (i==1 || i%PP==0) | |
S[i/PP].l=i; | |
S[i/PP].r=i; | |
S[i/PP].T=-INF; | |
} | |
m=n/PP; | |
for (int i=0;i<=m;i++){ | |
for (int j=0;j<=per;j++){ | |
S[i].F[j]=0; | |
S[i].pre[j]=S[i].T-j; | |
} | |
} | |
} | |
void Simple(int l,int r){ | |
for (int i=l;i<=r;i++) | |
if (CC-Time[i]>=per){ | |
Time[i]=CC; | |
Sum[i]++; | |
} | |
} | |
void Add(int i,int x){ | |
for (;i<=n;i+=i&-i) Tr[i]+=x; | |
} | |
int Get_Sum(int i){ | |
int ret=0; | |
for (;i;i-=i&-i) ret+=Tr[i]; | |
return ret; | |
} | |
void Gao1(){ | |
++CC; | |
int l,r; | |
scanf("%d%d",&l,&r); | |
Add(l,1); | |
Add(r+1,-1); | |
if (l/PP==r/PP){ | |
S[l/PP].push_down(); | |
Simple(l,r); | |
return; | |
} | |
int St=l/PP; if (l==S[St].l) St--; | |
int Ed=r/PP; if (r==S[Ed].r) Ed++; | |
for (int i=St+1;i<Ed;i++){ | |
for (int j=0;j<=per;j++) | |
if (CC-S[i].pre[j]>=per){ | |
S[i].pre[j]=CC; | |
S[i].F[j]++; | |
} | |
} | |
if (St>=0 && S[St].r>=l){ | |
S[St].push_down(); | |
Simple(l,S[St].r); | |
} | |
if (Ed<=m && S[Ed].l<=r){ | |
S[Ed].push_down(); | |
Simple(S[Ed].l,r); | |
} | |
} | |
void Gao2(){ | |
int p; | |
scanf("%d",&p); | |
S[p/PP].push_down(); | |
printf("%d\n",Get_Sum(p)-Sum[p]); | |
} | |
int main(){ | |
scanf("%d",&Tc); | |
for (int k=1;k<=Tc;k++){ | |
printf("Case %d:\n",k); | |
scanf("%d%d%d",&n,&Q,&per); | |
for (int i=1;i<=n;i++) { Time[i]=-INF; Sum[i]=0; Tr[i]=0; } | |
Build(); | |
CC=0; | |
for (int i=0;i<Q;i++){ | |
scanf("%s",Str); | |
if (Str[0]=='A') | |
Gao1(); | |
else | |
Gao2(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment