自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 23:11:18，当前版本为作者最后更新于2025-03-17 20:33:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

其实是很简单的题 ，但赛时脑抽了没写出来，赛后 40min 才过。

题目分析

考虑在什么情况下 $(b_i+x)\bmod P > a_i$。

我们显然只需考虑 $0\le x<P$ 的情况，其余在模 $P$ 意义下依然可以化为这种情况。

分两种情况讨论：

• $a_i\ge b_i$

  此时比较显然，需满足 $a_i<b_i+x<P$，解得 $a_i-b_i+1\le x\le P-b_i-1$。

• $a_i<b_i$

  此时有两种情况：

  当 $b_i+x<P$ 时，只需满足 $0\le x\le P-b_i-1$。

  当 $b_i+x\le P$ 时，此时 $(b_i+x)\bmod P = b_i+x-P$，需满足 $b_i+x-P > a_i$，即 $a_i-b_i+P+1\le x\le P-1$。

显然可以先离散化。因为在一个小段中无论 $x$ 取什么值答案都不变。

然后考虑枚举 $s$，此时我们需要将所有包括 $s$ 的数都去掉，对于剩下的，我们可以将这些区间扔到线段树上，然后求最大值就行了。

在枚举 $s$ 的过程中，考虑在进一个数的区间时删掉这个数的贡献，在出一个数的区间时加回这个数的贡献。这样总的操作次数为 $O(n)$。于是总复杂度 $O(n\log n)$。

AC Code

// by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
//bool Mst;
const int N=1e6+5;
int a[N],b[N],lsh[N];
int t[N<<2],tag[N<<2];
vector<int> in[N],out[N];
inline int ls(int id){return id<<1;}
inline int rs(int id){return id<<1|1;}
inline void push_up(int id){t[id]=max(t[ls(id)],t[rs(id)]);}
inline void __upd(int id,int x){t[id]+=x,tag[id]+=x;}
inline void push_down(int id){__upd(ls(id),tag[id]),__upd(rs(id),tag[id]),tag[id]=0;}
void update(int l,int r,int v,int id,int nl,int nr)
{
	if(l<=nl&&r>=nr) return __upd(id,v),void();
	push_down(id);
	int m=(nl+nr)>>1;
	if(l<=m) update(l,r,v,ls(id),nl,m);
	if(r>m) update(l,r,v,rs(id),m+1,nr);
	push_up(id);
}
int qry(){return t[1];}
#define root 1,1,c
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,p,c=0,res=0,ans=0;
	cin>>n>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=b[i]) lsh[++c]=a[i]-b[i]+1,lsh[++c]=p-b[i]-1;
		else lsh[++c]=0,lsh[++c]=p-b[i]-1,lsh[++c]=a[i]-b[i]+1+p,lsh[++c]=p-1;
	}
	sort(lsh+1,lsh+c+1),c=unique(lsh+1,lsh+c+1)-lsh-1;
	auto g=[&](int x){return lower_bound(lsh+1,lsh+c+1,x)-lsh;};
	auto upd=[&](int i,int v)
	{
		if(a[i]>=b[i])
		{
			if(a[i]-b[i]+1<=p-b[i]-1) update(g(a[i]-b[i]+1),g(p-b[i]-1),v,root);
		}
		else
		{
			update(g(0),g(p-b[i]-1),v,root);
			if(a[i]-b[i]+1+p<=p-1) update(g(a[i]-b[i]+1+p),g(p-1),v,root);
		}
	};
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=b[i])
		{
			if(a[i]-b[i]+1<=p-b[i]-1) in[g(a[i]-b[i]+1)].push_back(i),out[g(p-b[i]-1)].push_back(i);
		}
		else
		{
			in[g(0)].push_back(i),out[g(p-b[i]-1)].push_back(i);
			if(a[i]-b[i]+1+p<=p-1) in[g(a[i]-b[i]+1+p)].push_back(i),out[g(p-1)].push_back(i);
		}
	}
	for(int i=1;i<=n;i++) upd(i,1);
	for(int k=1;k<=c;k++)
	{
		for(int i:in[k]) upd(i,-1),res++;
		ans=max(ans,res+qry());
		for(int i:out[k]) upd(i,1),res--;
	}
	cout<<ans<<"\n";
	return 0;
}