题目链接
题目大意一共有n个列车 每个列车有运行时间和休息时间
有m天 每天进行一次操作 分别是添加某列车和去除某列车
添加某列车后 该列车先运行然后休息然后运行
问你每天里有多少个列车在休息
题目思路看官方题解没看明白 感谢这位大佬指点
当每个列车的运行时间x和休息时间y很长时
可以用差分来朴素的求解
但是当时间很紧密的时候时间复杂度 n^2 肯定会超时
所以考虑去分块
对于x+y小于sqrt(m)的部分 我们进行特殊处理
对于st+x到st+x+y-1的部分加1 但是st+x+（x+y）到st+x+y-1+（x+y）等 后面的取余x+y与之前相等的区间也需要+1 例如下图
我们考虑把这区间对x+y取模
这里画了一张很傻的图 意思是上面的本来很多的区间可以化简为一个区间
而这样的区间 由原来的可能有无数多个 变为一个
由原来的无数多种（长度）变成了 只有 根号下m种 长度
在后续的query函数中 我们只需要对当前的位置也进行相应取模x+y的值 即可判断这里的值
void updata(int st,int pos,int v)
{
int tot=e[pos].p.first+e[pos].p.second;
int x=e[pos].p.first;
int y=e[pos].p.second;
int l=(st+x)%tot;//开始休息的地方
int r=(st-1)%tot;//结束休息的地方
//这两个lr 对tot取余之后不一定谁大
if(l<=r)
{
for(int i=l;i<=r;i++)
{
cnt[tot][i]+=v;
//cout<
代码
#include
using namespace std;
const int maxn=2e5+10;
typedef pairPII;
int n,m;
int vis[maxn];
int sum[maxn];
int cnt[505][505];
struct node
{
PII p;
}e[maxn];
void updata(int st,int pos,int v)
{
int tot=e[pos].p.first+e[pos].p.second;
int x=e[pos].p.first;
int y=e[pos].p.second;
int l=(st+x)%tot;
int r=(st-1)%tot;
if(l<=r)
{
for(int i=l;i<=r;i++)
{
cnt[tot][i]+=v;
//cout<>n>>m;
int sqr=sqrt(m);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&e[i].p.first,&e[i].p.second);
}
int op,pos;
int ans=0;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&op,&pos);
int tot=e[pos].p.first+e[pos].p.second;
int x=e[pos].p.first;
int y=e[pos].p.second;
if(op==1)
{
if(tot>sqr)
{
for(int j=i+x;j<=m;j+=tot)
{
sum[j]++;
if(j+y<=m)sum[j+y]--;
}
}
else
{
updata(i,pos,1);
}
vis[pos]=i;
}
else
{
if(tot>sqr)
{
for(int j=vis[pos];j<=m;j+=tot)
{
if(j+x<=i-1)ans--;
if(j+x+y<=i-1)ans++;
if(j+x<=m)sum[j+x]--;
if(j+x+y<=m)sum[j+x+y]++;
}
}
else
{
updata(vis[pos],pos,-1);
}
}
ans+=sum[i];
//cout<
