再见OI,岁月静好。
Tag: NOI
【BZOJ 3672】[NOI2014] 购票
解题报告
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809
解题报告
一句话题解:树上CDQ分治
先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$
我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = N << 1; const LL INF = 6e18; int n, head[N], nxt[M], to[M], fa[N]; LL q[N], p[N], len[N], dep[N], f[N]; struct Point{ LL x, y, id, range; inline Point() { } inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) { } inline bool operator < (const Point &P) const { return x > P.x || (x == P.x && y > P.y); } inline Point operator - (const Point &P) { return Point(x - P.x, y - P.y, 0, 0); } inline double operator * (const Point &P) { return (double)x * P.y - (double)y * P.x; } inline double slope(const Point &P) { return (double)(y - P.y) / (x - P.x); } static bool update(const Point &P1, const Point &P2) { return P1.range > P2.range; } }; inline LL read() { char c = getchar(); LL ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } class DivideAndConquer{ int sz[N], vis[N]; public: inline void solve(int w, int universe) { int top = w; vis[w = FindRoot(w, universe)] = 1; if (fa[w] && !vis[fa[w]]) { solve(top, universe - sz[w]); } vector<Point> cvx; for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) { cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw])); } vector<Point> que; que.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { DFS(to[i], w, que); } } sort(que.begin(), que.end(), Point::update); sort(cvx.begin(), cvx.end()); for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) { for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) { for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot); cvx[tot++] = cvx[j]; } int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id; while (l <= r) { mid = l + r >> 1; if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) { ret = mid; r = mid - 1; } else { l = mid + 1; } } if (ret >= 0) { f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]); } } for (int i = 0, j; i < (int)que.size(); i++) { if (j = que[i].id, que[i].range <= dep[w]) { f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]); } } que.clear(); cvx.clear(); for (int i = head[w]; i; i = nxt[i]) { if (dep[to[i]] > dep[w] && !vis[to[i]]) { solve(to[i], sz[to[i]]); } } } private: inline int FindRoot(int w, int universe) { int ret = 0, ans; FindRoot(w, w, universe, ret, ans); return ret; } inline void FindRoot(int w, int f, int universe, int &ret, int &ans) { int mx = 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { FindRoot(to[i], w, universe, ret, ans); sz[w] += sz[to[i]]; mx = max(mx, sz[to[i]]); } } mx = max(mx, universe - sz[w]); if (!ret || mx < ans) { ans = mx; ret = w; } } inline void DFS(int w, int f, vector<Point> &ret) { ret.push_back(Point(dep[w], 0, w, dep[w] - len[w])); for (int i = head[w]; i; i = nxt[i]) { if (!vis[to[i]] && to[i] != f) { DFS(to[i], w, ret); } } } }DAC; int main() { n = read(); read(); for (int i = 2; i <= n; i++) { fa[i] = read(); LL c = read(); AddEdge(fa[i], i); p[i] = read(); q[i] = read(); len[i] = read(); dep[i] = dep[fa[i]] + c; } fill(f, f + N, INF); f[1] = 0; dep[0] = -1; DAC.solve(1, n); for (int i = 2; i <= n; i++) { printf("%lld\n", f[i]); } return 0; }
【BZOJ 4198】[NOI2015] 荷马史诗
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4198
解题报告
k叉哈夫曼树
注意最大化儿子不满的那个结点的深度
Code
#include<bits/stdc++.h> #define LL long long using namespace std; struct Data{ LL apt, mx; inline Data() { } inline Data(LL a, LL c):apt(a), mx(c) { } inline Data operator + (const Data &d) { return Data(apt + d.apt, max(mx, d.mx + 1)); } inline bool operator < (const Data &d) const { return apt > d.apt || (apt == d.apt && mx > d.mx); } }; priority_queue<Data> que; inline LL read() { char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main() { int n = read(), k = read(); for (int i = 1; i <= n; i++) { que.push(Data(read(), 0)); } LL ans = 0; for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) { Data np(0, 0); for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) { np = np + que.top(); que.pop(); } ans += np.apt; que.push(np); } printf("%lld\n%lld\n", ans, que.top().mx); return 0; }
【BZOJ 4195】[NOI2015] 程序自动分析
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4195
解题报告
用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = 300009; int n, fa[N], cet[M], val[N], dif[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int find(int x) { return fa[x] == x? x: fa[x] = find(fa[x]); } int main() { freopen("prog.in", "r", stdin); freopen("prog.out", "w", stdout); for (int T = read(); T; T--) { n = read(); int tot = 0, cnt = 0, tt = 0; for (int i = 1; i <= n; i++) { cet[++tot] = val[++cnt] = read(); cet[++tot] = val[++cnt] = read(); cet[++tot] = read(); } sort(val + 1, val + 1 + cnt); cnt = unique(val + 1, val + 1 + cnt) - val - 1; for (int i = 1; i <= cnt; i++) { fa[i] = i; } for (int i = 1; i <= n; i++) { int t = cet[tot--]; int u = cet[tot--], v = cet[tot--]; u = lower_bound(val + 1, val + 1 + cnt, u) - val; v = lower_bound(val + 1, val + 1 + cnt, v) - val; if (t == 1) { fa[find(u)] = find(v); } else { dif[++tt] = u; dif[++tt] = v; } } bool ok = 1; for (int i = 1; i <= tt; i += 2) { int u = dif[i], v = dif[i + 1]; if (find(u) == find(v)) { ok = 0; break; } } puts(ok? "YES": "NO"); } return 0; }
【BZOJ 4196】[NOI2015] 软件包管理器
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4196
解题报告
考虑树链剖分
线段树部分只需要支持区间赋值,查询区间中1的个数
总的时间复杂度:$O(n \log ^ 2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 200009; int n, m, head[N], nxt[N], to[N], beg[N], ot[N]; int fa[N], top[N], hvy[N], sz[N], dep[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void DFS1(int w, int f) { fa[w] = f; dep[w] = dep[f] + 1; sz[w] = 1; for (int i = head[w]; i; i = nxt[i]) { DFS1(to[i], w); sz[w] += sz[to[i]]; if (sz[to[i]] > sz[hvy[w]]) { hvy[w] = to[i]; } } } inline void DFS2(int w, int t) { static int dfc = 0; beg[w] = ++dfc; top[w] = t; if (hvy[w]) { DFS2(hvy[w], t); for (int i = head[w]; i; i = nxt[i]) { if (to[i] != hvy[w]) { DFS2(to[i], to[i]); } } } ot[w] = dfc; } class Segment_Tree{ int cnt, root, ch[M][2], sum[M], tag[M]; public: inline void init() { init(root, 1, n); } inline int install(int w) { int ret = 0, tmp; while (true) { int l = beg[top[w]], r = beg[w], len = r - l + 1; tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1); ret += tmp; if (fa[top[w]] != w && tmp) { w = fa[top[w]]; } else { break; } } return ret; } inline int uninstall(int w) { return modify(root, 1, n, beg[w], ot[w], -1); } private: inline void init(int &w, int l, int r) { w = ++cnt; if (l < r) { int mid = l + r + 1 >> 1; init(ch[w][0], l, mid - 1); init(ch[w][1], mid, r); } } inline void PushDown(int w, int l, int mid, int r) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; if (tag[w] == 1) { sum[ls] = mid - l; sum[rs] = r - mid + 1; } else { sum[ls] = sum[rs] = 0; } tag[ls] = tag[rs] = tag[w]; tag[w] = 0; } } inline int modify(int w, int l, int r, int L, int R, int t) { if (L <= l && r <= R) { int ret = sum[w]; sum[w] = t == -1? 0: r - l + 1; tag[w] = t; return ret; } else { int mid = l + r + 1 >> 1, ret = 0; PushDown(w, l, mid, r); if (L < mid) { ret += modify(ch[w][0], l, mid - 1, L, R, t); } if (mid <= R) { ret += modify(ch[w][1], mid, r, L, R, t); } sum[w] = sum[ch[w][1]] + sum[ch[w][0]]; return ret; } } }SGT; int main() { freopen("manager.in", "r", stdin); freopen("manager.out", "w", stdout); n = read(); for (int i = 2; i <= n; i++) { AddEdge(read() + 1, i); } DFS1(1, 1); DFS2(1, 1); SGT.init(); m = read(); char cmd[20]; for (int i = 1; i <= m; i++) { scanf("%s", cmd + 1); if (cmd[1] == 'i') { printf("%d\n", SGT.install(read() + 1)); } else { printf("%d\n", SGT.uninstall(read() + 1)); } } return 0; }
【BZOJ 4197】[NOI2015] 寿司晚宴
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4197
解题报告
考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 509; const int M = 6561; int pri[] = {2, 3, 5, 7, 11, 13, 17, 19}; int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3]; LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M]; vector<int> sta[N]; inline void relax(LL &a, LL b) { a = (a + b) % MOD; } inline int num(int x, int t) { for (; t; x /= 3, t--); return x % 3; } inline int SET(int w, int t, int v) { static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187}; int ret = 0; for (int i = 0; i < 8; i++, w /= 3, t >>= 1) { if (t & 1) { ret += buf[i] * v; } else { ret += buf[i] * (w % 3); } } return ret; } int main() { freopen("dinner.in", "r", stdin); freopen("dinner.out", "w", stdout); cin>>n>>MOD; for (int i = 0; i < M; i++) { for (int j = 0; j < 8; j++) { int t = num(i, j); if (t == 1) { sta1[i] |= 1 << j; } else if (t == 2) { sta2[i] |= 1 << j; } } } for (int i = 0; i < M; i++) { for (int j = 0; j < (1 << 8); j++) { for (int k = 1; k <= 2; k++) { tt[i][j][k] = SET(i, j, k); } } } for (int i = 2; i <= n; i++) { gpri[i] = i; for (int j = 0; j < 8; j++) { if (gpri[i] % pri[j] == 0) { spri[i] |= (1 << j); while (gpri[i] % pri[j] == 0) { gpri[i] /= pri[j]; } } } } f = arr1, g = arr2, h = arr3; g[0] = f[0] = 1; for (int i = 2; i <= n; i++) { if (gpri[i] == 1) { for (int j = M - 1; ~j; j--) { if (g[j]) { int sta = 0; for (int k = 0; k < 8; k++) { if (spri[i] >> k & 1) { sta |= num(j, k); } } if (sta == 0) { relax(f[tt[j][spri[i]][1]], g[j]); relax(f[tt[j][spri[i]][2]], g[j]); } else if (sta < 3) { relax(f[tt[j][spri[i]][sta]], g[j]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } else { sta[gpri[i]].push_back(spri[i]); } } for (int i = 2; i <= n; i++) { if (!sta[i].empty()) { memcpy(h, g, sizeof(arr1)); memcpy(ori, g, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (g[k]) { int s1 = vv & sta1[k]; if (!s1) { relax(f[tt[k][vv][2]], g[k]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } memcpy(f, h, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (h[k]) { int s2 = vv & sta2[k]; if (!s2) { relax(f[tt[k][vv][1]], h[k]); } } } memcpy(h, f, sizeof(arr1)); swap(f, h); } for (int k = 0; k < M; k++) { f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD; } } } LL ans = 0; for (int i = 0; i < M; i++) { relax(ans, f[i]); } printf("%lld\n", ans); return 0; }
【BZOJ 4650】[NOI2016] 优秀的拆分
相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4650
神犇题解:https://blog.sengxian.com/solutions/bzoj-4650
解题报告
主要是统计以每个点为开头/结尾的能划分成两个相等子串的串有多少个
这个是SA的经典应用
当然问能划分成x个相同子串的问题,SA也是一样的做法
比如:https://www.codechef.com/problems/TANDEM
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 60009; const int SGZ = 26; const int M = 15; char pat[N]; int n,c1[N],c2[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } class Suffix_Array{ char s[N]; int *rak,*que,len,dif; int arr1[N],arr2[N],bot[N],sa[N],height[N]; class Sparse_Table{ int mn[N][M],len; public: inline void init(int LEN, int *height) { len = LEN; memset(mn,0,sizeof(mn)); for (int i=1;i<=len;i++) mn[i][0] = height[i]; for (int j=1,w=1;j<M;j++,w<<=1) { for (int i=1,l=len-w;i<=l;i++) { mn[i][j] = min(mn[i][j-1], mn[i+w][j-1]); } } } inline int query(int l, int r) { if (l > r) swap(l, r); ++l; int h = r - l + 1 >> 1, t = 0, L = 1; while (L <= h) L<<=1, t++; return min(mn[l][t],mn[r-L+1][t]); } }st; public: inline void init(char *S, int L) { memset(s,0,sizeof(s)); memset(arr1,0,sizeof(arr1)); memset(arr2,0,sizeof(arr2)); for (int i=1;i<=L;i++) s[i] = S[i]; len = L; build(); } inline int query(int l, int r) { if (l < 0 || l > len || r < 0 || r > len) return 0; else return st.query(rak[l], rak[r]); } inline void out() { cout<<"----------"<<endl; for (int i=1;i<=len;i++) printf("%d ",sa[i]); cout<<endl; for (int i=1;i<=len;i++) printf("%d ",height[i]); cout<<endl; cout<<"----------"<<endl; } private: inline void build() { rak = arr1; que = arr2; for (int i=1;i<=SGZ;i++) bot[i] = 0; for (int i=1;i<=len;i++) bot[s[i]-'a'+1]++; for (int i=2;i<=SGZ;i++) bot[i] += bot[i-1]; for (int i=1;i<=len;i++) sa[bot[s[i]-'a'+1]--] = i; rak[sa[1]] = dif = 1; for (int i=2;i<=len;i++) rak[sa[i]] = (dif += (s[sa[i]]!=s[sa[i-1]])); for (int l=1,tot;tot=0,l<=len;l<<=1) { for (int i=len-l+1;i<=len;i++) que[++tot] = i; for (int i=1;i<=len;i++) if (sa[i] > l) que[++tot] = sa[i] - l; for (int i=1;i<=dif;i++) bot[i] = 0; for (int i=1;i<=len;i++) bot[rak[i]]++; for (int i=2;i<=dif;i++) bot[i] += bot[i-1]; for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i]; swap(que, rak); rak[sa[1]] = dif = 1; for (int i=2;i<=len;i++) if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]]=dif; else rak[sa[i]] = ++dif; if (dif >= len) break; } for (int i=1;i<=len;i++) { int t = max(0, height[rak[i-1]] - 1); int p1 = i + t, p2 = sa[rak[i]-1] + t; for (;s[p1]==s[p2];p1++,p2++) ++t; height[rak[i]] = t; } st.init(len, height); } }dir,rev; int main() { for (LL T=read(),vout;vout=0,T;T--) { memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); scanf("%s",pat+1); n = strlen(pat+1); dir.init(pat, n); for (int i=1,j=n;i<j;i++,j--) swap(pat[i], pat[j]); rev.init(pat, n); for (int l=1,suf,pre,L,R;l<=n;l++) { for (int i=1;i<=n;i+=l) { suf = dir.query(i, i+l); pre = rev.query(n-i+2, n-i-l+2) + 1; L = max(i, i + l - pre); R = min(i + l - 1, i + suf - 1); if (L <= R) { c1[L+l]++; c1[R+l+1]--; c2[L-l]++; c2[R-l+1]--; } } } for (int i=1,t1=c1[0],t2=c2[0];i<=n;i++) { t1 += c1[i]; t2 += c2[i]; vout += (LL)t1 * t2; } printf("%lld\n",vout); } return 0; }
【BZOJ 4199】[NOI2015] 品酒大会
相关链接
题目传送门Ⅰ:http://uoj.ac/problem/131
题目传送门Ⅱ:http://www.lydsy.com/JudgeOnline/problem.php?id=4199
神犇题解:https://blog.sengxian.com/solutions/bzoj-4199
解题报告
其实sengxian都写了题解了,我还有什么写的意义 _(:з」∠)_
不过还是简单说两句吧!
我们考虑把SA建出来,height数组搞出来
然后把height数组排个序
从小到大依次合并上去就可以辣!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 600009; const LL INF = 1e18; int n,val[N],sz[N],mx[N],mn[N]; int height[N],bot[N],sa[N],arr[N]; int *rak,*que,arr1[N],arr2[N],fa[N]; char pat[N]; LL ans1,ans2; stack<pair<LL,LL> > ans; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline bool cmp(const int &a, const int &b) { return height[a] > height[b]; } class Suffix_Array{ public: inline void build() { rak = arr1; que = arr2; for (int i=1;i<=n;i++) bot[pat[i]-'a'+1]++; for (int i=1;i<=26;i++) bot[i] += bot[i-1]; for (int i=1;i<=n;i++) sa[bot[pat[i]-'a'+1]--] = i; for (int ty=0,i=1;i<=n;i++) rak[sa[i]] = pat[sa[i]]==pat[sa[i-1]]? ty: ++ty; for (int l=1,tot=0,ty;l<n;l<<=1,tot=0) { memset(bot,0,sizeof(bot)); for (int i=n-l+1;i<=n;i++) que[++tot] = i; for (int i=1;i<=n;i++) if (sa[i]>l) que[++tot] = sa[i] - l; for (int i=1;i<=n;i++) bot[rak[i]]++; for (int i=1;i<=n;i++) bot[i] += bot[i-1]; for (int i=n;i;i--) sa[bot[rak[que[i]]]--] = que[i]; swap(rak, que); rak[sa[1]] = ty = 1; bot[1] = 1; for (int i=2;i<=n;i++) if (que[sa[i]] == que[sa[i-1]] && que[sa[i]+l] == que[sa[i-1]+l]) rak[sa[i]] = ty; else bot[rak[sa[i]] = ++ty] = 0; if (ty >= n) break; } Get_Height(); } inline void solve() { for (int i=1;i<=n;i++) { arr[i] = fa[i] = i; sz[i] = 1; mn[i] = mx[i] = val[sa[i]]; } sort(arr+1, arr+1+n, cmp); for (int i=n-1,j=1;~i;i--) { for (;height[arr[j]]>=i;++j) update(arr[j]); ans.push(make_pair(ans1, ans2)); } for (;!ans.empty();ans.pop()) printf("%lld %lld\n",ans.top().first, ans.top().second); } private: inline void Get_Height() { for (int i=1,len,p1,p2;i<=n;i++) { len = max(height[rak[i-1]] - 1, 0); p1 = i + len; p2 = sa[rak[i]-1] + len; while (pat[p1] == pat[p2]) ++p1, ++p2, ++len; height[rak[i]] = len; } height[1] = -1; } int find(int x) {return fa[x]==x?x:find(fa[x]);} inline void update(int i) { static int E = 1; if (E) E = 0, ans2 = -INF; int f1 = find(i), f2 = find(i-1); ans1 += (LL)sz[f1] * sz[f2]; ans2 = max(ans2, (LL)mx[f2] * mx[f1]); ans2 = max(ans2, (LL)mn[f2] * mn[f1]); sz[f1] += sz[f2]; fa[f2] = f1; mx[f1] = max(mx[f1], mx[f2]); mn[f1] = min(mn[f1], mn[f2]); } }SA; int main() { n = read(); scanf("%s",pat+1); for (int i=1;i<=n;i++) val[i] = read(); SA.build(); SA.solve(); return 0; }
—————————— UPD 2017.7.10 ——————————
显然这货用SAM也是可做的