OI笔记 | 2023.7-11 做题记录（三）
无不恒
有一个 $n$ 个数的排列 $a$。
$q$ 次操作，每次操作交换 $a$ 中的两个数。
每次操作后，求一个最小的 $k$，使得在把 $a$ 的前 $k$ 个数放到排列末尾之后，$a$ 的逆序对数最大。
$q, n\leq 10^6$
题解
设当前序列原来的逆序对数为 $x$。我们把序列的开头 $a_1$ 放到序列的最后时，由于有 $a_1-1$ 个数比它小， $n-a_1$ 个数比它大，所以逆序对数的变化量为 $(n-a_1)-(a_1-1)=n+1-2a_1$。
所以我们之后把 $a_2$ 放到末尾，逆序对数的变化量为 $n+1-2a_2$。以此类推，把前 $k$ 个元素放到末尾的逆序对数为 $x +\sum\limits_{i=1}^k (n+1-2a_i)$。这个数最大就是 $(n+1-2a_i)$ 的前缀和最大。
所以我们可以用线段树维护前缀和数组的最大值，交换可以拆成两个原数组的单点修改，即前缀和数组的区间加。
时间复杂度 $\mathcal{O}(n+q\log n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10;
int n, q;
ll a[MAX_N], sum[MAX_N];
struct node {
ll val, tag;
int mxpos;
} d[MAX_N << 2];
inline int lc(int p) { return (p << 1); }
inline int rc(int p) { return (p << 1) | 1; }
inline void pu(int p) {
if(d[lc(p)].val >= d[rc(p)].val) d[p].val = d[lc(p)].val, d[p].mxpos = d[lc(p)].mxpos;
else d[p].val = d[rc(p)].val, d[p].mxpos = d[rc(p)].mxpos;
}
void pd(int p) {
if(d[p].tag) {
d[lc(p)].val += d[p].tag, d[rc(p)].val += d[p].tag;
d[lc(p)].tag += d[p].tag, d[rc(p)].tag += d[p].tag;
d[p].tag = 0;
}
}
void build_tree(int s, int t, int p) {
if(s == t) {
d[p].val = sum[s];
d[p].mxpos = s;
d[p].tag = 0;
return;
}
int mid = (s + t) >> 1;
build_tree(s, mid, lc(p));
build_tree(mid + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int l, int r, int p, ll D) {
if(l <= s && t <= r) {
d[p].val += D;
d[p].tag += D;
return;
}
pd(p);
int mid = (s + t) >> 1;
if(l <= mid) update(s, mid, l, r, lc(p), D);
if(r > mid) update(mid + 1, t, l, r, rc(p), D);
pu(p);
}
int solve() { return d[1].mxpos == n ? 0 : d[1].mxpos; }
int main() {
n = read(), q = read();
for(int i = 1; i <= n; i++)
a[i] = read(), sum[i] = sum[i - 1] + n + 1 - 2 * a[i];
build_tree(1, n, 1);
write(solve()), putchar('\n');
while(q--) {
int u = read(), v = read();
update(1, n, u, n, 1, 2 * a[u] - 2 * a[v]);
update(1, n, v, n, 1, 2 * a[v] - 2 * a[u]);
swap(a[u], a[v]);
write(solve()), putchar('\n');
}
return 0;
}
[HNOI2005] 狡猾的商人
本题有 $t$ 组数据。
现在有一个长度为 $n$ 的数列 $a_i$，给出 $m$ 个条件，每个条件形如 $(l,r,w)$，表示这个数列满足 $\sum\limits_{i=l}^r a_i = w$。问是否存在满足条件的数列。
$t\leq 100, n\leq 100, m\leq 1000$
题解
考虑前缀和数组 $s_i$，则每个条件等价于 $s_{l-1}+w=s_r$。这个显然可以差分约束，但是这里条件只有等于，所以我们有更简单的做法。若存在条件 $(l,r,w)$，我们则称 $l-1$ 和 $r$ 连通，且它们的距离为 $w$。对于一个连通块，不如直接用 dfs，从连通块中任选一点为原点搜出其他点的距离。接下来只需要枚举所有条件，检验是否满足 $dis_r-dis_{l-1}=w$ 即可。
时间复杂度 $\mathcal{O}(t(m+n))$。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 2e5 + 10;
int T, n, m, dis[MAX_N];
struct qry {
int u, v, w;
} Q[MAX_N];
vector<pii> G[MAX_N];
bool vis[MAX_N];
void dfs(int u) {
for(pii x : G[u]) {
int v = x.first, w = x.second;
if(!vis[v]) {
vis[v] = 1;
dis[v] = dis[u] + w;
dfs(v);
}
}
}
int main() {
T = read();
while(T--) {
n = read(), m = read();
for(int i = 0; i <= n; i++) {
dis[i] = vis[i] = 0;
G[i].clear();
}
for(int i = 1; i <= m; i++) {
int u = read() - 1, v = read(), w = read();
Q[i].u = u, Q[i].v = v, Q[i].w = w;
G[u].pb(make_pair(v, w)), G[v].pb(make_pair(u, -w));
}
for(int i = 0; i <= n; i++)
if(!vis[i]) vis[i] = 1, dfs(i);
bool flag = 1;
for(int i = 1; i <= m; i++) {
int u = Q[i].u, v = Q[i].v, w = Q[i].w;
if(dis[v] - dis[u] != w) {
flag = 0;
break;
}
}
puts(flag ? "true" : "false");
}
return 0;
}
存储管理
小 P 最近参加了华为挑战赛，比赛中题目给定了 $n$ 个不同的元素和 $k$ 个存储位置。
接下来题目给出了一个元素的访问顺序 $a_1, a_2,\dots, a_m$。当一个元素被访问时它必须处于某个存储位置中，同时任意时刻小 P 都可以将某个元素插入到一个空的存储位置中，或者删除一个存储位置上的元素。
最初所有位置都是空的，题目的目标是最小化插入元素的次数。小 P 为了解决这个问题学习了 LRU 算法，即记录下每个存储位置元素的最后一次访问的时刻，随后如果需要删除就删除最后一次访问时刻最小的那个元素。
例如 $n=3, k=2$，且 $a = {1, 2, 3, 2, 1, 2}$，那么在需要访问 $a_1 , a_2$ 直接插入即可；访问 $a_3$ 的时候位置已满，LRU 算法会选择删除 $1$ 这个元素因为它的访问时刻更早，随后插入 $3$；当访问 $a_4$ 的时候可以发现 $2$ 存在于一个位置中所以不用操作；当访问 $a_5$ 的时候需要删除 $3$ 这个元素因为 $2$ 在 $a_4$ 时又被访问了一次,最后一次访问比 $3$ 要更晚，随 后插入 $1$；访问 $a_6$ 时 $2$ 仍在一个位置中，故不用操作。故总插入次数为 $4$。
现在小 P 为了测试 LRU 的效率，它给了你 $n$ 和 $a_1,a_2,\dots,a_m$，希望你对 $k = 1, 2,\dots, n$ 求出答案。
$1\leq n,m\leq 5\times 10^5, 1\leq a_i\leq n$
题解
$\mathcal{O}(n^2)$：用队列模拟即可。
$\mathcal{O}(m\log n)$：考虑一个数 $a_i$ 可以对什么样的 $k$ 造成贡献。如果 $a_i$ 已经在一个位置中，而且在上一次到现在的时间内没有被换掉，则不需要插入，也就不会造成贡献。设 $a_i$ 上一次出现的位置为 $pre_i$，若 $[pre_i+1,i-1]$ 内的元素种类大于或等于 $k$，那么就会进行插入。我们可以通过扫描线 $\mathcal{O}(m\log n)$ 预处理出 $f_i$ 表示 $[pre_i+1,i-1]$ 的元素个数，则这会让 $k\in [1,f_i]$ 的答案加一，差分前缀和维护一下即可求出答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 5e5 + 10;
int n, m, a[MAX_N], pre[MAX_N], pos[MAX_N], f[MAX_N], ans[MAX_N];
struct BIT {
int t[MAX_N], mx;
BIT(int n) {
mx = n;
for(int i = 1; i <= mx; i++)
t[i] = 0;
}
int lowbit(int i) { return i & -i; }
void update(int i, int x) {
for(; i <= mx; i += lowbit(i))
t[i] += x;
}
int query(int i) {
int ret = 0;
for(; i >= 1; i -= lowbit(i))
ret += t[i];
return ret;
}
};
struct qry {
int l, r;
bool operator < (const qry &t) const { return r < t.r; }
} Q[MAX_N];
int main() {
freopen("manage.in", "r", stdin);
freopen("manage.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; i++)
pre[i] = -1;
for(int i = 1; i <= m; i++) {
a[i] = read();
pre[a[i]] = pos[a[i]];
Q[i].l = pre[a[i]] + 1, Q[i].r = i - 1;
pos[a[i]] = i;
}
sort(Q + 1, Q + m + 1);
BIT tree = BIT(m + 10);
for(int i = 1; i <= n; i++)
pre[i] = -1;
for(int i = 1, j = 1; i <= m; i++) {
while(j <= Q[i].r) {
if(pre[a[j]] != -1) tree.update(pre[a[j]], -1);
pre[a[j]] = j;
tree.update(j, 1);
j++;
}
if(pre[a[Q[i].r + 1]] == -1) f[Q[i].r + 1] = -1;
else f[Q[i].r + 1] = tree.query(Q[i].r) - tree.query(Q[i].l - 1);
}
for(int i = 1; i <= m; i++) {
if(f[i] != -1) ans[1]++, ans[f[i] + 1]--;
else ans[1]++, ans[n + 1]--;
}
for(int i = 1; i <= n; i++) {
ans[i] += ans[i - 1];
write(ans[i]), putchar(" \n"[i == n]);
}
return 0;
}
Ugu
给定一个仅由 $0$ 或 $1$ 组成的长度为 $n$ 的数列。定义一次操作是选择一个后缀并把这个后缀的所有元素取反，求最少使用多少次操作可以让这个序列单调不降。
$\sum n\leq 2\times 10^5$
Solution 1
首先，一个后缀最多只会取一次反。如果你选了以 $p_1,p_2,\dots,p_k$ 为开头的一系列后缀进行操作，你的操作实际上相当于 $[p_1,p_2-1]$ 取反，$[p_2,p_3-1]$ 不变，$[p_3,p_4-1]$ 取反，以此类推，奇数块取反，偶数块不变。
之后，观察到你对一段 $0/1$ 连通块同时取反，是不劣于把它拆开取反的。所以我们可以把连通块缩成一个元素，这时数列就等价转化成了 $0/1$ 交替出现的形式。丢掉开头的 $0$ 不管，最终数列一定变成以下形式：
\[10101010\dots\]接下来你可以构造一个对于这个数列进行操作的最优方案，不妨拆成 $10, 1, 0, 1, 0,\dots$ 这些块，其中奇数块取反，偶数块不变。那么答案就是缩成的序列的长度减一。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline bool read_bool() {...}
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10;
int T, n, cnt;
bool f, a[MAX_N];
int main() {
T = read();
while(T--) {
n = read(), f = 0, cnt = 0;
for(int i = 1; i <= n; i++) {
a[i] = read_bool();
f |= a[i];
if(!f) continue;
if(a[i] != a[i - 1]) cnt++;
}
if(!f) cnt = 1;
write(cnt - 1), putchar('\n');
}
return 0;
}
Solution 2
既然是操作后缀，那么考虑从前往后 dp，每个点需不需要操作只和上一个有没有被取反有关。设计状态 $f(i, 0/1, 0/1)$ 表示考虑前 $i$ 个数，第 $i$ 个数取多少，第 $i$ 位是否和原数列中不同。转移显然，但代码写得有点抽象。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline bool read_bool() {...}
inline void write(ll x) {...}
const int INF = (1 << 30);
int T, n, dp[2][2][2];
int main() {
T = read();
while(T--) {
n = read();
dp[0][0][0] = dp[0][1][0] = 0, dp[0][0][1] = dp[0][1][1] = INF;
for(int i = 1; i <= n; i++) {
bool now = read_bool();
dp[i & 1][0][0] = dp[i & 1][1][0] = dp[i & 1][0][1] = dp[i & 1][1][1] = INF;
dp[i & 1][0][now] = min(dp[i & 1][0][now], dp[(i - 1) & 1][0][now]);
dp[i & 1][0][now] = min(dp[i & 1][0][now], dp[(i - 1) & 1][0][now ^ 1] + 1);
dp[i & 1][1][now ^ 1] = min(dp[i & 1][1][now ^ 1], min(dp[(i - 1) & 1][0][now ^ 1], dp[(i - 1) & 1][1][now ^ 1]));
dp[i & 1][1][now ^ 1] = min(dp[i & 1][1][now ^ 1], min(dp[(i - 1) & 1][0][now], dp[(i - 1) & 1][1][now]) + 1);
}
write(min({dp[n & 1][0][0], dp[n & 1][0][1], dp[n & 1][1][0], dp[n & 1][1][1]})), putchar('\n');
}
return 0;
}
Edges in MST
给定一个 $n$ 个点，$m$ 条边的带权无向图，考虑它的最小生成树。每条边有三种情况：
-
一定在最小生成树上。
-
有可能在最小生成树上，但不一定在最小生成树上。
-
不可能在最小生成树上。
请你确定每条边属于哪种情况。
$n,m\leq 10^5$
题解
先用 Kruskal 跑出任意一个最小生成树，现在这棵树的树边属于情况 1/2，非树边属于情况 2/3，不妨分别考虑。
对于非树边 $e(u,v,w)$，如果想要纳入最小生成树中，它就要在 Kruskal 的时候，作为较小的边，完成让 $u$ 和 $v$ 连通的任务。那么考虑树上的 $u$ 到 $v$ 的路径，只要在这条路径上存在一条边 $e_0(u_0,v_0,w_0)$，使得 $w_0\geq w$，那么我们就可以用 $e$ 替换 $e_0$，构造出合法的最小生成树。考虑充要转化，「存在一个大于或等于」等价于「最大值大于或等于」，那么我们只需要支持查询路径 $\max$ 即可，这个可以用倍增维护。
类似的，对于树边 $e(u,v,w)$，如果它不一定在最小生成树中，它就要能被一条非树边替换，也就是存在一条非树边 $e_0(u_0,v_0,w_0)$，使得 $e$ 属于树上 $u_0$ 到 $v_0$ 的路径，且 $w_0\leq w$，那么我们就可以用 $e_0$ 替换 $e$，构造出合法的最小生成树。考虑充要转化，「存在一个小于或等于」等价于「最小值小于或等于」。我们可以枚举非树边，然后将它两端的路径对这条边的权值取 $\min$，这个可以树剖加线段树维护。然而这也可以并查集，从小到大枚举非树边，然后暴力跳打最小值标记，对做过的部分用并查集跳过。
设 $n,m$ 同数量级，并查集的复杂度视为 $\mathcal{O}(\log n)$，则时间复杂度 $\mathcal{O}(n\log n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10, MAX_LOG = 17, INF = 1e9;
int n, m, cnt, ans[MAX_N], mn[MAX_N], fir[MAX_N], dep[MAX_N], fa[MAX_LOG][MAX_N], mx[MAX_LOG][MAX_N];
bool mst[MAX_N];
struct link {
int v, w, nxt;
link(int _v = 0, int _w = 0, int _nxt = 0) :
v(_v), w(_w), nxt(_nxt) { }
} e[MAX_N];
void AddEdge(int u, int v, int w) {
e[++cnt] = link(v, w, fir[u]);
fir[u] = cnt;
}
struct edge {
int u, v, w, id;
bool operator < (const edge &t) const { return w < t.w; }
} E[MAX_N];
struct dsu {
int fa[MAX_N], mx;
dsu(int _mx) {
mx = _mx;
for(int i = 1; i <= mx; i++)
fa[i] = i;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
};
void kruskal() {
dsu D = dsu(n);
sort(E + 1, E + m + 1);
for(int i = 1; i <= m; i++) {
int u = E[i].u, v = E[i].v, w = E[i].w;
int fu = D.find(u), fv = D.find(v);
if(fu == fv) continue;
D.fa[fu] = fv;
AddEdge(u, v, w), AddEdge(v, u, w);
mst[i] = 1;
}
}
void dfs(int u, int pre, int val) {
fa[0][u] = pre, mx[0][u] = val, dep[u] = dep[pre] + 1;
for(int i = 1; i < MAX_LOG; i++) {
fa[i][u] = fa[i - 1][fa[i - 1][u]];
mx[i][u] = max(mx[i - 1][u], mx[i - 1][fa[i - 1][u]]);
}
for(int i = fir[u]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if(v == pre) continue;
dfs(v, u, w);
}
}
pii query(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int res = 0;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[i][u] && dep[fa[i][u]] >= dep[v]) {
res = max(res, mx[i][u]);
u = fa[i][u];
}
if(u == v) return make_pair(res, u);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[i][u] && fa[i][v] && fa[i][u] != fa[i][v]) {
res = max({res, mx[i][u], mx[i][v]});
u = fa[i][u], v = fa[i][v];
}
res = max({res, mx[0][u], mx[0][v]});
return make_pair(res, fa[0][u]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++)
E[i].u = read(), E[i].v = read(), E[i].w = read(), E[i].id = i;
kruskal();
dfs(1, 0, 0);
dsu D = dsu(n);
for(int i = 1; i <= n; i++)
mn[i] = INF;
for(int i = 1; i <= m; i++)
if(!mst[i]) {
int u = E[i].u, v = E[i].v, w = E[i].w, id = E[i].id;
pii res = query(u, v);
ans[id] = (res.first >= w ? 2 : 3);
int lca = res.second;
while(dep[D.find(u)] > dep[lca]) {
int t = D.find(u);
mn[t] = w;
D.fa[t] = D.find(fa[0][t]);
}
while(dep[D.find(v)] > dep[lca]) {
int t = D.find(v);
mn[t] = w;
D.fa[t] = D.find(fa[0][t]);
}
}
for(int i = 1; i <= m; i++)
if(mst[i]) {
int u = E[i].u, v = E[i].v, w = E[i].w, id = E[i].id;
if(dep[u] < dep[v]) swap(u, v);
ans[id] = (mn[u] <= w ? 2 : 1);
}
for(int i = 1; i <= m; i++) {
if(ans[i] == 1) puts("any");
if(ans[i] == 2) puts("at least one");
if(ans[i] == 3) puts("none");
}
return 0;
}
饼干
有 $n$ 个魔咒，施展第 $i$ 个魔咒需要 $a_i$ 点能量。现在你有 $m$ 点能量。
如果现在你有 $a(a<m)$ 点能量，你可以用 $(m-a)$ 的代价回复 $1$ 点能量。
你有 $k$ 次机会，每次选定一个 $a_i\geq 1$，让它减一。
求把所有的魔咒都施展一遍的最小代价。
$1\leq n \leq 10^5,1\leq a_i\leq m\leq 10^6, 1\leq k\leq \sum a_i$
题解
对于 $k=0$，考虑贪心。如果你需要回复能量，却不回满，那么下次回复的代价就会变大。所以答案就是有一些回满，直到剩下需要的能量和不大于 $m$ 时，就只要回到剩下需要的能量和。为了让总代价尽量小，则让不需要回的尽量多，按 $a_i$ 从小到大做这个过程即可。
你发现每次代价加的是一个连续段 $1,2,\dots ,a_i$。那么设 $c_i$ 表示 $i$ 被加了几次，则答案为 $\sum i\cdot c_i$。那么一次机会就是选一个 $i$，使得 $c_i\gets c_i-1$。那么贪心地优先减去较大的 $i$ 即可。而且这样的话，$i$ 被删除前，比 $i$ 大的数都被减掉了，所以这样操作肯定是合法的。
时间复杂度 $\mathcal{O}(n\log n +m)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10;
ll n, m, k, res, a[MAX_N], s[MAX_N], c[MAX_N];
int main() {
n = read(), m = read(), k = read();
for(int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i];
for(int i = 1; i <= n - 1; i++)
if(s[n] - s[i] <= m) { c[m - (s[n] - s[i]) + 1]++, c[a[i] + 1]--; break; }
else c[1]++, c[a[i] + 1]--;
for(int i = 1; i <= m; i++)
c[i] += c[i - 1];
for(int i = m; i >= 1; i--) {
ll d = min(k, c[i]);
c[i] -= d, k -= d;
if(!k) break;
}
for(int i = 1; i <= m; i++)
res += c[i] * i;
write(res), putchar('\n');
return 0;
}
[NOIP2020] 字符串匹配
对于一个字符串 $S$，找到 $S$ 的所有具有下列形式的拆分方案数：
$S = ABC$，$S = ABABC$，$S = ABAB \ldots ABC$，其中 $A$，$B$，$C$ 均是非空字符串，且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量。
| $1 \le t \le 5$，$1 \le | S | \le 2^{20}$。 |
### 题解
我们枚举 $AB$ 的长度 $i$，然后枚举把 $AB$ 重复 $j$ 次，这样的复杂度是 $\mathcal{O}(\frac{n}{1}+\frac{n}{2}+\dots+\frac{n}{n})=\mathcal{O}(n\log n)$ 的。在这个过程中，我们用字符串哈希检验这是否和原串对应。
然后考虑怎么统计答案。 设 $\text{prec}(i)$ 表示 $[1,i]$ 中出现奇数次的字符个数，$\text{sufc}(i)$ 表示 $[i,n]$ 中出现奇数次的字符个数，那么这两个数组可以 $\mathcal{O}(n)$ 预处理。
设当前 $AB$ 长度为 $i$，$C$ 起点为 $k$，答案就是在可能的 $A$，也就是所有 $\text{prec}(1),\text{prec}(2),\dots,\text{prec}(i-1)$ 中，小于或等于 $\text{sufc}(k)$ 的个数。这个可以用树状数组维护。
时间复杂度是常数比较小的 $\mathcal{O}(t(n\log n\log 26))$，可过。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = (1 << 20) + 10, BASE = 13331, MOD = 998244353;
int T, n, cnt1[28], cnt2[28], val[MAX_N], power[MAX_N], prec[MAX_N], sufc[MAX_N];
ll ans;
char s[MAX_N];
struct BIT {
int t[MAX_N], mx;
BIT(int _mx) {
mx = _mx;
for(int i = 0; i <= mx; i++)
t[i] = 0;
}
int lowbit(int i) { return (i & -i); }
void update(int i, int x) {
for(; i <= mx; i += lowbit(i))
t[i] += x;
}
int query(int i) {
int res = 0;
for(; i; i -= lowbit(i))
res += t[i];
return res;
}
};
int get(int l, int r) { return (val[r] - 1ll * val[l - 1] * power[r - l + 1] % MOD + MOD) % MOD; }
void init() {
prec[0] = sufc[n + 1] = 0;
for(int i = 'a'; i <= 'z'; i++)
cnt1[i - 'a'] = cnt2[i - 'a'] = 0;
for(int i = 1, j; i <= n; i++) {
if(!power[i]) power[i] = 1ll * power[i - 1] * BASE % MOD;
val[i] = (1ll * val[i - 1] * BASE % MOD + (s[i] - 'a')) % MOD;
cnt1[s[i] - 'a']++;
if(cnt1[s[i] - 'a'] & 1) prec[i] = prec[i - 1] + 1;
else prec[i] = prec[i - 1] - 1;
j = n - i + 1;
cnt2[s[j] - 'a']++;
if(cnt2[s[j] - 'a'] & 1) sufc[j] = sufc[j + 1] + 1;
else sufc[j] = sufc[j + 1] - 1;
}
}
int main() {
T = read();
power[0] = 1;
while(T--) {
scanf("%s", s + 1);
n = strlen(s + 1), ans = 0;
init();
BIT tree(28);
for(int i = 2; i <= n; i++) {
tree.update(prec[i - 1] + 1, 1);
for(int j = 1; i * j < n; j++) {
int l = i * (j - 1) + 1, r = i * j;
if(get(l, r) != get(1, i)) break;
ans += tree.query(sufc[r + 1] + 1);
}
}
write(ans), putchar('\n');
}
return 0;
}
♥