vp 的时候写了一个比较愚蠢的做法过了。
首先选择一个区间修改等价于删掉这个区间。那么考虑它给定的 \(m\) 个区间会有什么影响。假设给定的某个区间是 \([l,r]\),那么假设颜色 \(col\) 在这个区间出现 \(k\) 次,下标是 \(c_1,c_2,...,c_k\)。那么:
要是得到了所有 \(c\),我们就得到若干个条件形式是下面两者之间一个:
很容易贪心去做。具体地,从小到大枚举答案右端点 \(r\),维护一个堆,每次用 \(r\) 减去堆的最小值更新答案。考虑对于第 \(2\) 类条件,我们在左端点的时候加入,到右端点的时候删除左端点,再加入右端点。
但是得到 \(c\) 需要的复杂度还是不对。记在 \(x\) 后且颜色与 \(x\) 相同的第一个位置为 \(s(x)\)(找不到则为 \(n+1\))。我们考虑把左端点从小到大扫过去,对于位置 \(l\),找到 \(l\) 所在给定区间的最大的 \(r\)。如果 \(s(s(x))\le r\),那么 \(s(x)\) 是一定要覆盖的位置(即条件 \(1\))。再找到 \(r\) 前面第一个和 \(l\) 同颜色的位置 \(p\),那么需要满足必须覆盖 \(l,p\) 之一(即条件 \(2\))。容易发现这样就涵盖了所有条件。
这样就做完了。实现的时候有点细节。
下面是场上写的丑陋代码,并不建议阅读。有疑问可以私信我。
const int N=500005; int n,m,sum; int a[N],s[N],c[N]; int p[N],h[N]; map<int,int>tmp; int col; vector<int>b[N]; int g[N]; vector<int>f[N]; void add(int x,int y) { sum++; g[x]++; f[y].push_back(x); } multiset<int>se; void work() { cin >> n >> m; sum=0; tmp.clear(); col=0; for (int i=1;i<=n;i++) cin >> a[i]; for (int i=1;i<=n;i++) { g[i]=0; f[i].clear(); if (tmp[a[i]]==0) tmp[a[i]]=++col; a[i]=tmp[a[i]]; } for (int i=1;i<=n;i++) c[i]=0,p[i]=0; for (int i=n;i>=1;i--) { if (p[a[i]]==0) s[i]=n+1; else s[i]=p[a[i]]; p[a[i]]=i; } s[n+1]=n+1; for (int i=1;i<=n;i++) b[i].clear(); for (int i=1;i<=m;i++) { int l,r; cin >> l >> r; b[l].push_back(r); } for (int i=1;i<=n;i++) b[i].push_back(i); int mx=0; for (int i=1;i<=n;i++) { for (int j:b[i]) mx=max(mx,j); int u=s[i],v=s[u]; if (v<=mx) c[u]=1; } int l=n+1,r=0; for (int i=1;i<=n;i++) { if (c[i]==1) r=max(r,i),l=min(l,i); } for (int i=l;i<=r;i++) c[i]=1; // cout << l << " " << r << endl << endl; mx=0; for (int i=1;i<=n;i++) h[i]=0; for (int i=1;i<=n;i++) { for (int j:b[i]) { while (mx<j) { mx++; h[a[mx]]=mx; } } if (c[i]) continue; int u=h[a[i]]; if (i!=u) add(i,u); } if (sum==0) { if (r==0) cout << 0 << endl; else cout << r-l+1 << endl; return; } if (r!=0) sum+=r-l+1; int ans=n,uu=0; se.clear(); for (int i=1;i<=n;i++) { for (int j=1;j<=g[i];j++) se.insert(i),uu++; if (c[i]) se.insert(i),uu++; for (int j:f[i]) { se.erase(se.find(j)); se.insert(i); } if (uu==sum) ans=min(ans,i-*se.begin()+1); //cout << "11c " << *se.begin() << endl; } cout << ans << endl; }