题意：给出一个 \(n\) 长序列 \(A\)，其拓展出来的 \(n^2\) 长度序列 \(B\) 是其复制 \(n\) 份的结果。现在给出一个 \(s\)，求一个最小的 \(l\)，满足对于任意的 \(x\)，\(s=x_1+x_2\cdots x_k\)，则 \(x\) 是 \(B_1,B_2,\cdots B_l\) 的一个子序列。\(s\le n\le 1.5\times 10^6,s\le 2\times 10^5\)，保证序列中 \([1,s]\) 都出现至少一次。
做法：
首先我们会一个 \(O(s^2)\) 的 dp，记 \(dp_{i}\) 代表已经满足了和为 \(i\) 的拆分，答案为多少，那么转移就是枚举再接一个 \(x\)，然后令 \(dp_{i+x}\) 对 \(\operatorname{nxt}(dp_i,x)\) 取 \(\max\)，这里 \(\operatorname{nxt}(x,y)\) 的意义为，从下标 \(x\) 开始，下一个 \(y\) 的位置在哪里，正确性显然。但是时间完全过不了。
我们考虑这是一个 1D-1D 的转移，考虑怎么优化一下。我们可以考虑分治一下，这样就只用考虑 \([l,mid]\) 对 \([mid+1,r]\) 的贡献。但是还是不好转移，没有什么性质。
我们先显然地发现 dp 数组是单调的。考虑什么时候比较有性质，那么得是同一个 \(y\) 这样我们 \(\operatorname{nxt}(x,y)\) 才有比较好的性质，对固定的一个 \(y\) 进行分析，那么我们发现，\(dp_i\) 如果对 \(dp_{i+x}\) 去尝试产生贡献，如果 \(\operatorname{nxt}(dp_{i},x)\) 和 \(\operatorname{nxt}(dp_{mid}, x)\) 相比更小，那我们肯定不用 \(i\) 对 \(i+x\) 更新，而因为 dp 数组单调，所以只有这两个值相等的时候才有用。所以我们可以直接找一个 \(\operatorname{pre}(dp_{mid}, x)\)，要求 \(dp_i\ge pre\) 才可以贡献，可以二分找到这个位置，然后直接对 \([mid+1,r]\) 中的元素区间取 \(\max\) 即可，用线段树维护一下就行，总复杂度 \(O(s\log^2s)\)。
需要注意一些等号上的细节。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1.5e6 + 5;
int n, s, a[maxn], f[maxn];
vector<int> v[maxn];
int get_nxt(int p, int k) {p += n;p %= n;int pos = upper_bound(v[k].begin(), v[k].end(), p) - v[k].begin();if(pos == v[k].size())return v[k][0] + n - p;return v[k][pos] - p;
}
int get_pre(int p, int k) {p += n;p %= n;int pos = upper_bound(v[k].begin(), v[k].end(), p) - v[k].begin();if(pos == 0)return n - v[k][v[k].size() - 1] + p;elsereturn p - v[k][pos - 1];
}
struct Segtree {int tr[(int)(8e5 + 5)];void build(int l, int r, int t) {tr[t] = -1;if(l == r) {tr[t] = -1;return ;}int mid = l + r >> 1;build(l, mid, t << 1), build(mid + 1, r, t << 1 | 1);// cout << l << " " << r << " " << tr[t] << " " << t << endl;}void update(int l, int r, int x, int y, int t, int val) {if(x <= l && r <= y) {tr[t] = max(tr[t], val);return ;}int mid = l + r >> 1;if(x <= mid)update(l, mid, x, y, t << 1, val);if(mid < y)update(mid + 1, r, x, y, t << 1 | 1, val);}int query(int l, int r, int pos, int t, int val) {// cout << t << " " << tr[t] << endl;if(l == r)return tr[t];int mid = l + r >> 1;if(pos <= mid)return max(query(l, mid, pos, t << 1, val), tr[t]);return max(query(mid + 1, r, pos, t << 1 | 1, val), tr[t]);}
} tree;
void solve(int l, int r) {if(l == r) {f[l] = tree.query(0, s, l, 1, 0);// cout << l << " " << f[l] << endl;return ;}int mid = l + r >> 1;solve(l, mid);for (int i = 1; i <= r - l; i++) {int nt = f[mid] + get_nxt(f[mid], i), pr = f[mid] - get_pre(f[mid], i);int lx = l - 1, rx = mid;while(lx + 1 < rx) {int mid = lx + rx >> 1;if(f[mid] >= pr)rx = mid;elselx = mid;}int ll = max(rx + i, mid + 1), rr = min(r, mid + i);// cout << l << " " << r << " " << i << " " << pr << " " << ll << " " << rr << " " << nt << endl;tree.update(0, s, ll, rr, 1, nt);}solve(mid + 1, r);
}
signed main() {cin >> n >> s;for (int i = 0; i < n; i++)cin >> a[i], v[a[i]].push_back(i);f[0] = -1;tree.build(0, s, 1);
// cout << tree.query(0, s, 0, 1, 0) << endl;solve(0, s);cout << f[s] + 1 << endl;return 0;
}
/*
5 5
5 1 3 4 2
*/