题解 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$ 的颜色块，如果 - $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 实现时可以用并查集。 ```cpp #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 */ ```