Description

火星人最近研究了一種操作：求一個字串兩個后綴的公共前綴。比方說，有這樣一個字符串：madamimadam，我們將這個字符串的各個字符予以標號：序號： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 現在，火星人定義了一個函數LCQ(x, y)，表示：該字符串中第x個字符開始的字串，與該字符串中第y個字符開始的字串，兩個字串的公共前綴的長度。比方說，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函數的過程中，火星人發現了這樣的一個關聯：如果把該字符串的所有后綴排好序，就可以很快地求出LCQ函數的值；同樣，如果求出了LCQ函數的值，也可以很快地將該字符串的后綴排好序。 盡管火星人聰明地找到了求取LCQ函數的快速算法，但不甘心認輸的地球人又給火星人出了個難題：在求取LCQ函數的同時，還可以改變字符串本身。具體地說，可以更改字符串中某一個字符的值，也可以在字符串中的某一個位置插入一個字符。地球人想考驗一下，在如此復雜的問題中，火星人是否還能夠做到很快地求取LCQ函數的值。

Input

第一行給出初始的字符串。第二行是一個非負整數M，表示操作的個數。接下來的M行，每行描述一個操作。操作有3種，如下所示： 1、 詢問。語法：Q x y，x, y均為正整數。功能：計算LCQ(x, y) 限制：1 <= x, y <= 當前字符串長度。 2、 修改。語法：R x d，x是正整數，d是字符。功能：將字符串中第x個數修改為字符d。限制：x不超過當前字符串長度。 3、 插入：語法：I x d，x是非負整數，d是字符。功能：在字符串第x個字符之后插入字符d，如果x = 0，則在字符串開頭插入。限制：x不超過當前字符串長度。

Output

對于輸入文件中每一個詢問操作，你都應該輸出對應的答案。一個答案一行。

Sample Input

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

HINT

?

數據規模：

對于100%的數據，滿足：

1、 所有字符串自始至終都只有小寫字母構成。

2、 M <= 150,000

3、 字符串長度L自始至終都滿足L <= 100,000

4、 詢問操作的個數不超過10,000個。

對于第1，2個數據，字符串長度自始至終都不超過1,000

對于第3，4，5個數據，沒有插入操作。

?

?

Source

?

r_64大神犇告訴我splay+二分+哈希，因此我就寫了一發，復雜度O(nlogn^2)。 代碼： 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 #define rhl 37 8 #define maxl 100010 9 #define maxm 150010 10 char s[maxl]; int len; 11 unsigned long long mi[maxl+maxm]; 12 13 struct SPLAY 14 { 15 int ch[maxl+maxm][2],fa[maxl+maxm],size[maxl+maxm],key[maxl+maxm],cnt,root; 16 unsigned long long hash[maxl+maxm]; 17 18 inline void updata(int x) 19 { 20 size[x] = size[ch[x][0]] + size[ch[x][1]] + 1; 21 hash[x] = hash[ch[x][0]] * mi[size[ch[x][1]]+1] + mi[size[ch[x][1]]] * (key[x]) + hash[ch[x][1]]; 22 } 23 24 inline void rotate(int x) 25 { 26 int y = fa[x],z = fa[y],l,r; 27 if (ch[y][0] == x) l = 0; else l = 1; r = l ^ 1; 28 if (z != 0) 29 { 30 if (ch[z][0] == y) ch[z][0] = x; else ch[z][1] = x; 31 } 32 fa[x] = z; fa[y] = x; fa[ch[x][r]] = y; 33 ch[y][l] = ch[x][r]; ch[x][r] = y; 34 updata(y); updata(x); 35 fa[0] = 0; ch[0][0] = ch[0][1] = 0; 36 } 37 38 inline void splay(int x,int aim) 39 { 40 int t = fa[aim]; 41 while (fa[x] != t) 42 { 43 int y = fa[x],z = fa[y]; 44 if (fa[y] != t) 45 { 46 if ((ch[y][0] == x)^(ch[z][0] == y)) rotate(x); 47 else rotate(y); 48 } 49 rotate(x); 50 } 51 if (aim == root) root = x; 52 } 53 54 inline int find(int rank,int have,int now) 55 { 56 if (size[ch[now][0]]+have+1==rank) return now; 57 if (size[ch[now][0]]+have+1 > rank) return find(rank,have,ch[now][0]); 58 else return find(rank,have+size[ch[now][0]]+1,ch[now][1]); 59 } 60 61 inline void init(int l,int r,int f) 62 { 63 int p; cnt = 0; root = 1; 64 build(l,r,f); 65 p = find(len,0,root); 66 splay(p,root); 67 fa[++cnt] = p; 68 ch[p][1] = cnt; 69 key[cnt] = 0; 70 size[cnt] = 1; 71 updata(p); 72 p = find(1,0,root); 73 splay(p,root); 74 fa[++cnt] = p; 75 ch[p][0] = cnt; 76 key[cnt] = 0; 77 size[cnt] = 1; 78 updata(p); 79 } 80 81 inline void build(int l,int r,int f) 82 { 83 fa[++cnt] = f; 84 if (l == r) 85 { 86 key[cnt] = s[l-1] - 'a' + 1; 87 hash[cnt] = key[cnt]; 88 size[cnt] = 1; 89 return; 90 } 91 int mid = (l+r)>>1,now = cnt; 92 key[now] = s[mid-1] - 'a' + 1; 93 if (mid > l) 94 { 95 ch[now][0] = cnt + 1; 96 build(l,mid - 1,now); 97 } 98 if (mid < r) 99 { 100 ch[now][1] = cnt+1; 101 build(mid+1,r,now); 102 } 103 updata(now); 104 } 105 106 inline void change(int a,char b) 107 { 108 int p = find(a+1,0,root); 109 splay(p,root); 110 key[p] = b-'a'+1; 111 updata(p); 112 } 113 114 inline void insert(int a,char b) 115 { 116 int p = find(a+1,0,root),q = find(a+2,0,root); 117 splay(p,root); 118 splay(q,ch[p][1]); 119 fa[++cnt] = q; 120 ch[q][0] = cnt; key[cnt] = b-'a'+1; 121 updata(cnt); 122 updata(q); 123 updata(p); 124 } 125 126 inline unsigned long long calc(int a,int b) 127 { 128 int p = find(a,0,root),q = find(b+2,0,root); 129 splay(p,root); 130 splay(q,ch[p][1]); 131 return hash[ch[q][0]]; 132 } 133 }tree; 134 135 inline int ask(int a,int b) 136 { 137 int l = 1,r = min(len-a+1,len-b+1),mid; 138 while (l <= r) 139 { 140 mid = (l + r) >> 1; 141 unsigned long long h1 = tree.calc(a,a+mid-1),h2 = tree.calc(b,b+mid-1); 142 if (h1 == h2) 143 l = mid+1; 144 else r = mid - 1; 145 } 146 return r; 147 } 148 149 inline void ready() 150 { 151 mi[0] = 1; 152 for (int i = 1;i < maxl+maxm;++i) 153 mi[i] = rhl*mi[i-1]; 154 } 155 156 inline int read() 157 { 158 int x=0,f=1;char ch=getchar(); 159 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 160 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 161 return x*f; 162 } 163 164 int main() 165 { 166 freopen("1014.in","r",stdin); 167 freopen("1014.out","w",stdout); 168 scanf("%s",s); len = strlen(s); 169 ready(); 170 tree.init(1,len,0); 171 int T = read(); char opt; 172 while (T--) 173 { 174 scanf("%c",&opt); 175 if (opt == 'Q') 176 { 177 int a = read(),b = read(); 178 printf("%d\n",ask(a,b)); 179 } 180 else if (opt == 'R') 181 { 182 int a = read(); char b; scanf("%c\n",&b); 183 tree.change(a,b); 184 } 185 else 186 { 187 int a = read(); char b; scanf("%c\n",&b); 188 tree.insert(a,b); ++len; 189 } 190 } 191 fclose(stdin); fclose(stdout); 192 return 0; 193 } View Code

?

轉載于:https://www.cnblogs.com/mmlz/p/4227380.html

總結

以上是生活随笔為你收集整理的BZOJ 1014 火星人prefix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。