2021杭电多校第四场
MorphLing
8月 02, 2021
04. Display Substring
题意：给出一个字符串S，每个字符有一个权值，某个串的权值为所有字符权值之和，问S中权值第k小的字串权值是多少（重复的字串不计）
如果计算重复的子串，可以二分答案之后将每个位置作为字串开始位置，再二分右端，判断答案是否小于k。因此需要考虑如何去掉重复的子串。后缀数组中height[i]数组表示后缀第i小的子串与后缀第i-1小的字串的最长公共前缀LCP，发现每个位置i的height[i]恰好就是重复子串的数量，减去重复后进行判断
（贴队友代码存板
#include <bits/stdc++.h>
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
// ----------------check here before submitting your code--------------------------------
#define QWQ1
// -------------------------------------check here before submitting your code-----------
const int INF = 2e9;
const long long INF64 = 4e18;
const double PI = acos(-1);
typedef long long ll;
typedef double db;
typedef complex<double> cb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define LOG(qwq...) fprintf(stderr, qwq)
#define rep(x, y, z) for (int(x) = int(y); int(x) <= int(z); x++)
#define per(x, y, z) for (int(x) = int(y); int(x) >= int(z); x--)
#define min3(x, y, z) min((x), min((y), (z)))
#define max3(x, y, z) max((x), max((y), (z)))
#define lowbit(x) ((-(x)) & (x))
#define ms1(a) memset((a), 0, (sizeof(a)))
#define ms2(a) memset((a), 0x3f, (sizeof(a)))
#define ms3(a) memset((a), -1, (sizeof(a)))
const int MOD = 998244353;
int mul(int x, int y) { return 1ll * x * y % MOD; }
int add(int x, int y) { return ((x + y) % MOD + MOD) % MOD; }
int sub(int x, int y) { return ((x - y) % MOD + MOD) % MOD; }
int qpow(int a, int b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans = mul(ans, a);
a = mul(a, a);
b /= 2;
}
return ans;
}
const int N = 2e5 + 5;
struct Suffix_Array {
int sa[N], rk[N * 2];
int oldrk[N * 2], cnt[N * 2], id[N], px[N * 2];
int ht[N];
int m = 300;
bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void clear(string &s) {
int n = s.size();
rep(i, 1, 2 * n) rk[i] = 0;
rep(i, 1, n) sa[i] = ht[i] = 0;
rep(i, 1, max(n, 200)) cnt[i] = 0;
}
void build_sa(string &s) {
int n = s.size();
int m = 200;
rep(i, 1, n) rk[i] = s[i - 1];
rep(i, 1, n) cnt[rk[i]]++;
rep(i, 1, m) cnt[i] += cnt[i - 1];
per(i, n, 1) sa[cnt[rk[i]]--] = i;
for (int w = 1; w < n; w <<= 1) {//排序长度为2w的子串
// 第二关键字排序
int p = 0;
per(i, n, n - w + 1) id[++p] = i; //该范围内的子串的第二关键字都是0
rep(i, 1, n) if (sa[i] > w) // sa[i] - w的后缀会以它为第二关键字
id[++p] = sa[i] - w;
// 第一关键字排序
rep(i, 1, m) cnt[i] = 0;
// memset(cnt, 0, sizeof(cnt));
rep(i, 1, n) cnt[px[i] = rk[id[i]]]++;
rep(i, 1, m) cnt[i] += cnt[i - 1];
per(i, n, 1) sa[cnt[px[i]]--] = id[i];
// 排名去重
rep(i, 1, 2 * n) oldrk[i] = rk[i];
// memcpy(oldrk, rk, sizeof(rk));
p = 0;
rep(i, 1, n) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
m = p;
}
for (int i = 1, k = 0; i <= n; i++) {
if (k)
k--;
while ((i + k <= n) && s[i + k - 1] == s[sa[rk[i] - 1] + k - 1]) //不小于前一个-1
k++;
ht[rk[i]] = k;
}
}
} sa;
int n;
ll k;
string s;
int c[N];
int pre[N];
bool ok(int x) {
ll sum = 0;
rep(i, 1, n)
{
int ll = sa.sa[i];
int l = ll, r = n;
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (pre[mid] - pre[ll - 1] < x)
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
sum += max(ans - ll + 1 - sa.ht[i], 0);
}
if (sum < k)
return true;
else
return false;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> k;
cin >> s;
rep(i, 0, 25) cin >> c[i];
rep(i, 1, n) pre[i] = pre[i - 1] + c[(int)(s[i - 1] - 'a')];
int l = 1, r = pre[n] + 1;
sa.build_sa(s);
int ans = pre[n] + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (ok(mid)) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
if (ans == pre[n] + 1)
cout << -1 << endl;
else
cout << ans << endl;
sa.clear(s);
}
return 0;
}
05. Didn’t I Say to Make My Abilities Average in the Next Life?!
题意：给出一个长度为n的数列，有q次询问，每次询问给出一个区间$[l_i,r_i]$，问在区间内随机选择一个小区间，问小区间的$\frac{\max+\min}{2}$期望
典中典，做法好像很多，先给一个$O(n\log n)$的dp做法
首先根据期望性质，可以把最小值和最大值分开来算，比如先来考虑一个数作为区间最小值的情况，可以用单调栈找到每个数左边和右边第一个比它小的数的位置l和r，那么该数作为最小值的贡献为$a[i]\times(i-l)\times(r-i)$
画出来就是
问题是怎么把这个东西快速算出来
首先预处理一个$last[i]$表示i左边第一个比i小的数的位置
再计算$f[i]=f[last[i]]+a[i]\times(i-last[i])$
想一想这时候$f[i]$存的是什么
$i->last[i]->last[last[i]]->\cdots$显然构成一条链，这条链其实就是在用单调栈求last时，刚刚把i加入单调栈时，单调栈内的所有元素，可以发现，这时链上的每个位置都能够以最小值向右扩展至i（即每个点j到i的区间上，不存在比a[j]更小的数，否则j一定在某个时刻出栈）
所以说$f[i]$是一个前缀和！所有能被记录在$f[i]$中的答案已经会在$i$处产生一次贡献
这一步还是挺难理解的，结合上图，可以理解成把右边一段区间分成了一个个小段，每一个小段长度为1，每一小段的贡献都是一个一个加上去的
接下来，我们要在区间里找到一个最小值p（用st表实现），显然p把区间分成了独立的两个部分，先考虑如何计算右半部分的答案。由于p是最小值，因此对于右半部分的每个点，p一定在每个点所对应的链上，由于$f[i]$本质是个前缀和，所以每个点的贡献就是$f[i]-f[p]$，加起来就是$\sum\limits_{i=p+1}^rf[i]-f[p]$，发现这个东西又可以用前缀和优化，只要处理一个$sum[i]=\sum\limits_{j=i}^xf[j]$，右半部分的贡献就可以$O(1)$计算了，也就是$sum[i]-sum[p]-(r-p)\times f[p]$
至于左半部分其实和右半部分没有本质区别，我们可以理解成把数组反转过来之后，左右部分自然互换，且对解法不产生影响。计算时只需要从后往前再处理一遍
现在其实还只完成了一半，还要求最大值，但是只需要令$a[i]=-a[i]$，再做一遍同样的工作就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return (1ll * a * b % MOD + MOD) % MOD; }
int rmk(int a) { return (a % MOD + MOD) % MOD; }
int bin(int x, int p) {
int res = 1;
for (int b = x; p; p >>= 1, b = mul(b, b))
if (p & 1) res = mul(res, b);
return res;
}
int T, n, m, a[N], dp[N], last[N], mn[N][25], f[N], sum[N], inv2;
deque<int> q;
struct Query {
int l, r;
}qry[N];
int ans[N];
bool cmp(int x, int y) {
return a[x] == a[y] ? x < y : a[x] < a[y];
}
int getMin(int l, int r) {
int k = log2(r - l + 1);
return cmp(mn[l][k], mn[r - (1 << k) + 1][k]) ? mn[l][k] : mn[r - (1 << k) + 1][k];
}
void getAns(int type) {
for (int j = 0; j <= 17; j++) {
for (int i = 1; i <= n; i++) {
if (j == 0) mn[i][j] = i;
else mn[i][j] = cmp(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]) ? mn[i][j - 1] : mn[i + (1 << (j - 1))][j - 1];
}
}
q.clear();
memset(last, 0, sizeof(last));
memset(f, 0, sizeof(f));
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++) {
while(!q.empty() && cmp(i, q.back())) q.pop_back();
if (!q.empty()) last[i] = q.back();
q.push_back(i);
}
for (int i = 1; i <= n; i++) {
f[i] = add(f[last[i]], mul(a[i], i - last[i]));
sum[i] = add(sum[i - 1], f[i]);
}
for (int i = 1; i <= m; i++) {
int l = qry[i].l, r = qry[i].r;
int p = getMin(l, r);
ans[i] = add(ans[i], mul(type, sub(sub(sum[r], sum[p]), mul(f[p], sub(r, p)))));
ans[i] = add(ans[i], mul(type, mul(a[p], mul(r - p + 1, p - l + 1))));
}
q.clear();
memset(last, 0, sizeof(last));
memset(f, 0, sizeof(f));
memset(sum, 0, sizeof(sum));
for (int i = n; i >= 1; i--) {
while(!q.empty() && cmp(i, q.back())) q.pop_back();
if (!q.empty()) last[i] = q.back();
else last[i] = n + 1;
q.push_back(i);
}
for (int i = n; i >= 1; i--) {
f[i] = add(f[last[i]], mul(a[i], last[i] - i));
sum[i] = add(sum[i + 1], f[i]);
}
for (int i = 1; i <= m; i++) {
int l = qry[i].l, r = qry[i].r;
int p = getMin(l, r);
ans[i] = add(ans[i], mul(type, sub(sub(sum[l], sum[p]), mul(f[p], sub(p, l)))));
}
}
void solve() {
scanf("%d %d", &n, &m);
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d %d", &qry[i].l, &qry[i].r);
getAns(1);
for (int i = 1; i <= n; i++) a[i] = -a[i];
getAns(-1);
for (int i = 1; i <= m; i++) {
int len = qry[i].r - qry[i].l + 1;
int fm = mul(mul(len, len - 1), inv2);
fm = add(fm, len);
printf("%d\n", mul(bin(fm, MOD - 2), mul(inv2, ans[i])));
}
}
int main() {
scanf("%d", &T);
inv2 = bin(2, MOD - 2);
while(T--) solve();
return 0;
}
09. License Plate Recognition
题意：给出一个$n\times m$的棋盘，有一些格子不能走，一个人从$(1,1)$出发，每步只能往下或往右走，问一共有多少个格子是能走到的
逐行递推，可以发现一个不能走的格子只会产生一段连续的不能走的格子，因此总个数$O(k)$，而产生连续不能走的格子只有两种情况：
- 从上一行第一个格子起有一段不能走的格子，将这些格子直接平移到下一行
- 某个不能走的格子右上方有一段不能走的格子，将这些格子平移到下一行
一开始想到用树状数组或线段树之类的方法维护，实际上只要用一个vector记录不能走的区间即可
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define per(x,y,z) for (int x=y;x>=z;x--)
#define pre (cur ^ 1)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 1e9 + 7, MOD2 = 1e9 + 9, INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
const int maxn=111;
const double pi=3.1415926535897932384626433832795,eps=1e-14;
int T, n, m, k;
vector<pii> vc[2];
vector<int> G[N];
ll ans;
vector<pii> rebuild(vector<pii> &vc) {
vector<pii> res;
int nl, nr;
nl = nr = -1;
for (auto now : vc) {
if (nl == -1 && nr == -1) nl = now.first, nr = now.second;
else {
if (now.first == nr + 1) nr = now.second;
else {
res.push_back({nl, nr});
nl = now.first;
nr = now.second;
}
}
}
if (!((nl == -1) && (nr == -1))) res.push_back({nl, nr});
return res;
}
void getAns(vector<pii> &vc) {
for (auto X : vc) {
ans += X.second - X.first + 1;
}
}
void solve() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++) G[i].clear();
for (int i = 1; i <= k; i++) {
int u, v; scanf("%d %d", &u, &v);
G[u].push_back(v);
}
int cur = 0;
ans = 0;
vc[pre].clear();
for (int i = 1; i <= n; i++) {
sort(all(G[i]));
vc[cur].clear();
auto it = vc[pre].begin();
int j = 0, mxr = 0;
if (it != vc[pre].end() && it->first == 1) {
vc[cur].push_back({it->first, it->second});
mxr = it->second;
it++;
}
if (G[i].size() != 0) {
if (i == 1) {
vc[cur].push_back({G[1][0], m});
} else {
for (; j < G[i].size(); j++) {
if (G[i][j] <= mxr) continue;
while(!(it == vc[pre].end()) && it->second <= G[i][j]) it++;
if (it != vc[pre].end()) {
if (it->first <= G[i][j] + 1 && it->second >= G[i][j] + 1) {
if (it->first == 1) vc[cur].push_back({1, it->second}), mxr = it->second;
else vc[cur].push_back({G[i][j], it->second}), mxr = it->second;
} else vc[cur].push_back({G[i][j], G[i][j]}), mxr = G[i][j];
} else vc[cur].push_back({G[i][j], G[i][j]}), mxr = G[i][j];
}
}
}
vc[cur] = rebuild(vc[cur]);
getAns(vc[cur]);
cur ^= 1;
}
printf("%lld\n", 1ll * n * m - ans);
}
int main()
{
scanf("%d", &T);
while(T--) {
solve();
}
return 0;
}