LOJ#2720 你的名字
2024-09-02 21:28:11
题意：给定母串s和若干个询问。每个询问是一个串t和两个数l,r，表示求t中有多少个本质不同的子串没有在s[l,r]中出现过。
解：我写的并不是正解......是个毒瘤做法。只在loj上面卡时过了就写loj的题号好了...
首先有个68分部分分是l = 1， r = |s|，这个怎么做呢？
回忆起之前写的广义SAM的套路，我们建出广义SAM之后把s的所有子串标记。
然后对于每个t跑一遍SAM，跳fail的时候如果该节点被标记了就停止。这样走到的节点所代表的子串总数就是该串的答案。
68分还是比较友善的...
然后顺着这个思路思考正解。
多了个母串范围限制，又听说这个题是线段树合并，这就很自然了。
对于每个节点用值域线段树维护right集合，然后对于每一个询问，查看该节点是否有个right存在于[l,r]之间。存在就GG了，同时也不能往上传递。否则可以加上这个节点的贡献。有一种居中的情况就是一个节点所表示的串中，有些可选，有些不行。这种情况下不用向上传递(然而我当时没想到，传了...无伤大雅)
细节上就是找到那一段暧昧区域的最右边一个right，用线段树上找第k个实现。
那么我们要一个一个询问的处理吗？我很天真的以为线段树合并之后下面的线段树就不存在了....于是只能把询问一次性处理。于是我又SB的对询问开了个线段树，继续线段树合并......
具体来说，对于每个询问串，都在对应节点加上该串的询问。然后DFSfail树，在每一个节点遍历询问线段树，处理询问，然后向上合并。如果不会有贡献就删去这个节点，减少复杂度。
还有个小问题，right线段树合并的时候sum是两棵树的sum和，但是询问的那棵线段树合并要去重，所以不能把sum累加...然后发现询问线段树不需要查sum......这样就可以了。
因为加了很多常数优化所以代码不是很能看......复杂度分析也不会...反正估计也是不对的。uoj洛谷都T了。bzoj空间限制512M根本开不下。只有loj过了(loj牛逼！！！)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue> template <class T> inline void read(T &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} typedef long long LL;
const int N = , M = ;
using std::string; struct SGT { // 两个线段树合并
int tot, sum[M * ], ls[M * ], rs[M * ], rt[M * ], p, k;
std::queue<int> Q;
inline int np() {
if(Q.empty()) {
return ++tot;
}
int t = Q.front();
Q.pop();
sum[t] = ls[t] = rs[t] = ;
return t;
}
void add(int l, int r, int &o) {
if(!o) {
o = np();
}
if(l == r) {
sum[o]++;
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
add(l, mid, ls[o]);
}
else {
add(mid + , r, rs[o]);
}
sum[o] = sum[ls[o]] + sum[rs[o]];
return;
}
int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
int z = np();
sum[z] = sum[x] + sum[y];
ls[z] = merge(ls[x], ls[y]);
rs[z] = merge(rs[x], rs[y]);
Q.push(x);
Q.push(y);
return z;
}
int ask(int L, int R, int l, int r, int o) {
if(!o) {
return ;
}
if(L <= l && r <= R) {
return sum[o];
}
int mid = (l + r) >> , ans = ;
if(L <= mid) {
ans += ask(L, R, l, mid, ls[o]);
}
if(mid < R) {
ans += ask(L, R, mid + , r, rs[o]);
}
return ans;
}
inline void exmerge(int x, int y) {
rt[x] = merge(rt[x], rt[y]);
return;
}
int getK(int l, int r, int o) {
if(l == r) {
return r;
}
int mid = (l + r) >> ;
if(k <= sum[ls[o]]) {
return getK(l, mid, ls[o]);
}
else {
k -= sum[ls[o]];
return getK(mid + , r, rs[o]);
}
}
}rt, st; string str[N];
char ss[N], s[N];
int tot = , fail[M], len[M], e[M], tr[M][], top, n, m, nodel[N], noder[N], edgenex[M], edgev[M];
LL nodea[N]; inline void add(int x, int y) {
top++;
edgev[top] = y;
edgenex[top] = e[x];
e[x] = top;
return;
} inline int split(int p, int f) {
int Q = tr[p][f];
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
return nQ;
} inline int insert(int p, char c) {
int f = c - 'a';
if(tr[p][f]) {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
return Q;
}
return split(p, f);
}
int np = ++tot;
len[np] = len[p] + ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
fail[np] = split(p, f);
}
}
return np;
} void work(int l, int r, int &o, int x) {
if(!o || !st.sum[o]) {
if(o) {
st.Q.push(o);
}
o = ;
return;
}
if(l == r) {
// node[r]
int sum = ;
if(nodel[r] + len[fail[x]] <= noder[r]) {
sum = rt.ask(nodel[r] + len[fail[x]], noder[r], , n, rt.rt[x]);
}
if(!sum) {
nodea[r] += len[x] - len[fail[x]];
}
else {
int temp = ;
if(nodel[r] + len[x] - <= noder[r]) {
temp = rt.ask(nodel[r] + len[x] - , noder[r], , n, rt.rt[x]);
}
if(temp) {
//GG
st.sum[o] = ;
st.Q.push(o);
o = ;
return;
}
else {
// add some...
// find ->| (the right pos)
rt.k = rt.ask(, nodel[r] + len[x] - , , n, rt.rt[x]);
int ed = rt.getK(, n, rt.rt[x]);
nodea[r] += len[x] - (ed - nodel[r] + );
}
}
return;
}
int mid = (l + r) >> ;
if(st.ls[o]) {
work(l, mid, st.ls[o], x);
}
if(st.rs[o]) {
work(mid + , r, st.rs[o], x);
}
st.sum[o] = st.sum[st.ls[o]] + st.sum[st.rs[o]];
if(!st.sum[o]) {
st.Q.push(o);
o = ;
}
return;
} void solve(int x) {
for(int i = e[x]; i; i = edgenex[i]) {
int y = edgev[i];
solve(y);
if(x > ) {
rt.exmerge(x, y);
}
}
if(x > ) {
work(, m, st.rt[x], x);
if(fail[x] > ) {
st.exmerge(fail[x], x);
}
}
return;
} int main() { //freopen("name.in", "r", stdin);
//freopen("name.out", "w", stdout); scanf("%s", ss);
n = strlen(ss);
int last = ;
for(int i = ; i < n; i++) {
last = insert(last, ss[i]);
}
read(m);
for(int i = ; i <= m; i++) {
scanf("%s", s);
str[i] = (string)(s);
int t = strlen(s);
last = ;
for(int j = ; j < t; j++) {
last = insert(last, s[j]);
}
read(nodel[i]);
read(noder[i]);
}
//
int p = ;
for(int i = ; i < n; i++) {
p = tr[p][ss[i] - 'a'];
rt.p = i + ;
rt.add(, n, rt.rt[p]);
}
for(int i = ; i <= tot; i++) {
add(fail[i], i);
} for(int i = ; i <= m; i++) {
int t = str[i].size(), p = ;
for(int j = ; j < t; j++) {
// str[i][j]
p = tr[p][str[i][j] - 'a'];
st.p = i;
st.add(, m, st.rt[p]);
}
} solve(); for(int i = ; i <= m; i++) {
printf("%lld\n", nodea[i]);
}
return ;
}
AC代码
正解不是广义SAM，是普通SAM，还不用离线......还是我太菜了>_<
时限4s，你们感受一下...尤其是跟下面那个AC代码的对比......
正解：
68分：对S和T分别建sam然后同时跑T。跑到一个位置的时候会有一个匹配长度lenth。这时给T的节点打上长度为lenth的标记。
最后拓扑序跑一遍T的sam，统计答案。总不同子串数 - 匹配子串数。
#include <cstdio>
#include <cstring>
#include <algorithm> typedef long long LL;
const int N = , M = ; struct Edge {
int nex, v;
}edge[N << ]; int tp; int tr[N << ][], fail[N << ], len[N << ], last, tot;
int e[N << ], n, vis[N << ], Time, f[N], vis2[N << ], use[N << ], vis3[N << ];
int rt[N << ], ls[M], rs[M], cnt;
char str[N], ss[N]; inline void init() {
tot = last = ;
return;
} inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void insert(int p, int l, int r, int &o) {
if(!o) o = ++cnt;
use[o] = ;
if(l == r) {
return;
}
int mid = (l + r) >> ;
if(p <= mid) insert(p, l, mid, ls[o]);
else insert(p, mid + , r, rs[o]);
return;
} int merge(int x, int y) {
if(!x || !y) return x | y;
int o = ++cnt;
use[o] = use[x] | use[y];
ls[o] = merge(ls[x], ls[y]);
rs[o] = merge(rs[x], rs[y]);
return o;
} inline void insert(char c, int id) {
int f = c - 'a', p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
///insert(id, 1, n, rt[np]);
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} void DFS_1(int x) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
DFS_1(y);
rt[x] = merge(rt[x], rt[y]);
}
return;
} namespace sam {
int tot, len[N << ], fail[N << ], tr[N << ][], last, large[N << ];
int bin[N << ], topo[N << ];
inline void clear() {
for(int i = ; i <= tot; i++) {
memset(tr[i], , sizeof(tr[i]));
large[i] = bin[i] = fail[i] = len[i] = ;
}
tot = last = ;
return;
}
inline void insert(char c) {
//printf("insert : "); putchar(c); printf("\n");
int f = c - 'a', p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
}
inline LL sort() {
for(int i = ; i <= tot; i++) {
bin[len[i]]++;
}
for(int i = ; i <= tot; i++) {
bin[i] += bin[i - ];
}
for(int i = ; i <= tot; i++) {
topo[bin[len[i]]--] = i;
}
LL ans = ;
for(int i = tot; i >= ; i--) {
int x = topo[i];
if(large[x] > len[fail[x]]) {
ans -= std::min(len[x], large[x]) - len[fail[x]];
}
ans += len[x] - len[fail[x]];
large[fail[x]] = std::max(large[fail[x]], large[x]);
}
return ans;
}
} int main() { freopen("in.in", "r", stdin);
freopen("my.out", "w", stdout); init();
scanf("%s", str);
n = strlen(str);
for(int i = ; i < n; i++) {
insert(str[i], i + );
}
for(int i = ; i <= tot; i++) add(fail[i], i);
//DFS_1(1);
/// build over
int q, x, y;
scanf("%d", &q);
for(Time = ; Time <= q; Time++) {
//printf("i = %d \n", Time);
scanf("%s%d%d", ss, &x, &y);
int m = strlen(ss);
sam::clear();
for(int i = ; i < m; i++) {
sam::insert(ss[i]);
}
/// match
int p1 = , p2 = , lenth = ;
for(int i = ; i < m; i++) {
int ff = ss[i] - 'a';
p2 = sam::tr[p2][ff];
while(p1 && !tr[p1][ff]) {
p1 = fail[p1];
lenth = len[p1];
}
if(!p1) {
p1 = ;
}
if(tr[p1][ff]) {
p1 = tr[p1][ff];
lenth++;
}
sam::large[p2] = std::max(sam::large[p2], lenth);
}
LL ans = sam::sort();
printf("%lld\n", ans);
}
return ;
}
68分代码
100分：写个匹配函数来判断能不能匹配。失配的话先不跳fail，而是lenth--。
#include <cstdio>
#include <cstring>
#include <algorithm> typedef long long LL;
const int N = , M = ; struct Edge {
int nex, v;
}edge[N << ]; int tp; int tr[N << ][], fail[N << ], len[N << ], last, tot;
int e[N << ], n, Time, use[M];
int rt[N << ], ls[M], rs[M], cnt, X, Y;
char str[N], ss[N]; inline void init() {
tot = last = ;
return;
} inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void insert(int p, int l, int r, int &o) {
if(!o) o = ++cnt;
use[o] = ;
if(l == r) {
return;
}
int mid = (l + r) >> ;
if(p <= mid) insert(p, l, mid, ls[o]);
else insert(p, mid + , r, rs[o]);
return;
} int merge(int x, int y) {
if(!x || !y) return x | y;
int o = ++cnt;
use[o] = use[x] | use[y];
ls[o] = merge(ls[x], ls[y]);
rs[o] = merge(rs[x], rs[y]);
return o;
} inline void insert(char c, int id) {
int f = c - 'a', p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
insert(id, , n, rt[np]);
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} void DFS_1(int x) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
DFS_1(y);
rt[x] = merge(rt[x], rt[y]);
}
return;
} inline bool ask(int L, int R, int l, int r, int o) {
//printf("ask [%d %d] [%d %d] o = %d sum = %d \n", L, R, l, r, o, use[o]);
if(!o) return ;
if(L <= l && r <= R) return use[o];
int mid = (l + r) >> ; bool ans = ;
if(L <= mid) ans |= ask(L, R, l, mid, ls[o]);
if(mid < R) ans |= ask(L, R, mid + , r, rs[o]);
return ans;
} inline bool match(int p, int lenth, int f) {
if(!tr[p][f]) return ;
return ask(X + lenth, Y, , n, rt[tr[p][f]]);
} namespace sam {
int tot, len[N << ], fail[N << ], tr[N << ][], last, large[N << ];
int bin[N << ], topo[N << ];
inline void clear() {
for(int i = ; i <= tot; i++) {
memset(tr[i], , sizeof(tr[i]));
large[i] = bin[i] = fail[i] = len[i] = ;
}
tot = last = ;
return;
}
inline void insert(char c) {
//printf("insert : "); putchar(c); printf("\n");
int f = c - 'a', p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
}
inline LL sort() {
for(int i = ; i <= tot; i++) {
bin[len[i]]++;
}
for(int i = ; i <= tot; i++) {
bin[i] += bin[i - ];
}
for(int i = ; i <= tot; i++) {
topo[bin[len[i]]--] = i;
}
LL ans = ;
for(int i = tot; i >= ; i--) {
int x = topo[i];
if(large[x] > len[fail[x]]) {
ans -= std::min(len[x], large[x]) - len[fail[x]];
}
ans += len[x] - len[fail[x]];
large[fail[x]] = std::max(large[fail[x]], large[x]);
}
return ans;
}
} int main() { //printf("%d \n", (sizeof(ls) * 3) / 1048576); freopen("name.in", "r", stdin);
freopen("name.out", "w", stdout); init();
scanf("%s", str);
n = strlen(str);
for(int i = ; i < n; i++) {
insert(str[i], i + );
}
for(int i = ; i <= tot; i++) add(fail[i], i);
DFS_1();
/// build over
int q;
scanf("%d", &q);
for(Time = ; Time <= q; Time++) {
//printf("i = %d \n", Time);
scanf("%s%d%d", ss, &X, &Y);
int m = strlen(ss);
sam::clear();
for(int i = ; i < m; i++) {
sam::insert(ss[i]);
}
/// match
int p1 = , p2 = , lenth = ;
for(int i = ; i < m; i++) {
int ff = ss[i] - 'a';
p2 = sam::tr[p2][ff];
while(p1 && !match(p1, lenth, ff)) {
if(lenth) lenth--;
if(lenth == len[fail[p1]]) p1 = fail[p1];
}
if(!p1) {
p1 = ;
}
else {
p1 = tr[p1][ff];
lenth++;
}
sam::large[p2] = std::max(sam::large[p2], lenth);
//printf("lneth = %d \n", lenth);
}
LL ans = sam::sort();
printf("%lld\n", ans);
}
return ;
}
AC代码
最新文章
- VSALM 动手实验 - 持续集成
- XE8 (RTM) Android SDK 更新安装（转）
- 最近学习了Node,利用Express搭建了个人博客，总结下吧
- zjuoj 3608 Signal Detection
- 用dom操作替代正则表达式
- JAVA并发编程学习笔记之ReentrantLock
- knockoutjs简单使用
- CentOS 7 +Nginx
- js for...in 语句
- jsp登陆页面验证码在火狐浏览器不能刷新问题处理方案
- Scrum Meeting Alpha - 7
- Linux 性能监测：IO
- C语言实现将日期、时间保存到文本文件中
- orcal - 单行函数
- Mybatis PageHelper 简单使用
- 《Mysql ALTER基本操作》
- Horizon Is Easy, Horizon Is Complex
- ASP.NET MVC4优化
- BadUSB测试记录
- Ionic入门十：icon(图标)