P8150

· · 题解

Solution

感觉难点在于如何想到三分。

很明显，如果我们确定了最小值的位置（显然，必须确定最小值的位置，然后找到其具体值），就可以往左右两端拓展，用 n-1 次 get 操作即可确定整个数列。

一个自然的想法是用二分，每次看最小值在左区间内还是在右区间内。但是我们很容易察觉到，我们找不到判断最小值在哪个区间内的方法。

于是考虑三分。我们取区间 [l,r] 的两个三等分点 p_1 和 p_2，这个区间被分成了 [l,p_1]，[p_1+1,p_2-1]，[p_2,r] 三个区间。

然后又有一个我感觉想不到的操作。考虑 \text{query}(l,p_2-1)-\text{query}(l,p_1) 和 \text{query}(p_1+1,r)-\text{query}(p_2,r)。

很明显，他们的 \sum 项最终结果都是相同的，为 \sum_{i=p_1+1}^{p_2-1} a_i。因此如果我们比较两个值的相对关系，我们只需要比较 \min_{i=l}^{p_2-1} a_i-\min_{i=l}^{p_1} a_i 和 \min_{i=p_1+1}^{r} a_i - \min_{i=p_2}^{r} a_i。

由于所有数互不相同，我们取三个区间的最小值分别是 x，y，z。他们之间的相对值无非六种情况，作为新时代的 OIer 应该具有坚实的分类讨论基础。于是我们要比较 \min\{x,y\}-x 和 \min\{y,z\} - z。

所以考虑最小值在三个区间内的所有情况：

然后你发现有一个很头疼的问题：如果我们找到的两个值并不相同，那么我们很容易舍掉最左边或者最右边的一个区间。

但是如果两个值相同，我们如何舍去最中间那个区间呢？

答曰：直接把他们删掉。因为最小值一定不在这里面，所以我们可以忽略不计，把左右区间拼起来即可。

实现的时候考虑搞一个双向链表，然后暴力找三等分点。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
uint64_t query(int l, int r);
uint32_t get(int x);
const int MAXN=1e6+10;
uint32_t nxt[MAXN],pre[MAXN],hd,tl,len;
void del(uint32_t pos) {
    len--;
    uint32_t u=pre[pos],v=nxt[pos];
    nxt[u]=v,pre[v]=u;
    return ;
}
uint32_t get_kth(uint32_t k) {
    uint32_t ans=0;
    ffor(i,1,k) ans=nxt[ans];
    return ans; 
}
void dele(uint32_t l,uint32_t r) {
    vector<uint32_t> aim;
    uint32_t ans=0;
    while(ans<l) ans=nxt[ans];
    while(ans<=r) aim.push_back(ans),ans=nxt[ans];
    for(auto id:aim) del(id);
    return ;    
}

std::vector<uint32_t> recover(int n) {
    vector<uint32_t> ans(n);
    hd=0,tl=n+1,len=n;
    ffor(i,1,n) nxt[i]=i+1,pre[i]=i-1;
    nxt[0]=1,pre[n+1]=n;
    while(len>2) {
        uint32_t l=nxt[hd],r=pre[tl],p1=get_kth(len/3),p2=get_kth(len-len/3+1);
        uint64_t val1=query(l,p2-1)-query(l,p1),val2=query(p1+1,r)-query(p2,r);
        if(val1<val2) dele(p2,r);
        else if(val1>val2) dele(l,p1);
        else dele(nxt[p1],pre[p2]);
    }
    uint32_t mnpos;
    if(len==1) mnpos=nxt[hd],ans[mnpos-1]=get(mnpos);
    else {
        uint32_t pos1=nxt[hd],pos2=pre[tl],val1=get(pos1),val2=get(pos2);
        if(val1<val2) mnpos=pos1,ans[mnpos-1]=val1; 
        else mnpos=pos2,ans[mnpos-1]=val2;
    }
    uint64_t lst=ans[mnpos-1];
    ffor(i,mnpos+1,n) {
        uint64_t val=query(mnpos,i)+ans[mnpos-1];
        ans[i-1]=val-lst,lst=val;   
    }
    lst=ans[mnpos-1];
    roff(i,mnpos-1,1) {
        uint64_t val=query(i,mnpos)+ans[mnpos-1];
        ans[i-1]=val-lst,lst=val;   
    }
    return ans;
}

不得不说，交互题属实有点。