根号思想

根号思想

我也不知道这个标题应该放在哪个分类下了...工(　)。゜新开一栏吧

直接上例题

1.1 例题

题意很好理解：有\(n\)种车，接下来要计算\(m\)天的数据。在第\(i\)天，如果第\(j\)种车投入使用，则从这天起，它将会进入运行\(x_j\)天，维修\(y_j\)的循换；如果第\(j\)种车停止使用，则从这天起，它不再运行或维修。

2.1 解法

既然题目都是根号思想了，那就直接开始一个论的讨。

如果\(x_i+y_i>\sqrt{m}\)，那么就在一个差分数组上暴力维护一个区间加减。因为\(x_i+y_i>\sqrt{m}\),所以遍历\(m\)天的复杂度是\(O(\sqrt{m})\)

如果\(x_i+y_i\leq\sqrt{m}\)，这种情况又是另一种暴力方式。开一个数组\(f[a][b]\)表示的是对于所有\(x_i+y_i=a\)的车，在天数\(t\)对模\(a\)意义下为\(b\)时，有多少辆车需要维修。如果一辆车上次维修日期是\(s_i\)的话，那么当\((t-s_i) \%(x_i+y_i)\)等于\(0\)或\(>x_i\)时，它就需要维修。

每次新加入一辆车，就暴力更新对应的\(f[a]\)

inline void modify(int id,int val){
	int tot=x[id]+y[id],*c=cnt[tot];
	for(register int i=0;i<tot;++i){
		int now=(tot+i-s[id])%tot;
		if(!now||now>x[id]) c[i]+=val;
	}
}

在第\(t\)天则需要求\(\sum f[i][t\%i]\)

inline int query(int tim){
	int ans=0;
	for(register int i=2;i<=S;++i) ans+=cnt[i][tim%i];
	return ans;
}

修改、查询复杂度都是\(O(\sqrt m)\)

2.2 code

#include <bits/stdc++.h>
using namespace std;
#define lor(a,b,c) for(register int a=b;a<=c;++a)
#define ror(a,b,c) for(register int a=c;a>=b;--a)

char buf[1<<21],*p1=buf,*p2=buf;
template <typename T> inline T read(){
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	char tmp=gc(); T sum=0;
	while(tmp<'0'||tmp>'9') tmp=gc();
	while(tmp>='0'&&tmp<='9') sum=(sum<<1)+(sum<<3)+tmp-'0',tmp=gc();
	return sum;
}

const int N=2e5+5,M=sqrt(N)+5;
int n,m,x[N],y[N],s[N],S,pre[N],sum,cnt[M][M];

inline void modify(int id,int val){
	int tot=x[id]+y[id],*c=cnt[tot];
	int l=(x[id]+s[id]+1)%tot,r=s[id];
	if(l<=r) lor(i,l,r) c[i]+=val;
	else{
		for(register int i=0;i<=s[id];++i) c[i]+=val;
		for(register int i=(x[id]+s[id]+1)%tot;i<tot;++i) c[i]+=val;
	}
}

inline int query(int tim){
	int ans=0;
	for(register int i=2;i<=S;++i) ans+=cnt[i][tim%i];
	return ans;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	#endif
	ios::sync_with_stdio(false); cin.tie(0);

	n=read<int>(); m=read<int>(); lor(i,1,n) x[i]=read<int>(),y[i]=read<int>();
	S=sqrt(m);
	lor(qwq,1,m){
		int op=read<int>(),k=read<int>();
		switch(op){
			case 1:
				if(x[k]+y[k]>S){
					s[k]=qwq-1;
					for(register int pos=qwq+x[k];pos<=m;pos+=x[k]+y[k]){
						pre[pos]++;
						if(pos+y[k]<=m) pre[pos+y[k]]--;
					}
				}
				else {s[k]=(qwq-1)%(x[k]+y[k]); modify(k,1);}
				sum+=pre[qwq];
			break;
			case 2:
				if(x[k]+y[k]>S){
					sum+=pre[qwq];
					for(register int pos=s[k]+1+x[k];pos<=m;pos+=x[k]+y[k]){
						pre[pos]--;
						if(pos+y[k]<=m) pre[pos+y[k]]++;
					}
					int now=(qwq-s[k])%(x[k]+y[k]);
					if(!now||now>x[k]) sum--;
				}
				else modify(k,-1);
			break;
		}
		printf("%d\n",sum+query(qwq));
	}

	return 0;
}