bzoj 1014[JSOI2008]火星人prefix - 二分 + hash + splay

 ?1 #include <iostream> ?2 #include <cstdio> ?3 #include <cstring> ?4 #include <algorithm> ?5 #define LL long long ?6 using namespace std; ?7 ??8 const int MAXN = 1e5 + 10, MAXM = 2e5 + 10; ?9 int N, M; 10 int root; 11 int ans = 0; 12 int tot = 0; 13 char opr[30], d[30]; 14 unsigned long long pow[MAXN]; 15 struct spl { 16 ????int ch[2]; 17 ????int fa; 18 ????unsigned LL c; 19 ????int size; 20 ????unsigned LL hash; 21 ????void init() 22 ????{ 23 ????????ch[0] = ch[1] = 0; 24 ????????size = 0; 25 ????????hash = 0; 26 ????????c = 0; 27 ????????fa = 0; 28 ????} 29 } t[MAXN * 50]; 30 inline LL read() 31 { 32 ????LL x = 0, w = 1; char ch = 0; 33 ????while(ch < ‘0‘ || ch > ‘9‘) { 34 ????????if(ch == ‘-‘) { 35 ????????????w = -1; 36 ????????} 37 ????????ch = getchar(); 38 ????} ????39 ????while(ch >= ‘0‘ && ch <= ‘9‘) { 40 ????????x = x * 10 + ch - ‘0‘; 41 ????????ch = getchar(); 42 ????} 43 ????return x * w; 44 } 45 ?46 char s[MAXN]; 47 ?48 void pushup(int k) 49 { 50 ????t[k].size = t[t[k].ch[0]].size + t[t[k].ch[1]].size + 1; 51 ????t[k].hash = t[t[k].ch[0]].hash * pow[t[t[k].ch[1]].size + 1] + t[k].c * pow[t[t[k].ch[1]].size] + t[t[k].ch[1]].hash; 52 } 53 ?54 void rotate(int x, int &k) 55 { 56 ????int y = t[x].fa, z = t[y].fa; 57 ????int l = 0, r; 58 ????if(y == k) { 59 ????????k = x; 60 ????} 61 ????if(t[y].ch[0] == x) { 62 ????????l = 0; 63 ????} else { 64 ????????l = 1; 65 ????} 66 ????r = l ^ 1; 67 ????if(z) { 68 ????????if(t[z].ch[0] == y) { 69 ????????????t[z].ch[0] = x; 70 ????????} else { 71 ????????????t[z].ch[1] = x; 72 ????????} 73 ????} 74 ????int tt = t[x].ch[r]; 75 ????t[x].ch[r] = y, t[x].fa = z, t[tt].fa = y; 76 ????t[y].ch[l] = tt, t[y].fa = x; 77 ????pushup(y), pushup(x); 78 } 79 ?80 void splay(int x, int &k) 81 { 82 ????while(x != k) { 83 ????????int y = t[x].fa, z = t[y].fa; 84 ????????if(y != k) { 85 ????????????if(t[z].ch[0] == y ^ t[y].ch[0] == x) { 86 ????????????????rotate(x, k); 87 ????????????} else { 88 ????????????????rotate(y, k); 89 ????????????} 90 ????????} 91 ????????rotate(x, k); 92 ????} 93 } 94 ?95 unsigned LL judge(int st, int len) 96 { 97 ????int k = root; 98 ????int loc = st; 99 ????while(loc != t[t[k].ch[0]].size + 1) {100 ????????if(loc > t[t[k].ch[0]].size) {101 ????????????loc = loc - t[t[k].ch[0]].size - 1;102 ????????????k = t[k].ch[1];103 ????????} else {104 ????????????k = t[k].ch[0]; ???105 ????????}106 ????}107 ????splay(k, root);108 ????k = root;109 ????loc = st + len + 1;110 ????while(loc != t[t[k].ch[0]].size + 1) {111 ????????if(loc > t[t[k].ch[0]].size) {112 ????????????loc = loc - t[t[k].ch[0]].size - 1;113 ????????????k = t[k].ch[1];114 ????????} else {115 ????????????k = t[k].ch[0]; ???116 ????????}117 ????}118 ????splay(k, t[root].ch[1]);119 ????return t[t[t[root].ch[1]].ch[0]].hash;120 }121 122 void query(int x, int y)123 {124 ????int l = 0, r = tot - max(x, y) - 1;125 ????while(l <= r) {126 ????????int mid = (l + r) >> 1;127 ????// ???cout<<mid<<endl;128 ????????if(judge(x, mid) == judge(y, mid)) {129 ????????????ans = mid;130 ????????????l = mid + 1;131 ????????} else {132 ????????????r = mid - 1;133 ????????}134 ????}135 ????printf("%d\n", ans);136 }137 138 void update(int loc, char d)139 {140 ????int k = root;141 ????while(loc != t[t[k].ch[0]].size + 1) {142 ????????if(loc > t[t[k].ch[0]].size) {143 ????????????loc = loc - t[t[k].ch[0]].size - 1;144 ????????????k = t[k].ch[1];145 ????????} else {146 ????????????k = t[k].ch[0]; ???147 ????????}148 ????}149 ????t[k].c = d - ‘a‘;150 // ???pushup(k);151 ????splay(k, root);152 }153 154 void insert(int x, char d)155 {156 ????int k = root;157 ????int loc = x;158 ????while(loc != t[t[k].ch[0]].size + 1) {159 ????????if(loc > t[t[k].ch[0]].size) {160 ????????????loc = loc - t[t[k].ch[0]].size - 1;161 ????????????k = t[k].ch[1];162 ????????} else {163 ????????????k = t[k].ch[0]; ???164 ????????}165 ????}166 ????splay(k, root);167 ????loc = x + 1;168 ????k = root;169 ????while(loc != t[t[k].ch[0]].size + 1) {170 ????????if(loc > t[t[k].ch[0]].size) {171 ????????????loc = loc - t[t[k].ch[0]].size - 1;172 ????????????k = t[k].ch[1];173 ????????} else {174 ????????????k = t[k].ch[0]; ???175 ????????}176 ????}177 ????splay(k, t[root].ch[1]);178 ????t[++tot].init();179 ????t[t[root].ch[1]].ch[0] = tot;180 ????t[tot].fa = t[root].ch[1];181 ????t[tot].size = 1;182 ????t[tot].hash = t[tot].c = d - ‘a‘;183 ????pushup(t[root].ch[1]);184 ????pushup(root);185 }186 187 void build(int l, int r, int &k, int last)188 {189 // ???cout<<l<<" "<<r<<endl;190 ????if(l > r) {191 ????????return;192 ????}193 ????k = ++tot;194 ????if(l == r) {195 ????????t[k].init();196 ????????t[k].size = 1;197 ????????t[k].c = t[k].hash = s[l] - ‘a‘;198 ????????t[k].fa = last;199 ????????return;200 ????}201 ????int mid = (l + r) >> 1;202 ????t[k].init();203 ????t[k].size = 1;204 ????t[k].c = s[mid] - ‘a‘;205 ????t[k].fa = last;206 ????build(l, mid - 1, t[k].ch[0], k);207 ????build(mid + 1, r, t[k].ch[1], k);208 ????pushup(k); 209 }210 211 void init()212 {213 ????pow[0] = 1;214 ????for(int i = 1; i <= 1e5; i++) {215 ????????pow[i] = pow[i - 1] * 27;216 ????}217 }218 219 void print(int k)220 {221 // ???cout<<t[k].ch[0]<<" "<<t[k].ch[1]<<" "<<char(t[k].c ?+ ‘a‘)<<" "<<t[k].size<<" "<<t[k].hash<<endl;222 223 ????if(t[k].ch[0]) {224 ????????print(t[k].ch[0]);225 ????}226 ????//cout<<char(t[k].c + ‘a‘);227 ????if(t[k].ch[1]) {228 ????????print(t[k].ch[1]);229 ????}230 }231 232 int main()233 {234 ????init();235 /* ???for(int i = 1; i <= 10; i++) {236 ????????cout<<pow[i]<<" ";237 ????}238 ????cout<<endl;*/239 ????t[0].init();240 ????scanf("%s", s + 1);241 ????N = strlen(s + 1);242 ????N++;243 ????s[0] = ‘A‘;244 ????s[N] = ‘A‘;245 ????build(0, N, root, 0);246 // ???print(root);247 ????M = read();248 ????while(M--) {249 ????????scanf("%s", opr);250 ????????if(opr[0] == ‘Q‘) {251 ????????????int x = read(), y = read();252 ????????????query(x, y);253 ????????} else if(opr[0] == ‘R‘) {254 ????????????int ???x = read();255 ????????????scanf("%s", d);256 ????????????update(x + 1, d[0]);257 ????????} else {258 ????????????int x = read();259 ????????????scanf("%s", d);260 ????????????insert(x + 1, d[0]);261 ????????}262 ????}263 ????return 0;264 }265 266 /*267 madamimadam268 7269 Q 1 7270 Q 4 8271 Q 10 11272 R 3 a273 Q 1 7274 I 10 a275 Q 2 11276 */