[luoguP2463] [SDOI2008]Sandy的卡片（后缀数组 + st表）

传送门

很容易想到，题目中的相同是指差分数组相同。

那么可以把差分数组连起来，中间加上一个没有出现过的且字典序小的数

双指针移动，用st表维护height数组中的最小值。

当然用单调队列应该也可以且更快。

#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#define N 1010000using namespace std;int n, m, t, cnt, len, ans, mx, mn = 1e9;int pos[N], a[N / 1000], num[N / 1000], sa[N], height[N], Rank[N], b[N], x[N], y[N], d[N][22], s[N];inline int read()inline void build_sa()}inline void build_height()}inline void build_st()inline int query(int l, int r)inline void solve()if(cnt == t) ans = max(ans, query(i, j  1));if(!num[pos[sa[i]]] && pos[sa[i]]) cnt;}}int main()s[n++] = mx++;}for(i = 0; i < n; i++)if(pos[i]) s[i] = s[i]  mn + mx, m = max(m, s[i]);m++;build_sa();build_height();build_st();solve();printf("%d\n", ans + 1);return 0;}

上一篇：javascript加超链接

下一篇：dede5.7-修改自定义表单