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

题意

给定一个有

n

个元素的序列

x

，保证

0=x_1<x_2<\dots<x_n=X

。给定

z

次询问，每次询问会按照如下规则插入

k

个新元素：

令 $p$ 为满足 $x_{i+1}-x_i$ 最大的 $i$ 中的最小值，在 $x_p$ 和 $x_{p+1}$ 中插入 $\displaystyle\frac{x_p+x_{p+1}}{2}$ 。

求第

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)

。

代码

CPP

#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;
}

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

文章操作

题意

思路

代码

相关推荐

评论

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