原题链接
ad-hoc。
首先规定第 \(i\) 种牌第一次出现的位置为 \(l_i\) ，第二次出现的位置为 \(r_i\) 。
-
\(n+1\) 做法 把所有 \(l\) 放到同一个栈里，所有 \(r\) 平摊到 \(n\) 个栈里，每次从 \(n\) 个栈中找 \(l\) 的栈顶，没有技术含量。
-
期望 \(2\sqrt n+1\) 做法 这是对方法 \(1\) 的优化。注意到如果两种牌 \(x,y\) 满足 \(l_x ，那么他们的 \(r\) 可以放到一起。根据 \(Dilworth\) 定理，这样的 \(r\) 的组数等于整个 \(r\) 序列的非严格下降子序列长度，随机序列的长度期望为 \(2\sqrt n\) ，于是总数为 \(2\sqrt n+1\) 。
-
严格 \(2\sqrt n\) 做法 一个 \(r\) 栈用完就闲置了，我们能不能让他们循环起来？考虑对 \(r\) 排序后分块，块长为 \(B\) ，一个块一个块处理，每个块使用方案 \(1\) ，下一个块继续用上一个块清空的 \(r\) 栈，则 \(r\) 栈总共只需要开 \(B\) 个，而总共 \(\frac{n}{B}\) 个块，总共 \(B+\frac{n}{B}\) 个块，平衡到 \(2\sqrt n\) 。
-
\(3n^{\frac{1}{3}}\) 做法 直接注意到方法 \(2\) 是对方法 \(1\) 的优化，而方法 \(3\) 需要直接用到方法 \(1\) ，那直接用方法 \(2\) 平替方法 \(3\) 中的方法 \(1\) 即可，总次数\(\frac{n}{B}+2\sqrt B\) ，\(B=n^{\frac{2}{3}}\) 时原式最小取 \(3n^{\frac{1}{3}}\) 。
由此我们总结一下这个题对于ad-hoc题的启示：
1.不管复杂度如何，先尝试多构造一些方法作为备用或者启发。
2.尝试寻找不同方法直接的结合，分清每种方法的核心思路，寻找联系或者替换。
3.好好分析复杂度，均值不等式，随机化的期望啥的。
4.必要时做好常数优化
代码：
#include
#include
#include
#include
using namespace std;
const int N=5e5+5;
int n,c[2*N];
struct Node{ int l,r; }p[N];
int main(){ios::sync_with_stdio(0); cin.tie(0);cin>>n;for(int i=1;i<=2*n;i++){int v; cin>>v;if(!p[v].l) p[v].l=i;else p[v].r=i;}sort(p+1,p+n+1,[](const Node& x,const Node& y){ return x.r>y.r; });int B=pow(n,2.0/3.0),blknum=(n+B-1)/B;for(int i=1;i<=blknum;i++){int st=(i-1)*B+1,ed=min(n,i*B);for(int j=st;j<=ed;j++) c[p[j].l]=i;sort(p+st,p+ed+1,[](const Node& x,const Node& y){ return x.l > s;int cur=0;for(int j=st;j<=ed;j++){int r=p[j].r;auto it=s.lower_bound(make_pair(r,0));if(it==s.begin()){++cur;c[r]=blknum+cur;}else{--it;c[r]=it->second;s.erase(it);}s.insert(make_pair(r,c[r]));}}for(int i=1;i<=2*n;i++) cout<