posted on 2022-10-08 19:07:28 | under 题解 | source
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\) 的颜色块，如果
- \(query(a,c)=1\)，这可能吗？
- \(query(a,c)=2\)，可以推出 \(a\) 的颜色和 \(c\) 的颜色相同。
- \(query(a,c)=3\)，这三个颜色互不相同，假设我们已经知道 \(a,b\) 的颜色，那么 \(c\) 就是异于它们的第三种颜色。实现时暴力找出 \([1,b]\) 中有什么颜色，最后去掉 \(a,b\)，剩下的就是 \(c\) 的颜色（如果没有说明 \(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)=query(k,i-1)\)，说明 \(i\) 的颜色一定是 \([k,i-1]\) 中的其中一种；
- 若 \(query(k,i)=query(k,i-1)+1\)，说明 \(i\) 的颜色不是 \([k,i-1]\) 中的其中一种，它可能是 \([1,k-1]\) 的其中一种，或者是一种不同于 \([1,i-1]\) 的全新的颜色。
发现 \(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
*/