## 【Codeforces 819B】Mister B and PR Shifts

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;

int n, p[N], chg[N], delta[2];

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;
}

int main() {
LL cur = 0, ans, pos = 0;
for (int i = 1; i <= n; i++) {
cur += abs(p[i] - i);
delta[p[i] > i]++;
if (p[i] > i) {
++chg[p[i] - i];
} else {
++chg[n - i + p[i]];
}
--chg[n - i + 1];
}
ans = cur;
for (int i = 1; i < n; i++) {
cur += delta[0] - delta[1];
cur += abs(p[n - i + 1] - 1) - abs(p[n - i + 1] - n - 1);
if (cur < ans) {
ans = cur;
pos = i;
}
delta[1] -= chg[i];
delta[0] += chg[i];
}
cout<<ans<<' '<<pos<<endl;
return 0;
}


## 【BZOJ 4567】[Scoi2016] 背单词

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define AC AC_Automata
#define LL long long
using namespace std;

LL vout = 0;
char pat[510000+9];

namespace AC_Automata{
const int N = 510000+9;
const int SIGMA_SIZE = 26;
struct Node{int ch[SIGMA_SIZE],fail,last,vis;}p[N];
int cnt,que[N],itr1,itr2;
vector<int> G[N];

int TOT,tot,sz[N];

inline void insert(char *s){
int len = strlen(s), w=0;
for (int i=0;i<len;i++){
int c = s[i] - 'a';
if (!p[w].ch) w = p[w].ch = ++cnt;
else w = p[w].ch;
} p[w].vis++;
}

inline void GetFail(){
itr1 = 0; itr2 = 1;
for (int i=0;i<SIGMA_SIZE;i++)
if (p[0].ch[i]) que[++itr1] = p[0].ch[i];

while (itr2 <= itr1){
int w = que[itr2++];
for (int i=0;i<SIGMA_SIZE;i++){
if (p[w].ch[i]) {
int nw = p[w].fail;
while (nw && !p[nw].ch[i]) nw = p[nw].fail;
p[p[w].ch[i]].fail = p[nw].ch[i];
p[p[w].ch[i]].last = p[p[nw].ch[i]].vis ? p[nw].ch[i] : p[p[nw].ch[i]].last;
que[++itr1] = p[w].ch[i];
}
}
}
}

void DFS(int w){
sz[w] = 1;
for (int i=head[w];i;i=nxt[i]) DFS(to[i]), sz[w] += sz[to[i]], G[w].push_back(sz[to[i]]);
int len = G[w].size();
sort(G[w].begin(), G[w].end());
for (int i=0,sta=0;i<len;i++) vout += (LL)sta + 1LL, sta += (LL)G[w][i];
}
};

int main(){
int n; scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%s",pat), AC::insert(pat);
AC::GetFail(); AC::DFS(0);
printf("%lld",vout);
return 0;
}