前后缀排序sort
复制数组然后 sa 即可。
像忘了哪个题目一样，先考虑删除 \(s_i,s_k\) 哪个会更小，不妨令 \(i<j\)。考虑 \(s_j\) 是 \(i\) 后面第一个不同的字符，发现删除点在 \([i+1,j-1],j,[j+1,n]\) 的比删除 \(i\) 的小还是大是很容易确定的，考虑从小到大连出一个偏序的 dag 搜出来就是答案。\([i+1,j-1]\) 就 \((i,i+1)\) 顺次往后，\(j\) 就 \((i,j)/(j,i)\) 即可，对于 \([j+1,n]\) 不妨求出后缀最小/大的位置 \(f_i/g_i\)，这个只需要比较 \(f_{i+1}/g_{i+1}\) 和 \(i\) 的大小即可，之后如果那段比 \(i\) 小就是那段的最大值比 \(i\) 小，反之就是那段的最小值比 \(i\) 大，然后这些加起来充分性显然。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_backusing namespace std;const int N=500005;int id, T, n, in[N], f[N], g[N];
char str[N];
vector<int> to[N];void eadd(int u,int v) { to[u].pb(v), ++in[v]; }void mian() {cin >> n >> (str+1);int lst, j;dn(i,n,1) {if(str[i]!=str[i+1]) lst=i;j=lst+1;if(i+1<j) eadd(i,i+1);if(j<=n) {if(str[j]<str[i]) eadd(i,j);else eadd(j,i);}if(j+1<=n) {if(str[j]<str[i]) {eadd(i,g[j+1]);}else { eadd(f[j+1],i);}}if(i==n) { f[i]=g[i]=i; continue; }if(f[i+1]<j) { f[i]=f[i+1]; }else if(f[i+1]==j) { f[i]=str[j]>str[i]?i:j; }else { f[i]=str[j]>str[i]?i:f[i+1]; }if(g[i+1]<j) { g[i]=i; }else if(g[i+1]==j) { g[i]=str[j]<str[i]?i:j; }else { g[i]=str[j]<str[i]?i:g[i+1]; }}queue<int> q;up(i,1,n) if(!in[i]) q.push(i);while(q.size()) {int x=q.front(); q.pop();cout << x << ' ';for(int y:to[x]) if(!--in[y]) q.push(y);} cout << '\n';up(i,1,n) to[i].clear();
}signed main() {freopen("sort.in","r",stdin);freopen("sort.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> id >> T;while(T--) mian();return 0;
}
回家的路home
首先集合 \(i\) 是还没回家的人的的编号排序，那就是没有回家的人的位置集合惹，那么操作的意思就是没回家的人顺着往下一个走。考虑一下一个人走的过程（顺时针断环成链），不会跨越着跳动，哦那是一个有多少人中途停下来了你就少走几步嘛！所以考虑 \(i,nxt_i\) （\(nxt\) 是断环成链后的 \(a\)）有多少个 \((j,nxt_j)\) 满足 \(i<j\leq nxt_j<nxt_i\) 即可，二维偏序来的。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=200005;int id, T, n, a[N], sp[N], nxt[N], Ans[N], tr[N];inline void add(int x,int v) {for( ; x<=2*n; x+=x&-x) tr[x]+=v;
}inline int ask(int x) {int res=0;for( ; x; x-=x&-x) res+=tr[x];return res;
}void mian() {cin >> n;up(i,1,n) cin >> a[i];up(i,1,n) a[i+n]=a[i];up(i,1,n) nxt[i]=(a[i]>=i?a[i]:(a[i]+n));up(i,1,n) nxt[i+n]=(a[i]>=i?(a[i]+n):(2*n+1));up(i,1,2*n) sp[i]=i;sort(sp+1,sp+1+2*n,[](int i,int j){return nxt[i]<nxt[j];});up(u,1,2*n) {int i=sp[u];if(i<=n) {int ans=nxt[i]-i;ans-=ask(nxt[i])-ask(i);Ans[a[i]]=ans;}add(i,1);}up(i,1,n) cout << Ans[i] << ' '; cout << '\n';up(i,0,2*n) tr[i]=0;
}signed main() {
// freopen("data.txt","r",stdin);freopen("home.in","r",stdin);freopen("home.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> id >> T;while(T--) mian();return 0;
}
栈模拟stack
暴力肯定是行不通的虽然其实历史上可，但是又好像尝试描述出的充要条件也都不太好算，不妨考虑一定程度上一起处理。考虑第一步 \(i\to a_i\) 形成了一颗基环树，注意到环上的从哪里进去就会回到哪里，整个环都没有贡献可以全都消除，不断消除最后会形成森林，每个点的答案就是其对应的根。这个消环让我完全自主写我肯定更新的暴力加进 set 之类的东西然后每一次取一个出来搜，但是其实可以直接就去深搜，正确性也是显然的但感觉不对我的脑子，应该以后每天欣赏一下，顺直算法真虾头。
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=100005;int id, n, ans[N], in[N], stk[N], top;
stack<int> a[N]; int solve(int x) {if(ans[x]) return ans[x];if(!a[x].size()) return ans[x]=x;if(in[x]) {while(stk[top]!=x) {a[stk[top]].pop();in[stk[top--]]=0;}a[stk[top]].pop(), in[stk[top--]]=0;return solve(x);}in[x]=1, stk[++top]=x;return solve(a[x].top());
}signed main() {
// freopen("data.txt","r",stdin);freopen("stack.in","r",stdin);freopen("stack.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> id >> n;up(i,1,n) {int k, tmp; cin >> k;while(k--) cin >> tmp, a[i].push(tmp);}up(i,1,n) {top=0;int tmp=solve(i);while(top) ans[stk[top--]]=tmp;}up(i,1,n) cout << ans[i] << ' ';return 0;
}
括号游戏3 bracket
看到这个题目直觉告诉我删除的应该是一段一段匹配的括号，更理性的说去考虑前缀和序列 \(s_{1,\dots,m}\)，想要字典序小就是依次想要 \(s_i\) 尽可能大，你去删除 \(str_i,str_j\) 就是减小了 \(s_{i+1,\dots,j-1}\)，注意原本到 \(s_{i+1}-1\leq s_i\) 所以因为祂们违背了家族信念所以都要被消失删除，而这个条件在于存在括号匹配。
那么好像可以 dp 了，设 \(f_i\) 表示考虑了前缀 \(i\) 时的最小 \(s\) 是多少，可以从 \(f_{i-1}+str_i\) 转移也可以转移 \([j,i]\) 匹配的 \(j\)，注意到 \(s_{j-1}=s_i\) 可以相互转移所以 \(f_j\) 相等随便挑一个出来转移就行了。现在问题在于比较 \(f_{i-1}+str_i\) 和 \(f_j\) 的大小，可以用可持久化线段树但是过于麻烦惹，转移是一个 trie 的结构，我们尝试使用倍增表找 lcp 其实已经可以了，先二分再跳父亲这样。因为倍增我们还是更希望做后缀那么不妨倒序 dp 这样子问题转化成找树上后缀最大重叠长度，写一个哈希就可以了。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=600005, M=23;
const ull B=23333;int n, m, T, s[N], top, stk[N], f[N], fa[N][M], dep[N], val[N];
char str[N];
ull pw[N], hsh[N][M];void insert(int &i,int j,char c) {i=++m, dep[i]=dep[j]+1;fa[i][0]=j, hsh[i][0]=val[i]=(c=='('?1:2);up(u,1,T) {fa[i][u]=fa[fa[i][u-1]][u-1];hsh[i][u]=hsh[i][u-1]+hsh[fa[i][u-1]][u-1]*pw[1<<u-1];}
}bool fc(int i,int j) {dn(u,T,0) if(fa[i][u]&&fa[j][u]&&hsh[i][u]==hsh[j][u]) i=fa[i][u], j=fa[j][u];return val[i]==val[j]?dep[i]<dep[j]:val[i]<val[j];
}signed main() {freopen("bracket.in","r",stdin);freopen("bracket.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> (str+1), n=strlen(str+1), T=log2(n), pw[0]=1;up(i,1,n) pw[i]=B*pw[i-1]; s[stk[top=1]=n+1]=0;dn(i,n,1) {s[i]=s[i+1]+(str[i]=='('?-1:1);while(top&&s[stk[top]]>s[i]) --top;insert(f[i],f[i+1],str[i]);if(s[stk[top]]==s[i]) {int j=stk[top];if(fc(f[j],f[i])) f[i]=f[j];}stk[++top]=i;}for(int i=f[1]; i; i=fa[i][0]) cout << (val[i]==1?'(':')');return 0;
}