http://acm.hdu.edu.cn/showproblem.php?pid=4031
【题意】
- 有一个长为n的长城，进行q次操作，d为防护罩的冷却时间，Attack表示区间a-b的墙将在1秒后受到攻击，
- 询问表示计算第a块墙受到攻击的次数，被防护罩抵消的不算
【思路】
- 总的攻击次数-防护罩抵消的次数
- 总的攻击次数可以树状数组维护
- 防护罩抵消的模拟
【AC】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,t;
const int maxn=2e4+;
int a[maxn];
int l[maxn],r[maxn];
int cur[maxn];
int sum[maxn];
int tree[maxn];
int cnt; void init()
{
memset(tree,,sizeof(tree));
cnt=;
memset(l,,sizeof(l));
memset(r,,sizeof(r));
memset(cur,,sizeof(cur));
memset(sum,,sizeof(sum));
}
int lowbit(int x)
{
return x&-x;
}
void add(int k,int x)
{
while(k<=n)
{
tree[k]+=x;
k+=lowbit(k);
}
}
int query(int k)
{
int ans=;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
int solve(int x)
{
int i=cur[x];
while(i<cnt)
{
if(x>=l[i]&&x<=r[i])
{
sum[x]++;
i+=t;
cur[x]=i;
}
else
{
i++;
}
}
return sum[x];
}
int main()
{
int T;
scanf("%d",&T);
int cas=;
while(T--)
{
init();
scanf("%d%d%d",&n,&q,&t);
printf("Case %d:\n",++cas);
char op[];
while(q--)
{
scanf("%s",op);
if(op[]=='A')
{
int x,y;
scanf("%d%d",&x,&y);
l[cnt]=x;r[cnt++]=y;
add(x,);
add(y+,-);
}
else
{
int x;
scanf("%d",&x);
int ans=query(x);
int delta=solve(x);
ans-=delta;
printf("%d\n",ans);
}
}
}
return ;
}