题目链接
题目链接
题目大意
一共有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<<i<<" "<<cnt[tot][i]<<endl;}}else {for(int i=0;i<=r;i++){cnt[tot][i]+=v;}for(int i=l;i<tot;i++){cnt[tot][i]+=v;}}
}代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef pair<int ,int >PII;
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<<i<<" "<<cnt[tot][i]<<endl;}}else {for(int i=0;i<=r;i++){cnt[tot][i]+=v;}for(int i=l;i<tot;i++){cnt[tot][i]+=v;}}
}
int query(int pos)
{int ans=0;for(int i=2;i<=sqrt(m);i++){ans+=cnt[i][pos%i];} return ans;
}
int main()
{cin>>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<<ans<<endl;printf("%d\n",ans + query(i));}return 0;}