首页 > 其他分享 >BZOJ 2555 = P5212 SubString 题解

BZOJ 2555 = P5212 SubString 题解

时间：2024-09-22 21:37:17浏览次数：8  
标签：ch P5212 int 题解 len SubString fa link cur

Statement

给你一个字符串 \(\text{init}\)，要求你支持两个操作：

  1. 在当前字符串的后面插入一个字符串；
  2. 询问字符串 \(s\) 在当前字符串中出现了几次？（作为连续子串）

你必须在线支持这些操作。

Solution

extend 中 link[cur] = q，相当于 link，链加

新建 copy 那里，相当于 link，cut，链加

询问，相当于单点查权值

于是 SAM + LCT 做完了

想一想有没有常数更小的方法

考虑单点加，LCT 维护子树和

考虑 Link、Cut 操作仅仅是改变父亲，可以用 access 实现

于是没有链操作了，没有 Makeroot、Pushdown 了，常数小多了

Code 1

有 down，无 up

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 8e6 + 10;

namespace LCT {
	int fa[N], ch[N][2], rev[N], val[N], add[N];
  #define get(u) (u == ch[fa[u]][1])
  #define nrt(u) (u == ch[fa[u]][0] || u == ch[fa[u]][1])
	void Add(int u, int v) {
		add[u] += v, val[u] += v;
	}
	void swp(int u) {
		rev[u] ^= 1, swap(ch[u][0], ch[u][1]);
	}
	void upd(int u) {
		if (add[u]) Add(ch[u][0], add[u]), Add(ch[u][1], add[u]), add[u] = 0;
		if (rev[u]) swp(ch[u][0]), swp(ch[u][1]), rev[u] = 0;
	}
	void down(int u) {
		if (nrt(u)) down(fa[u]);
		upd(u);
	}
	void rot(int u) {
		int f = fa[u], g = fa[f], k = get(u);
		if (nrt(f)) ch[g][get(f)] = u;
		ch[f][k] = ch[u][!k];
		if (ch[u][!k]) fa[ch[u][!k]] = f;
		ch[u][!k] = f, fa[f] = u, fa[u] = g;
	}
	void splay(int u) {
		for (down(u); nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
	}
	void access(int u) {
		for (int v = 0; u; v = u, u = fa[u]) splay(u), ch[u][1] = v;
	}
	void makert(int u) {
		access(u), splay(u), swp(u);
	}
	void link(int u, int v) {
		makert(u), fa[u] = v;
	}
	void cut(int u, int v) {
		makert(u), access(v), splay(v), ch[v][0] = fa[u] = 0;
	}
	int split(int u, int v) {
		makert(u), access(v), splay(v);
		return v;
	}
  #undef get
  #undef nrt
}

namespace SAM {
	int sz, cur, last, len[N], link[N], nxt[N][2];
	void init() {
		link[0] = -1;
	}
	void extend(int ch) {
		cur = ++sz, len[cur] = len[last] + 1;
		int p = last;
		for (; ~p; p = link[p])
			if (!nxt[p][ch]) nxt[p][ch] = cur;
			else break;
		if (!~p) {
			link[cur] = 0, LCT::link(cur + 1, 1);
		} else {
			int q = nxt[p][ch];
			if (len[p] + 1 == len[q]) {
				link[cur] = q, LCT::link(cur + 1, q + 1);
			} else {
				int copy = ++sz;
				LCT::split(q + 1, q + 1), LCT::split(copy + 1, copy + 1), LCT::Add(copy + 1, LCT::val[q + 1]);
				LCT::cut(q + 1, link[q] + 1);
				LCT::link(copy + 1, link[q] + 1);
				LCT::link(q + 1, copy + 1);
				LCT::link(cur + 1, copy + 1);
				link[copy] = link[q], link[q] = copy, link[cur] = copy, len[copy] = len[p] + 1;
				rep(i, 0, 1) nxt[copy][i] = nxt[q][i];
				for (; ~p; p = link[p])
					if (nxt[p][ch] == q) nxt[p][ch] = copy;
					else break;
			}
		}
		last = cur, LCT::Add(LCT::split(1, cur + 1), 1);
	}
}

void decodeWithMask(string &s, int mask) {
	int len = s.length();
	rep(j, 0, len - 1) swap(s[j], s[mask = (mask * 131 + j) % len]);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int q;
	cin >> q;
	string init;
	cin >> init;
	int initlen = init.length();
	SAM::init();
	rep(i, 0, initlen - 1) SAM::extend(init[i] - 'A');
	int mask = 0;
	while (q--) {
		string type, str;
		cin >> type >> str, decodeWithMask(str, mask);
		int len = str.length();
		if (type == "ADD") {
			rep(i, 0, len - 1) SAM::extend(str[i] - 'A');
		}
		if (type == "QUERY") {
			int pos = 0, res = 0, ok = 1;
			rep(i, 0, len - 1) {
				if (!SAM::nxt[pos][str[i] - 'A']) {
					ok = 0;
					break;
				}
				pos = SAM::nxt[pos][str[i] - 'A'];
			}
			if (ok) {
				LCT::split(1, pos + 1);
				cout << (res = LCT::val[pos + 1]) << '\n';
			} else cout << "0\n";
			mask ^= res;
		}
	}
	return 0;
}

Code 2

有 up，无 down（维护子树信息）

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 8e6 + 10;

namespace LCT {
	int fa[N], ch[N][2], All[N], MyXu[N], val[N];
  #define get(u) (u == ch[fa[u]][1])
  #define nrt(u) (u == ch[fa[u]][0] || u == ch[fa[u]][1])
	void up(int u) {
		All[u] = All[ch[u][0]] + All[ch[u][1]] + val[u] + MyXu[u];
	}
	void rot(int u) {
		int f = fa[u], g = fa[f], k = get(u);
		if (nrt(f)) ch[g][get(f)] = u;
		ch[f][k] = ch[u][!k];
		if (ch[u][!k]) fa[ch[u][!k]] = f;
		ch[u][!k] = f, fa[f] = u, fa[u] = g, up(f), up(u);
	}
	void splay(int u) {
		for (; nrt(u); rot(u)) if (nrt(fa[u])) rot(get(u) == get(fa[u]) ? fa[u] : u);
	}
	void access(int u) {
		for (int v = 0; u; v = u, u = fa[u]) 
			splay(u), MyXu[u] = MyXu[u] - All[v] + All[ch[u][1]], ch[u][1] = v, up(u);
	}
	void Add(int u, int v) {
		access(u), splay(u), All[u] += v, val[u] += v;
	}
	void link(int u, int v) {
		fa[u] = v, MyXu[v] += All[u], access(u);
	}
	void cut(int u, int v) {
		access(u), splay(v), All[v] -= All[u], fa[u] = ch[v][1] = 0;
	}
	int qry(int u) {
		return access(u), splay(u), MyXu[u] + val[u];
	}
  #undef get
  #undef nrt
}

namespace SAM {
	int sz, cur, last, len[N], link[N], nxt[N][2];
	void init() {
		link[0] = -1;
	}
	void extend(int ch) {
		cur = ++sz, len[cur] = len[last] + 1;
		int p = last;
		for (; ~p; p = link[p])
			if (!nxt[p][ch]) nxt[p][ch] = cur;
			else break;
		if (!~p) {
			link[cur] = 0, LCT::link(cur + 1, 1);
		} else {
			int q = nxt[p][ch];
			if (len[p] + 1 == len[q]) {
				link[cur] = q, LCT::link(cur + 1, q + 1);
			} else {
				int copy = ++sz;
				LCT::cut(q + 1, link[q] + 1);
				LCT::link(copy + 1, link[q] + 1);
				LCT::link(q + 1, copy + 1);
				LCT::link(cur + 1, copy + 1);
				link[copy] = link[q], link[q] = copy, link[cur] = copy, len[copy] = len[p] + 1;
				rep(i, 0, 1) nxt[copy][i] = nxt[q][i];
				for (; ~p; p = link[p])
					if (nxt[p][ch] == q) nxt[p][ch] = copy;
					else break;
			}
		}
		last = cur, LCT::Add(cur + 1, 1);
	}
}

void decodeWithMask(string &s, int mask) {
	int len = s.length();
	rep(j, 0, len - 1) swap(s[j], s[mask = (mask * 131 + j) % len]);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int q;
	cin >> q;
	string init;
	cin >> init;
	int initlen = init.length();
	SAM::init();
	rep(i, 0, initlen - 1) SAM::extend(init[i] - 'A');
	int mask = 0;
	while (q--) {
		string type, str;
		cin >> type >> str, decodeWithMask(str, mask);
		int len = str.length();
		if (type == "ADD") {
			rep(i, 0, len - 1) SAM::extend(str[i] - 'A');
		}
		if (type == "QUERY") {
			int pos = 0, res = 0, ok = 1;
			rep(i, 0, len - 1) {
				if (!SAM::nxt[pos][str[i] - 'A']) {
					ok = 0;
					break;
				}
				pos = SAM::nxt[pos][str[i] - 'A'];
			}
			if (ok) {
				cout << (res = LCT::qry(pos + 1)) << '\n';
			} else cout << "0\n";
			mask ^= res;
		}
	}
	return 0;
}

标签：ch,P5212,int,题解,len,SubString,fa,link,cur
From： https://www.cnblogs.com/laijinyi/p/18425928

相关文章

  • 2024 秋季模拟赛题解
    2024秋季模拟赛题解CSP-S模拟赛2024.9.8CSP-S模拟赛28T1签到题。对\(b\)分解质因数后便容易求解。T2考虑枚举\(\gcd(S)\)的取值\(x\)，则\(\operatorname{lcm}(S)=m-x\)。那么同时变形\(\gcd\)和\(\operatorname{lcm}\)变为\(\gcd(S)=1,\operatorname{lcm}......
  • BZOJ 3277 串 题解
    Statement给 \(n\) 个串，问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。Solution1%%注意到\(\text{LCP}\)在后缀排序后一定是连续的一段，包含一个串的区间是连续的先预处理出对于所有左端点\(l\)，最左的\(r\)满足\([l..r]\)中出现了至少\(k\)个......
  • BZOJ 4310 跳蚤 题解
    Statement把\(S\)分成不超过\(k\)段，使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串，check中从右往左贪心地划分，需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<......
  • BZOJ 4545 DQS 的 trie 题解
    Statement维护一棵树，边权\(\in\{\texttta,\textttb,\textttc\}\)，根为\(1\)，定义这棵树的子串为从\(1\)走到所有点构成的字符串的所有后缀，需要支持以下操作：问当前树的本质不同子串数给一个点添加一棵子树问一个串在当前树中作为子串的出现次数Solution直接广义SAM+......
  • 力扣72-编辑距离（Java详细题解）
    题目链接：力扣72-编辑距离前情提要：因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。dp五部曲。1.确定dp数组和i下标的含义。2.确定递推公式。3.dp初始化。4.确定dp的遍历顺序。5.如果没有ac打印dp数组利于debug。每一个dp题目如果都用这五步分析清楚，那么......
  • ABC372 F 题解
    F-TeleportingTakahashi2先把问题转化一下：把环断开成链，复制\((K+1)\)层，每走一步就相当于前进一层：可以想到一个简单的dp：设\(f(i,j)\)表示走到第\(i\)层第\(j\)个位置的方案数。初始化：\(f(0,1)=1\)，其它均为\(0\)，表示Takahashi从第\(0\)层的\(1\)位置......
  • 【题解】「Public NOIP Round #2」找零
    【题解】「PublicNOIPRound#2」找零[官解](PublicNOIPRound#2题解-博客-Qingyu的博客(pjudge.ac))Tag：背包、dp凸优化决策点单调触碰到知识点盲区了，所以来写几笔。首先，由于我们只关心最终状态下\(1\)的最多个数，其实有用的面值只有\(5,1\)（其她的可以当成若干......
  • U389139 至少有一位重复的数字-题解
    题目传送门一、举例说明以\(654923\)为例要判断在\([0,654923]\)区间至少有一位重复的数值的数，可以考虑其补集，即\(\color{red}所有位数均不重复的数\)，用\(N\)减去补集即为结果。首先可以将其分为两种情况。情况一，位数小于\(6\)位。所有位数均不重复的有\(9\time......
  • 【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
    【洛谷】P10417[蓝桥杯2023国A]第K小的和的题解题目传送门题解CSP-S1补全程序，致敬全A的答案，和神奇的预言家。写一下这篇的题解说不定能加CSP2024的RP代码#include<bits/stdc++.h>#definelowbit(x)x&(-x)#defineendl"\n"usingnamespacestd......
  • 【题解】【枚举】—— [NOIP2014 普及组] 比例简化
    【题解】【枚举】——[NOIP2014普及组]比例简化[NOIP2014普及组]比例简化题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.思路解析2.AC代码[NOIP2014普及组]比例简化通往洛谷的传送门题目背景NOIP2014普及组T2题目描述在社交媒体......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99