题解：P11910 [THSPC 2023] I. 对战机器马

· · 题解

题目传送门

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

题目分析

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

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

分两种情况讨论：

显然可以先离散化。因为在一个小段中无论 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;
}