题解：P9000 [CEOI 2022] Measures

FS_NEO · 2025-11-10 16:39:10 · 题解

先转换一波：每轮动完，将每个人都向右移动一格。于是三种移动变为：不动，向右移动一格，向右移两格。

设初始位置 a_i，最终位置 f_i，容易得到递推：

展开得：

则答案为 \max(\: \frac{a_j+D \times (i-j) -a_i }{2} \:)，线段树上用脚维护。

/*

        2025.11.10

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
const int MAXN=1000005,inf=0x3f3f3f3f3f3f3f3f;
int n,m,D,rev[MAXN];
P a[MAXN];
struct node{
    int l,r,mn,mx,ans,d;
}tree[MAXN*4];
void up(int x){
    tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
    tree[x].mn=min(tree[x*2].mn,tree[x*2+1].mn);
    tree[x].ans=max(max(tree[x*2].ans,tree[x*2+1].ans),tree[x*2+1].mx-tree[x*2].mn);
}
void build(int x,int l,int r){
    tree[x].l=l,tree[x].r=r;
    if(l==r){
        tree[x].mn=inf,tree[x].mx=-inf,tree[x].ans=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    up(x);
}
void down(int x){
    int &t=tree[x].d;
    tree[x*2].mn+=t,tree[x*2].mx+=t,tree[x*2].d+=t;
    tree[x*2+1].mn+=t,tree[x*2+1].mx+=t,tree[x*2+1].d+=t;
    t=0;
}
void add(int x,int l,int r,int t){
    if(tree[x].l>=l&&tree[x].r<=r){
        tree[x].mn+=t,tree[x].mx+=t,tree[x].d+=t;
        return ;
    }
    if(tree[x].d)down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(l<=mid)add(x*2,l,r,t);
    if(r>mid)add(x*2+1,l,r,t);
    up(x);
}
void change(int x,int l,int t){
    if(tree[x].l==tree[x].r){
        tree[x].mx=tree[x].mn=tree[x].mn-inf-t;
        return ;
    }
    if(tree[x].d)down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(l<=mid)change(x*2,l,t);
    else change(x*2+1,l,t);
    up(x);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m>>D;
    for(int i=1;i<=n;i++)cin>>a[i].fi,a[i].se=i;
    for(int i=1;i<=m;i++)cin>>a[i+n].fi,a[i+n].se=i+n;
    sort(a+1,a+1+n+m);
    for(int i=1;i<=n+m;i++)rev[a[i].se]=i;
    build(1,1,n+m);
    for(int i=1;i<=n;i++){
        int t=rev[i];
        if(t<n+m)add(1,t+1,n+m,D);
        change(1,t,a[t].fi);
    }
    for(int i=n+1;i<=n+m;i++){
        int t=rev[i];
        if(t<n+m)add(1,t+1,n+m,D);
        change(1,t,a[t].fi);
        if(tree[1].ans%2)cout<<tree[1].ans/2<<".5 ";
        else cout<<tree[1].ans/2<<" ";
    }
    return 0;
}