【题解】P12914 [POI 2020/2021 R2] 沙滩游客 / Plażowicze

· · 题解

题意

给定一个有 n 个元素的序列 x，保证 0=x_1<x_2<\dots<x_n=X。给定 z 次询问，每次询问会按照如下规则插入 k 个新元素：

求第 k 个插入元素的值。

思路

每次操作可以理解为把长度最大的区间劈成两半，考虑朴素做法，设一个大根堆，记 pos 为某个区间左端点的位置，len 为这个区间的长度，初始放入所有区间。每次取出堆顶的区间，把它劈成两半再放回堆中即可。

然后我们可以按 k 单调不降排序询问，每次模拟到当前的 k。这样做时间复杂度为 O(k_{\max}\log (n+k_{\max}))，显然无法通过。

由于 k_{\max} 过大，考虑将其优化掉。我们发现一个区间被劈成两半后的两个区间本质是相同的，所以我们可以记 cnt 为这个区间包含几半，len 为每半的长度，pos 为这个区间的左端点位置。弹出堆顶区间后可以发现必然会从左往右把这个区间的几半再劈开，所以共插入 cnt 个新元素，其中第 k 个被加入的元素值为 pos+len\times(k-1)+\displaystyle\frac{len}{2}。之后我们只需把 len 减半，cnt 翻倍，再放入堆中即可。

由于每轮操作最多 N 次弹出堆顶，最少让堆中所有的 cnt 翻倍，所以总的时间复杂度为 O(n\log k_{\max}\log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct fact{int x,y;};
bool operator<(const fact x,const fact y){return x.x*y.y<y.x*x.y;}
bool operator>(const fact x,const fact y){return x.x*y.y>y.x*x.y;}
bool operator==(const fact x,const fact y){return x.x*y.y==y.x*x.y;}
bool operator!=(const fact x,const fact y){return x.x*y.y!=y.x*x.y;}
struct data1{int k,id;}ask[N];
bool cmp(data1 x,data1 y){return x.k<y.k;}
struct data2
{
    int pos,cnt;
    fact len;
};
bool operator<(const data2 x,const data2 y){return(x.len!=y.len?x.len<y.len:x.pos>y.pos);}
bool operator>(const data2 x,const data2 y){return(x.len!=y.len?x.len>y.len:x.pos<y.pos);}
int a[N];
fact ans[N];
void solve()
{
    int n,len,q;
    cin>>n>>len>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++)cin>>ask[i].k,ask[i].id=i;
    sort(ask+1,ask+q+1,cmp);
    priority_queue<data2>heap;
    for(int i=2;i<=n;i++)heap.push({a[i-1],1,{a[i]-a[i-1],1}});
    int sum=0;
    for(int i=1;;)
    {
        auto now=heap.top();
        heap.pop();
        fact tmp=now.len;
        if((tmp.x&1)^1)tmp.x>>=1;
        else tmp.y<<=1;
        while(i<=q&&sum+now.cnt>=ask[i].k)
        {
            int id=ask[i].id;
            ans[id]={now.pos*now.len.y+now.len.x*(ask[i].k-sum-1),now.len.y};
            if(now.len.y!=tmp.y)ans[id].x<<=1,ans[id].y<<=1;
            ans[id].x+=tmp.x,i++;
        }
        if(i>q)break;
        heap.push({now.pos,now.cnt<<1,tmp});
        sum+=now.cnt;
    }
    for(int i=1;i<=q;i++)
    {
        int gcd=__gcd(ans[i].x,ans[i].y);
        cout<<ans[i].x/gcd<<'/'<<ans[i].y/gcd<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    for(;_;_--)solve();
    return 0;
}