题解 P7971 【[KSN2021] Colouring Balls】

· · 题解

problem

交互库有一个长为 n 的颜色序列，你可以询问区间 [l,r] 中有多少种颜色，最后还原交互库手中的序列，只需要保持相对顺序不变。n\leq 10^3，最多询问次数 Q=2000 或 Q=10^4。

solution

令 C 为 [1,n] 的颜色种类数，一开始就 query(1,n) 一次。

C=1,C=n：Q=O(1)

？

相同颜色连续：Q=O(n)

做一个类似于去重的工作，把相邻两个颜色相同的（query(i-1,i)=1）合并成同一种颜色。因为相同颜色连续，所以不需要考虑其它，这样就能通过 T\leq 2 的测试点。

C=3：Q=O(n)

考虑先去重，去掉相邻的相同颜色。对于连续的 a,b,c 的颜色块，如果

这样就能通过 T=3 的测试点。

C=n-1：Q=O(n)

因为 C=n-1，所以一定存在一对 i,j 使得这两个下标的颜色相同。

考虑一个包含了 [i,j] 的区间，这一段区间里一定有 len-1 种颜色。那么令 l=1,r=n，让 l 一直往右扫，r 一直往左扫，什么时候 query(l,r)=r-l+1，那么就找到了 i,j。这样就通过了 T=5 的测试点

通解：Q=O(n\log n)

考虑一遍扫过去，用 [1,i-1] 的颜色求出 i 的颜色。

对于 i，假设我们有一个编号 k：

发现 query(k,i) 有单调性，试图二分 k\in[1,i-1]，于是你解决了 T=6 和 T=7 的测试点。

Q=O(n\log C) 及小优化

动态维护一个 pre_c 表示颜色为 c 的最大的编号，这样，query(k,i-1) 就等同于有多少个 pre_c 落在 [k,i-1] 中。把所有有意义的 pre_c 的值拉出来排序（容易发现只有 O(C) 个），对着排序的 pre 二分，那么就能通过 T=3 的测试点。注意到因为 n\leq 10^3，所以排序部分直接写 O(n^2+n\cdot C \log C)) 的时间复杂度也能过。

还不能通过 T=4 的测试点，因为这样每个颜色需要询问 3 次，需要优化。这个优化很简单：如果 \color{red}{C}=4（而不是 T=4），当前有意义的 pre 恰有 C 个，那么不需要特判 i 是新颜色的情况，这是不可能的，询问次数降为 2 次（若 pre 有 3 个那么只需要询问 2 次）。于是可以通过 T=4 的测试点。

code

实现时可以用并查集。

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<int N> struct dsu{
    int fa[N+10],siz[N+10],cnt;
    dsu(int n=N):cnt(n){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void merge(int x,int y){
        if(x=find(x),y=find(y),x!=y){
            if(siz[x]<siz[y]) swap(x,y);
            cnt--,siz[x]+=siz[y],fa[y]=x;
        }
    }
};
int n,T,f[1010][1010],last[1010],p[1010];
dsu<1010> s;
int query(int l,int r){
    if(l>r) swap(l,r);
    if(f[l][r]==-1){
        printf("? %d %d\n",l,r);
        fflush(stdout);
        scanf("%d",&f[l][r]);
    }
    return f[l][r];
}
int flower(){
    int cnt=0;
    p[++cnt]=1;
    for(int i=2;i<=n;i++){
        if(query(p[cnt],i)==1) s.merge(p[cnt],i);
        else p[++cnt]=i;
    }
    return cnt;
}
int main(){
    memset(f,-1,sizeof f);
    scanf("%d%d%*d",&T,&n);
    if(T==1||T==2) flower();
    else if(query(1,n)==n-1){
        int L=1,R=n;
        while(query(n,L)==n-L) L++;
        while(query(R,1)==R-1) R--;
        s.merge(L-1,R+1);
    }else if(query(1,n)==3){
        int cnt=flower();
        if(query(p[1],p[3])==2) s.merge(p[1],p[3]);
        for(int i=4;i<=cnt;i++){
            if(query(p[i-2],p[i])==2) s.merge(p[i-2],p[i]);
            else{
                set<int> fs;
                for(int j=1;j<i;j++) fs.insert(s.find(p[j]));
                fs.erase(s.find(p[i-1]));
                fs.erase(s.find(p[i-2]));
                if(!fs.empty()) s.merge(*fs.begin(),p[i]);
            }
        }
    }else if(query(1,n)!=n){
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=1000;j++) if(last[j]) p[++cnt]=last[j];
            sort(p+1,p+cnt+1);
            int L=1,R=cnt;
            while(L<R){
                int mid=(L+R+1)>>1;
                if(query(p[mid],i)==cnt-mid+1) L=mid;
                else R=mid-1;
            }
            if(query(1,n)==cnt||!cnt||query(p[L],i)==cnt-L+1) s.merge(p[L],i);
            last[s.find(i)]=i;
        }
    }
    printf("! ");
    for(int i=1;i<=n;i++) printf("%d%c",s.find(i)," \n"[i==n]);
    fflush(stdout);
    return 0;
}
/*
1213
*/