没有传送门题目大意考场上的思路思路参考代码
没有传送门
题目大意
给你一个长度为
n
n
的由小写字符组成的字符串。每个位置（不是每种字符）有一个权值。定义它的某个子串的排名为：把原串中所有子串按字典序降序排序并去重后这个子串所在的位置。称一个子串是我们想要的，当且仅当：这个子串的排名等于这个子串的权值之和。求在所有 n22n22 个子串中，有多少个子串是我们想要的。要求输出这些子串。
n≤200000
n
≤
200000
；权值非负，保证权值之和不会溢出；保证答案不超过
200000
200000
。
Limited Constraint： 1.
n≤50
n
≤
50
； 2.
n≤1000
n
≤
1000
； 3.
n≤50000
n
≤
50000
。
Special Instance： 1. 字符串只由一种字符组成； 2. 所有位置权值相同。
考场上的思路
n≤50
n
≤
50
估计是把所有子串拿出来 sort 吧……我没管它，由于时间不多，就没有做 Special Instance 了，只做了
n≤1000
n
≤
1000
的情况。
由于题目要求去重，因此考虑后缀数组。对于
SAi
S
A
i
的某个子串，如果在
heighti
h
e
i
g
h
t
i
范围内，那么它的排名就是之前算过的排名；否则它的排名从左到右，从上到下依次递增。当我遇到一个新的子串时（即遇到一个
heighti
h
e
i
g
h
t
i
范围外的子串时），我直接暴力向下查找与它相等的子串，并更新答案。这样每个子串会被计算一次，时间复杂度为
O(n2)
O
(
n
2
)
。
思路
首先肯定要用后缀数组（你用 SAM 当我没说，但是这种要去重的应该后缀数组很好做吧，关键是接下的步骤 SAM 不好做），所以第一步是对的。注意到这么一个问题：平常后缀排序都是升序，这里的降序是个什么鬼？
注意到权值非负，也就是说前缀和非负。考虑这么一个问题：当子串左端点确定时，右端点越往右，那么这个子串字典序越大，排名越小；但是前缀和却越来越大。换句话说，对于一个左端点，至多只会有一个我们想要的子串……
考虑二分排名的前缀和的位置，那么现在的问题就是如何求一个子串的排名。似乎没有一个好的在线求子串排名的方法，考虑离线。自然想到按 SA 从小到大的顺序处理，因为 SA 上子串的排名是依次的（就是暴力的那种方法）。如果对于每个后缀我们能够维护每个前缀的排名，问题就解决了。
观察从
SAi
S
A
i
到
SAi+1
S
A
i
+
1
排名是如何变化的。在
heighti
h
e
i
g
h
t
i
范围内，排名不会变化；在
heighti
h
e
i
g
h
t
i
范围外，排名会从当前的计数器开始依次递减：这是一个等差数列。考虑用线段树维护这个东西，显然可以
O(nlogn)
O
(
n
log
n
)
区间赋值和区间加等差数列。线段树维护的排名也应该是从左到右递减的，因此可以直接在线段树上二分。
虽然这里说是区间加等差数列，但实际上我们的操作时先清空，再区间加等差数列，相当于让区间等于一个等差数列，因此可以方便地维护最小值，也就可以二分了。由于我们直接在线段树上二分，因此时间复杂度为
O(nlogn)
O
(
n
log
n
)
。实际操作时，只需要写一个区间赋值等差数列即可。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::
cin;
using std::
cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a =
0;
bool positive =
true;
char ch = getchar();
while (!(ch ==
'-' ||
std::
isdigit(ch))) ch = getchar();
if (ch ==
'-') { positive =
false; ch = getchar(); }
while (
std::
isdigit(ch)) { a = a *
10 - (ch -
'0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[
20];
int length =
0;
if (x <
0)
putchar(
'-');
else x = -x;
do buffer[length++] = -(x %
10) +
'0';
while (x /=
10);
do putchar(buffer[--length]);
while (length);
}
const int maxn =
int(
2e5) +
5;
int n;
char str[maxn];
int val[maxn];
struct SuffixArray
{
int temp[maxn];
int x[maxn];
int y[maxn];
int buf_size;
int buf[maxn];
int SA[maxn];
int Rank[maxn];
int Height[maxn];
void GetSA()
{
buf_size =
128;
int* rank = x;
int* SA_second = y;
for (
int i =
0; i < n; i++)
rank[i] = str[i];
for (
int i =
0; i < buf_size; i++) buf[i] =
0;
for (
int i =
0; i < n; i++) buf[rank[i]]++;
for (
int i =
1; i < buf_size; i++) buf[i] += buf[i -
1];
for (
int i = n -
1; ~i; i--) SA[--buf[rank[i]]] = i;
for (
int k =
1; k <= n; k <<=
1)
{
int t =
0;
for (
int i = n - k; i < n; i++)
SA_second[t++] = i;
for (
int i =
0; i < n; i++)
if (SA[i] >= k)
SA_second[t++] = SA[i] - k;
for (
int i =
0; i < buf_size; i++) buf[i] =
0;
for (
int i =
0; i < n; i++) buf[rank[SA_second[i]]]++;
for (
int i =
1; i < buf_size; i++) buf[i] += buf[i -
1];
for (
int i = n -
1; ~i; i--)
SA[--buf[rank[SA_second[i]]]] = SA_second[i];
int* oldRank = rank;
std::swap(rank, SA_second);
rank[SA[
0]] =
0;
t =
1;
for (
int i =
1; i < n; i++)
rank[SA[i]] = (oldRank[SA[i -
1]] == oldRank[SA[i]] &&
SA[i -
1] + k < n && SA[i] + k < n &&
oldRank[SA[i -
1] + k] == oldRank[SA[i] + k]) ? t -
1 : t++;
if (t >= n)
break;
buf_size = t;
}
}
void GetHeight()
{
for (
int i =
0; i < n; i++)
Rank[SA[i]] = i;
int same =
0;
for (
int i =
0; i < n; i++)
{
if (Rank[i])
{
if (same) same--;
int pre = SA[Rank[i] -
1];
while (i + same < n && pre + same < n &&
str[i + same] == str[pre + same])
same++;
}
else
same =
0;
Height[Rank[i]] = same;
}
}
} suffix_array;
int* sa;
int* height;
std::
vector<std::pair<int, int> > ans;
#define RunInstance(x) delete new x
struct brute
{
brute()
{
LL all =
0;
for (
int i =
0; i < n; i++)
all += n - sa[i] - height[i];
LL rank =
0;
for (
int i =
0; i < n; i++)
{
for (
int j = height[i]; j < n - sa[i]; j++)
{
rank++;
int k = i;
do
{
if (val[sa[k] + j +
1] - val[sa[k]] == all - rank +
1)
ans.push_back(
std::make_pair(sa[k] +
1, sa[k] + j +
1));
k++;
}
while (k < n && height[k] > j);
}
}
}
};
struct work
{
class SegTree
{
static inline int code(
int l,
int r)
{
return (l + r) | (l != r);
}
struct Node
{
LL min;
bool bFlag;
LL a;
int d;
Node() : min(), bFlag(), a(), d() {}
} nodes[maxn *
2];
int g_L, g_R, g_Pos, g_Val;
void cover(
int l,
int r, LL a,
int d)
{
Node& t = nodes[code(l, r)];
t.min = a + (r - l) * d;
t.bFlag =
true;
t.a = a;
t.d = d;
}
void pushdown(
int l,
int r)
{
Node& t = nodes[code(l, r)];
if (t.bFlag)
{
int mid = (l + r) >>
1;
cover(l, mid, t.a, t.d);
cover(mid +
1, r, t.a + t.d * (mid - l +
1), t.d);
t.bFlag =
false;
}
}
void update(
int l,
int r)
{
Node& t = nodes[code(l, r)];
int mid = (l + r) >>
1;
Node& lc = nodes[code(l, mid)];
Node& rc = nodes[code(mid +
1, r)];
t.min =
std::min(lc.min, rc.min);
}
void modify_(
int l,
int r, LL a)
{
if (g_L <= l && r <= g_R)
{
cover(l, r, a, g_Val);
return;
}
pushdown(l, r);
int mid = (l + r) >>
1;
if (g_R <= mid)
modify_(l, mid, a);
else if (g_L > mid)
modify_(mid +
1, r, a);
else
{
modify_(l, mid, a);
modify_(mid +
1, r, a + g_Val * (mid -
std::max(l, g_L) +
1));
}
update(l, r);
}
void query_(
int l,
int r)
{
if (l == r)
{
Node& t = nodes[code(l, r)];
if (val[g_Pos + l] - g_Val == t.min)
ans.push_back(
std::make_pair(g_Pos +
1, g_Pos + l));
return;
}
pushdown(l, r);
int mid = (l + r) >>
1;
if (g_R <= mid)
return void(query_(l, mid));
Node& lc = nodes[code(l, mid)];
if (lc.min > val[g_Pos + mid] - g_Val)
query_(mid +
1, r);
else
query_(l, mid);
}
public:
void modify(
int l,
int r, LL a,
int d)
{
g_L = l;
g_R = r;
g_Val = d;
modify_(
1, n, a);
}
void query(
int r,
int base,
int sub)
{
g_L =
1;
g_R = r;
g_Pos = base;
g_Val = sub;
query_(
1, n);
}
} st;
work()
{
LL all =
0;
for (
int i =
0; i < n; i++)
all += n - sa[i] - height[i];
for (
int i =
0; i < n; i++)
{
st.modify(height[i] +
1, n - sa[i], all, -
1);
st.query(n - sa[i], sa[i], val[sa[i]]);
all -= n - sa[i] - height[i];
}
}
};
void run()
{
scanf(
"%s", str);
n =
strlen(str);
suffix_array.GetSA();
suffix_array.GetHeight();
sa = suffix_array.SA;
height = suffix_array.Height;
for (
int i =
1; i <= n; i++)
val[i] = val[i -
1] + readIn();
if (n <=
1000)
RunInstance(brute);
else
RunInstance(work);
std::sort(ans.begin(), ans.end());
printOut(ans.size());
putchar(
'\n');
for (
int i =
0; i < ans.size(); i++)
{
printOut(ans[i].first);
putchar(
' ');
printOut(ans[i].second);
putchar(
'\n');
}
}
int main()
{
#ifndef LOCAL
freopen(
"platform.in",
"r", stdin);
freopen(
"platform.out",
"w", stdout);
#endif
run();
return 0;
}
