当前位置:网站首页>【luogu U142356】Suffix of the Brave (SA) (Chairman Tree) (2 points)
【luogu U142356】Suffix of the Brave (SA) (Chairman Tree) (2 points)
2022-08-09 04:50:00 【SSL_TJH】
The brave suffix
题目链接:luogu U142356
题目大意
给你一个字符串,Each time you ask to you i,l,r To you all l~r As a starting point of the suffix which with i As a starting point of the suffix public longest prefix the longest.
If there are multiple as long,输出字典序最小的.
思路
首先考虑 SA / SAM.
然后如果是 SA,Between the two suffix public longest prefix is r n k \rm rnk rnk 区间中的 min \min min.
如果是 SAM,那就是 fail 树上的 LCA(The opposite building)
Then consider how to find min \min min The largest of or LCA 最下面的.(Actually find is probably the same)
那因为是 min \min min,Nature is a short time will appear(LCA In fact is on the bottom of the in dfs Order the latest)
So we find it is the precursor of subsequent.
However, we can only find l ∼ r l\sim r l∼r 的,So we can use, chairman of the tree to maintain looking for.
(Then find precursor successor has a simple method is to look for the front of it there are many k k k,And then precursor is positioning to the first k − 1 k-1 k−1 个,Similarly a successor is k k k)
(What I don't know why everyone always know,Tears of)
Selected dictionary and found that if the answer is the same to the smallest.
Consider how make,The first two answers compare,If the right than the left superior right must be right that the optimum(Because all is according to the dictionary sequence row,SAM 的 dfs Order is the dictionary order)
What about on the left side of the?
Then we can find the most on the left side of the binary,And then use that can.
代码
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 100;
int n, ans1[N], ans2[N], ss[N];
char s[N];
struct Ask {
int id, l, r;
};
vector <Ask> q[N];
int sa[N], xx[N], yy[N], fir[N], log2_[N];
int height[N][21], rnk[N], tong[N], kind, ynum;
void Sort(int m, int *x, int *y) {
for (int i = 1; i <= m; i++) tong[i] = 0;
for (int i = 1; i <= n; i++) tong[x[i]]++;
for (int i = 2; i <= m; i++) tong[i] += tong[i - 1];
for (int i = n; i >= 1; i--) sa[tong[fir[i]]--] = y[i];
}
void SA(int *r, int *sa, int n, int m) {
int *x = xx, *y = yy;
for (int i = 1; i <= n; i++) x[i] = r[i] + 1;
for (int i = 1; i <= n; i++) y[i] = i;
for (int i = 1; i <= n; i++) fir[i] = x[y[i]];
Sort(m, x, y);
for (int j = 1; j < n; j <<= 1) {
ynum = 0;
for (int i = n - j + 1; i <= n; i++)
y[++ynum] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > j) y[++ynum] = sa[i] - j;
for (int i = 1; i <= n; i++) fir[i] = x[y[i]];
Sort(m, x, y);
swap(x, y);
kind = 1;
x[sa[1]] = 1;
for (int i = 2; i <= n; i++)
if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = kind;
else x[sa[i]] = ++kind;
if (kind == n) break;
m = kind;
}
}
void get_height(int *r, int *sa, int n) {
int k = 0, j;
for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
for (int i = 1; i <= n; i++) {
if (k) k--;
j = sa[rnk[i] - 1];
while (r[i + k] == r[j + k] && i + k <= n && j + k <= n) k++;
height[rnk[i]][0] = k;
}
}
void get_RMQ(int n) {
log2_[0] = -1; for (int i = 1; i <= n; i++) log2_[i] = log2_[i >> 1] + 1;
for (int i = 1; i <= 20; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
height[j][i] = min(height[j][i - 1], height[j + (1 << (i - 1))][i - 1]);
}
int RMQ_sa(int l, int r) {
if (!l || !r) return 0;
if (l == r) return n - l + 1;
l = rnk[l]; r = rnk[r]; if (l > r) swap(l, r);
l++; int k = log2_[r - l + 1];
return min(height[l][k], height[r - (1 << k) + 1][k]);
}
int RMQ_rnk(int l, int r) {
if (!l || !r) return 0;
if (l == r) return n - sa[l] + 1;
if (l > r) swap(l, r);
l++; int k = log2_[r - l + 1];
return min(height[l][k], height[r - (1 << k) + 1][k]);
}
struct XD_tree {
int ls[N << 6], rs[N << 6], sum[N << 6], tot;
int copy(int x) {
int now = ++tot; ls[now] = ls[x]; rs[now] = rs[x]; sum[now] = sum[x]; return now;
}
void insert(int &now, int l, int r, int pl) {
now = copy(now); sum[now]++;
if (l == r) return ; int mid = (l + r) >> 1;
if (pl <= mid) insert(ls[now], l, mid, pl); else insert(rs[now], mid + 1, r, pl);
}
int get_sum(int now1, int now2, int l, int r, int L, int R) {
if (!(sum[now2] - sum[now1])) return 0;
if (L <= l && r <= R) return sum[now2] - sum[now1];
int mid = (l + r) >> 1, re = 0;
if (L <= mid) re += get_sum(ls[now1], ls[now2], l, mid, L, R);
if (mid < R) re += get_sum(rs[now1], rs[now2], mid + 1, r, L, R);
return re;
}
int get_k(int now1, int now2, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (k <= sum[ls[now2]] - sum[ls[now1]]) return get_k(ls[now1], ls[now2], l, mid, k);
else return get_k(rs[now1], rs[now2], mid + 1, r, k - (sum[ls[now2]] - sum[ls[now1]]));
}
}T;
int rt[N];
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
for (int i = 1; i <= n; i++) ss[i] = s[i] - 'a';
SA(ss, sa, n, n);
get_height(ss, sa, n);
get_RMQ(n);
for (int i = 1; i <= n; i++)
rt[i] = rt[i - 1], T.insert(rt[i], 1, n, rnk[i]);
int Q; scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
int x, l, r; scanf("%d %d %d", &x, &l, &r);
q[x].push_back((Ask){
i, l, r});
}
for (int i = 1; i <= n; i++) {
int x = rnk[i];
for (int j = 0; j < q[i].size(); j++) {
int id = q[i][j].id, l = q[i][j].l, r = q[i][j].r;
int num = T.get_sum(rt[l - 1], rt[r], 1, n, 1, x - 1), L = 0, R = 0;
if (num) L = T.get_k(rt[l - 1], rt[r], 1, n, num);
if (num < T.sum[rt[r]] - T.sum[rt[l - 1]]) R = T.get_k(rt[l - 1], rt[r], 1, n, num + 1);
int re1 = RMQ_rnk(L, x), re2 = RMQ_rnk(x, R);
if (re2 > re1) {
ans1[id] = re2; ans2[id] = sa[R];
}
else {
int L_ = 1, R_ = L, re = L;
while (L_ <= R_) {
int mid = (L_ + R_) >> 1;
if (RMQ_rnk(mid, x) >= re1) re = mid, R_ = mid - 1;
else L_ = mid + 1;
}
int numb = T.get_sum(rt[l - 1], rt[r], 1, n, 1, re - 1);
L = T.get_k(rt[l - 1], rt[r], 1, n, numb + 1);
ans1[id] = re1; ans2[id] = sa[L];
}
}
}
for (int i = 1; i <= Q; i++) printf("%d %d\n", ans1[i], ans2[i]);
return 0;
}
边栏推荐
- Integer multiple series
- B. Arrays Sum
- `数学` 极限, 渐进分析, 近似阶, 线性化, 线性近似, 线性函数
- 稳定性测试怎么做,这篇文章彻底讲透了!
- [UNR #6 A] Noodle-based road (shortest path)
- 2022 Security Officer-A Certificate Special Work Permit Exam Question Bank and Online Mock Exam
- Dingding conflicts with RStudio shortcuts--Dingding shortcut settings
- 【Harmony OS】【ARK UI】自定义弹窗
- 【暑期每日一题】洛谷 P5724 【深基4.习5】求极差 / 最大跨度值
- 关于sys.path.append(‘..‘)失效
猜你喜欢
LeetCode-从链表中删去总和值为零的连续结点
[OpenCV] - Find and draw contours
数量遗传学遗传力计算2:半同胞和全同胞
[21天学习挑战赛——内核笔记](四)——内核常见调试手段(printf、dump_stack、devmem)
杰理之手机OTG问题【篇】
leetcode:316. 去除重复字母
【MLT】MLT多媒体框架生产消费架构解析(二)
C进阶-C语言文件操作
2022 Security Officer-B Certificate Exam Practice Questions and Online Mock Exam
【Harmony OS】【FAQ】Hongmeng Questions Collection 1
随机推荐
OKR management process, how to implement effective dialogue, using the CFR feedback and recognition?
mysql content does not exist error
基于ABP和Magicodes实现Excel导出操作
在快手工作是一种什么体验
【暑期每日一题】洛谷 P4325 [COCI2006-2007#1] Modulo
ABP中的数据过滤器
How to choose an APS system, it is necessary to clarify these seven key factors
2022下半年深圳信息系统项目管理师认证招生简章
如何剪裁svg并压缩
[Harmony OS] [ArkUI] ets development graphics and animation drawing
C进阶 - 程序的编译(预处理操作) + 链接
2022 High-altitude installation, maintenance, and demolition exam practice questions and mock exams
【HMS Core】【FAQ】【AR Engine】AR Engine FAQ
【暑期每日一题】洛谷 P1200 [USACO1.1]你的飞碟在这儿Your Ride Is Here
【Harmony OS】【ARK UI】Date 基本操作
学习笔记--文件夹处理--代码学习
杰理之手机OTG问题【篇】
钉钉与RStudio快捷方式冲突--钉钉快捷键设置
【暑期每日一题】洛谷 P8086 『JROI-5』Music
equals和==