Codeforces Round #655 (Div. 2) F.Omkar and Modes(交互 题-分治+二分/纯分治)

题目

n(n<=2e5)个数的数组a[]，ai在[1,1e9]间，数组内的数是非严格单增的，

现在需要猜出这个数组，

每次询问输入，? l r，代表询问[l,r]的众数，系统会返回这个区间内众数x及其次数f，

如存在多个众数，则会返回最小的那个，

保证数组内的不同元素数量为k(k<=min(n,25000))，

但k未知，你需要不超过4*k次询问，询问出这个数组，最后输出不算次数

交互题日常，输出完之后fflush(stdout)

思路来源

CF 1372F Omkar and Modes_WAautomaton的博客-CSDN博客

CF 1372F - Omkar and Modes （交互题）_wineandchord的博客-CSDN博客

题解1

设对[l,r]中询问x得到了次数f，并且已经知道了一个x的位置mid，

mid把f个数划分成了前后两半，f奇数则必有一半超过f/2个x，

f偶数则最坏情况两半均等于f/2个x，但后面那半会因为数小而留下

则[mid-f+1,mid]这前f个数和[mid,mid+f-1]这后f个数中，必有一个区间，x是众数，

最坏情况，对两个区间都询问一下，

由于一个端点固定在mid，必能得到另一个端点，从而得到完整区间

所以先对[l,r]询问一次，然后如果能用一次得到一个x的位置，

再询问最多两次，就能找到x的位置[xl,xr]，

然后分治[l,xl-1]和[xr+1,r]即可

考虑如何得到x的位置，实际上是均摊的每个数恰一次，

mp[x]=y代表已经得到了x的一个位置y，

先二分一下x，如果x已经在map里存在了直接返回

否则去<x的数里已经找到位置的最大的数，记为v，

从v的位置后f个起，在[l,r]区间，往后f个f个找，这样由于x是f个的最小的，

在前面找的数必两两不同，为其贡献了新的一些数的位置，

且由于x出现了f次，间隔为f的找必不会错过x，

找到x的位置之后，执行前文提到的操作即可

题解2（2022.10.31补充）

感觉很妙，考虑最坏的情况，是每个数都不同的情况，这时折半递归类似于建线段树的过程，

线段树建[1,n]所需的节点不超过4*n，因此对[1,n]询问的次数折半递归询问不超过4*n次，

另一种情况，区间众数超过整个区间的一半，

如：[1,7]中区间众数x出现5次，则能说明[3,5]一定是x，取[1,5]和[3,7]的交集即可得到

这种情况下，整个区间递归的两个子区间长度有所减少，使得总递归次数一定不超过4*n

代码1

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
int n,a[N];
void ask(int l,int r,int &x,int &f){
    printf("? %d %d\n",l,r);
    fflush(stdout);
    scanf("%d%d",&x,&f);
}
void dfs(int l,int r){
    if(l>r){
        return;
    }
    int x,f;
    ask(l,r,x,f);
    if(r-l+1==f){
        mp[x]=l;
        for(int i=l;i<=r;++i){
            a[i]=x;
        }
        return;
    }
    auto p=mp.lower_bound(x);
    //找到x的mp的位置
    int xl,xr,nx,nf,mid;
    if(p!=mp.end() && p->first==x){
        mid=p->second;
    }
    else{
        p--;
        int a,b;
        for(int i=max(l,p->second+f);i<=r;i+=f){
            ask(i,i,a,b);
            mp[a]=i;
            if(a==x){
                mid=i;
                break;
            }
        }
    }
    ask(max(l,mid-f+1),mid,nx,nf);
    if(nx==x){
        xl=mid-nf+1;
        xr=xl+f-1;
    }
    else{
        ask(mid,min(r,mid+f-1),nx,nf);
        xr=mid+nf-1;
        xl=xr-f+1;
    }
    for(int i=xl;i<=xr;++i){
        a[i]=x;
    }
    dfs(l,xl-1);
    dfs(xr+1,r);
}
int main(){
    mp[0]=0;//二分前驱的最小
    scanf("%d",&n);
    dfs(1,n);
    printf("!");
    for(int i=1;i<=n;++i){
        printf(" %d",a[i]);
    }
    fflush(stdout);
    return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N];
void ask(int l,int r,int &x,int &f){
    printf("? %d %d\n",l,r);
    fflush(stdout);
    scanf("%d%d",&x,&f);
}
void dfs(int l,int r){
    if(l>r){
        return;
    }
    int x,f;
    ask(l,r,x,f);
    int nr=r-f+1,nl=l+f-1;
    if(nr<=nl){
        for(int i=nr;i<=nl;++i){
            a[i]=x;
        }
        dfs(l,nr-1);
        dfs(nl+1,r);
    }
    else{
        int mid=(l+r)/2;
        dfs(l,mid);
        dfs(mid+1,r);
    }
}
int main(){
    scanf("%d",&n);
    dfs(1,n);
    printf("!");
    for(int i=1;i<=n;++i){
        printf(" %d",a[i]);
    }
    fflush(stdout);
    return 0;
}