题意
Sol
一眼splay + 二分hash,不过区间splay怎么写来着呀
试着写了两个小时发现死活不对
看了一下yyb的代码发现自己根本就不会splay。。。。
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN = 1e6 + 10;
const ull base = 27;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
char s[MAXN];
int root, tot, ch[MAXN][2], fa[MAXN], siz[MAXN];
ull ha[MAXN], val[MAXN], po[MAXN];
bool rev[MAXN];
int ident(int x) {
return ch[fa[x]][1] == x;
}
void connect(int x, int f, int id) {
fa[x] = f; ch[f][id] = x;
}
void update(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
ha[x] = ha[ch[x][0]] + val[x] * po[siz[ch[x][0]]] + po[siz[ch[x][0]] + 1] * ha[ch[x][1]];
}
void rotate(int x) {
int y = fa[x], R = fa[y], Yson = ident(x), Rson = ident(y);
int B = ch[x][Yson ^ 1];
connect(x, R, Rson); connect(B, y, Yson); connect(y, x, Yson ^ 1);
update(y); update(x);
}
void splay(int x, int to) {
//to = fa[to];
while(fa[x] != to) {
if(fa[fa[x]] == to) rotate(x);
else if(ident(x) == ident(fa[x])) rotate(fa[x]), rotate(x);
else rotate(x), rotate(x);
}
if(!to) root = x; update(x);
}
int find(int k) {
int x = root;
while(1) {
if(siz[ch[x][0]] + 1 == k) return x;
if(siz[ch[x][0]] + 1 < k) k -= siz[ch[x][0]] + 1, x = ch[x][1];//tag
else x = ch[x][0];
}
}
ull gethash(int l, int len) {
int x = find(l), y = find(l + len + 1);
splay(x, 0); splay(y, x);
return ha[ch[y][0]];
}
int LCP(int y, int x) {
int l = 0, r = tot - max(x, y) - 1, ans = 0;
while(l <= r) {
int mid = l + r >> 1;
if(gethash(x, mid) == gethash(y, mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
return ans;
}
void insert(int x, int v) {
int l = find(x + 1), r = find(x + 2);
splay(l, 0); splay(r, l);
val[++tot] = v; fa[tot] = r; ch[r][0] = tot; splay(tot, 0);
}
void change(int x, int v) {
int l = find(x), r = find(x + 2);
splay(l, 0); splay(r, l);
val[ch[r][0]] = v; update(ch[r][0]);
update(r); update(l);
}
int main() {
// freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);
po[0] = 1;
for(int i = 1; i <= (int)1e5; i++) po[i] = base * po[i - 1];
scanf("%s", s + 1); N = strlen(s + 1);
ch[1][1] = 2; fa[2] = 1; tot = 2; root = 1; update(2); update(1);
for(int i = 1; i <= N; i++)
insert(i - 1, s[i]);
int M = read();
while(M--) {
char opt[3]; scanf("%s", opt);
if(opt[0] == 'Q') {int x = read(), y = read(); printf("%d\n", LCP(x, y));}
else if(opt[0] == 'R') {
int x = read(); scanf("%s", opt + 1);
change(x, opt[1]);
} else {
int x = read(); scanf("%s", opt + 1);
insert(x, opt[1]);
}
}
return 0;
}
/*
*/
BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)的更多相关文章
-
BZOJ 1014: [JSOI2008]火星人prefix [splay 二分+hash] 【未完】
1014: [JSOI2008]火星人prefix Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 6243 Solved: 2007[Submit] ...
-
【BZOJ-1014】火星人prefix Splay + 二分 + Hash
1014: [JSOI2008]火星人prefix Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 5852 Solved: 1871[Submit] ...
-
BZOJ1014[JSOI2008]火星人prefix(splay维护hash)
Description 火星人最近研究了一种操作:求一个字串两个后缀的公共前缀.比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 ...
-
[BZOJ1014] [JSOI2008] 火星人prefix (splay &; 二分答案)
Description 火星人最近研究了一种操作:求一个字串两个后缀的公共前缀.比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 ...
-
BZOJ 1014: [JSOI2008]火星人prefix Splay+二分
1014: [JSOI2008]火星人prefix 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=1014 Description 火星人 ...
-
bzoj1014: [JSOI2008]火星人prefix splay+hash+二分
Description 火星人最近研究了一种操作:求一个字串两个后缀的公共前缀.比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 ...
-
BZOJ 1014 [JSOI2008]火星人prefix (splay+二分答案+字符串hash)
题目大意:维护一个字符串,支持插入字符和替换字符的操作,以及查询该字符串两个后缀的最长公共前缀长度 乍一看以为是后缀数组,然而并没有可持久化后缀数组(雾) 看题解才知道这是一道splay题,首先要对s ...
-
bzoj1014: [JSOI2008]火星人prefix splay+hash
我写的代码好像自古以来就是bzoj不友好型的 本地跑的比std快,但是交上去巧妙被卡 答案...应该是对的,拍了好久了 #include <bits/stdc++.h> #define M ...
-
[bzoj1014](JSOI2008)火星人 prefix (Splay维护哈希)
Description 火星人最近研究了一种操作:求一个字串两个后缀的公共前缀. 比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 ...
随机推荐
-
用ProGet搭建内部的NuGet服务器
最近团队内部用的一个很简陋的NuGet服务器出问题了,nuget push发包,客户端显示发布成功,服务器上就是没有.懶得再去排查这个问题,早就想换掉这个过于简陋的NuGet服务器,借此机会直接弃旧迎 ...
-
推公式 HDU 2552
T 给你2个值 求另外一个 需要推一下 tan(a+b)=(tan(a)+tan(b))/(1-tan(a)*tan(b)); 等式左右取tan tan(atan(a))=a 1/s=tan(...) ...
-
高性能javascript(记录三)
DOM(文档对象模型)是一个独立的语言,用于操作XML和HTML文档的程序接口(API).在游览器中,主要用来与HTML文档打交道,同样也用在Web程序中获取XML文档,并使用DOM API用来访问文 ...
-
VES Hand Book Contents
3...ABOUT THE VES4...Foreword 6...Chapter 1......Introduction6......Visual Effects and Special Effec ...
-
使用SQL如何把用逗号等字符隔开的字符串转换成列表(转)
如何把用逗号等字符隔开的字符串转换成列表,下面依逗号分隔符为例: 比如有一个字符串,其值为:香港,张家港,北京,上海用SQL把这个字符串转换成列表的方法是: 1.方法一 WITH A AS (SELE ...
-
android中xmlns:tools属性详解
今天读到一篇总结的非常棒的文章,写的逻辑很清晰也很实用,很少见到如此棒的文章了.就原文转发过来,我把格式给整理了一下,分享给园子里的各位朋友!好久没写博客了,就为2015年的11月留份纪念吧.希望对你 ...
-
OkHttp+Stetho+Chrome调试android网络部分
如果要达到上面的效果,你需要改造你的网络请求模块,使用Chrome浏览器和android程序之间的中间件来连接,这就是本篇要介绍的主题:OkHttp+Stetho+Chrome进行网络调试. okht ...
-
shell 脚本执行日志通用模块
目标 实现记录SHELL执行的開始时间,结束时间.执行状态,错误信息等,以函数封装日志记录的方式,脚本调用函数 源代码 通用函数脚本program_log_new.sh function init_l ...
-
poj1007 qsort快排
这道题比较简单,但通过这个题我学会了使用c++内置的qsort函数用法,收获还是很大的! 首先简要介绍一下qsort函数. 1.它是快速排序,所以就是不稳定的.(不稳定意思就是张三.李四成绩都是90, ...
-
CLR的组成和运转
CLR的组成和运转 clr基本 CLR(Common Language Runtime)是一个可由多种编程语言使用的“运行时”.(例如:c#,c++/cli,vb,f#,ironpython,iron ...