给定两个整数数组 \(a[0..n-1],b[0..n-1]\)，求出它们的循环卷积 \(c[0..n-1]\)。其中：
\[\large c_i=\max\limits_{0\le j<n}\{a_j+b_{(i-j+n)\mod n}\} \]对于 \(100\%\) 的数据，\(n\le 2\times 10^5,0\le a_i,b_i\le 5000,\sum a_i\le 5000,\sum b_i\le 5000\)。
原题有个 \(\mathcal{O(n^2)}\) 暴力，所以人均 60 分。
正解隐藏在数据范围中，\(\sum a_i\le 5000,\sum b_i\le 5000\) 有什么实际意义？
答：数组 \(a,b\) 中，各自最多有 \(5000\) 个数不为 \(0\)。运用反证法，其实压根不用，正确性是显然的。
因此考虑刷表法，有至少一个数为 \(0\) 时，\(c_i\) 最大值为 \(\max\{a_i\}+\max\{b_j\}\)，将其赋为 \(c\) 数组初值，再 \(\mathcal{O(n^2)}\) 地用不为 \(0\) 的那至多 \(5000\) 个数更新 \(c\) 数组。虽然也是 \(n^2\)，但数据范围缩减到了 \(5000\)，完全能过。
具体做法是：扫 \(a,b\) 两数组，把不为 \(0\) 的分别拿出来，扔进数组 \(a',b'\)，同时保留其编号（可以用 pair 类型）。不难发现 \(a_i+b_j\) 可以更新 \(c_{(i+j)\mod n}\)，做完了。这件事情很像离散化，所以就以此为标题了（大雾
下面是 AC 代码：
int main(){
int n,cnt1=0,cnt2=0;
scanf("%d",&n);
for(int i(0);i<n;++i){
int x; scanf("%d",&x);
if(x) a[++cnt1]=std::make_pair(x,i);//输入的时候顺带就挑出来了，下同
}
for(int i(0);i<n;++i){
int x; scanf("%d",&x);
if(x) b[++cnt2]=std::make_pair(x,i);
}
std::sort(a+1,a+cnt1+1);
std::sort(b+1,b+cnt2+1);
c[0]=std::max(a[cnt1].first,b[cnt2].first);//排序只是为了找max，并无必要，可以O(n)扫一遍嘛
for(int i(1);i<n;++i) c[i]=c[0];//赋初值，如果没赋能水80分，但是显然一卡就没了
for(int i(1);i<=cnt1;++i)
for(int j(1);j<=cnt2;++j)
c[(a[i].second+b[j].second)%n]=std::max(c[(a[i].second+b[j].second)%n],a[i].first+b[j].first);
for(int i(0);i<n;++i){
printf("%d",c[i]);
putchar(i==n-1?'\n':' ');//最后不加空格，末尾有换行是代码好习惯，否则fc可能出错，搞崩心态
}
return 0;
}