[bzoj1014](JSOI2008)火星人 prefix (Splay维护哈希)

  1 /**************************************************************
  2     Problem: 1014
  3     User: AsmDef
  4     Language: C++
  5     Result: Accepted
  6     Time:8932 ms
  7     Memory:7664 kb
  8 ****************************************************************/
  9  
 10 #include <cctype>
 11 #include <cstdio>
 12 #include <cmath>
 13 #include <iostream>
 14 #include <ctime>
 15 #include <cstdlib>
 16 using namespace std;
 17 template<typename T>inline void getd(T &x){
 18     char c = getchar();
 19     bool minus = 0;
 20     while(!isdigit(c) && c != ‘-‘)c = getchar();
 21     if(c == ‘-‘)minus = 1, c = getchar();
 22     x = c - ‘0‘;
 23     while(isdigit(c = getchar()))x = x * 10 - ‘0‘ + c;
 24     if(minus)x = -x;
 25 }
 26 /*========================================================*/
 27 typedef unsigned long long ull;
 28 const int maxn = 100005;
 29 const ull p1 = 3127, p2 = 49999, p3 = 2147483647;
 30 char tmp[maxn];
 31 ull pow1[maxn], pow2[maxn], pow3[maxn];
 32 int M;
 33 struct Splay{
 34     int size, val;
 35     ull h1, h2, h3;
 36     Splay* init(int);
 37     Splay *son[2];
 38     int cmp(int k){
 39         if(k <= son[0]->size)return 0;
 40         if(k - son[0]->size == 1)return -1;
 41         return 1;
 42     }
 43     void update(){
 44         size = son[0]->size + son[1]->size + 1;
 45         h1 = son[0]->h1 + pow1[son[0]->size]*(p1 * son[1]->h1 + val);
 46         h2 = son[0]->h2 + pow2[son[0]->size]*(p2 * son[1]->h2 + val);
 47         h3 = son[0]->h3 + pow3[son[0]->size]*(p3 * son[1]->h3 + val);
 48     }
 49 }Nil, *Root, Pool[maxn];
 50 int iter = 0;
 51 Splay* Splay::init(int v){
 52     val = h1 = h2 = h3 = v;
 53     size = 1;
 54     son[0] = son[1] = &Nil;
 55     return this;
 56 }
 57 inline void rot(Splay* &o, bool lr){
 58     Splay *t = o->son[lr];o->son[lr] = t->son[lr^1];t->son[lr^1] = o;o->update();o = t;o->update();
 59 }
 60 inline void find(Splay* &o, int k){
 61     int c = o->cmp(k);
 62     if(c == -1)return;
 63     if(c)k -= o->son[0]->size + 1;
 64     int c2 = o->son[c]->cmp(k), k2 = k;
 65     if(~c2){
 66         if(c2)k2 -= o->son[c]->son[0]->size + 1;
 67         find(o->son[c]->son[c2], k2);
 68         if(c == c2)rot(o, c);
 69         else rot(o->son[c], c2);
 70     }
 71     rot(o, c);
 72 }
 73 inline Splay *newT(char *str, int len){
 74     if(len == 1){return Pool[iter++].init(*str - ‘a‘);}
 75     int mid = len >> 1;
 76     Splay *t = Pool[iter++].init(str[mid] - ‘a‘);
 77     t->son[0] = newT(str, mid);
 78     if(len - mid > 1)t->son[1] = newT(str + mid + 1, len - mid - 1);
 79     t->update();
 80     return t;
 81 }
 82 inline void init(){
 83     Nil.h1 = Nil.h2 = Nil.h3 = Nil.val = Nil.size = 0;
 84     int len = 1, i;
 85     while(!isalpha(*tmp = getchar()));
 86     while(isalpha(tmp[len] = getchar()))++len;
 87     getd(M);
 88     const int m = min(M + len, maxn - 1);
 89     *pow1 = *pow2 = *pow3 = 1;
 90     for(i = 1;i <= m;++i)
 91         pow1[i] = pow1[i-1]*p1, pow2[i] = pow2[i-1]*p2, pow3[i] = pow3[i-1]*p3;
 92     Root = newT(tmp, len);
 93 }
 94 inline bool check(int x, int y, int len){
 95     Splay *t;
 96     ull h11, h12, h13, h21, h22, h23;
 97     if(x == 1){
 98         find(Root, len + 1);
 99         t = Root->son[0];
100     }
101     else{
102         find(Root, x - 1);
103         find(Root->son[1], len + 1);
104         t = Root->son[1]->son[0];
105     }
106     h11 = t->h1, h12 = t->h2, h13 = t->h3;
107      
108     find(Root, y - 1);
109     if(len == Root->son[1]->size)t = Root->son[1];
110     else{
111         find(Root->son[1], len + 1);
112         t = Root->son[1]->son[0];
113     }
114     h21 = t->h1, h22 = t->h2, h23 = t->h3;
115     if((h11 != h21) || (h12 != h22) || (h13 != h23))return 0;
116     return 1;
117 }
118 inline void Query(){
119     int l = 1, r, x, y, mid;
120     getd(x), getd(y);
121     if(x > y)x ^= y ^= x ^= y;
122     r = Root->size - y + 1;
123     if(x == y){
124         printf("%d", r);
125         if(M)putchar(‘\n‘);
126         return;
127     }
128     while(l <= r){
129         mid = (l + r) >> 1;
130         if(check(x, y, mid))l = mid + 1;
131         else r = mid - 1;
132     }
133     printf("%d", r);
134     if(M)putchar(‘\n‘);
135 }
136 inline void Change(){
137     int x, d;
138     getd(x);while(!isalpha(d = getchar()));d -= ‘a‘;
139     find(Root, x);
140     Root->val = d;
141     Root->update();
142 }
143 inline void Insert(){
144     int x, d;
145     getd(x);while(!isalpha(d = getchar()));
146     Splay *t = Pool[iter++].init(d - ‘a‘);
147     if(!x){
148         t->son[1] = Root;
149         Root = t;
150         Root->update();
151         return;
152     }
153     find(Root, x);
154     t->son[1] = Root->son[1];Root->son[1] = t;
155     t->update(); Root->update();
156 }
157 int main(){
158     #if defined DEBUG
159     freopen("test", "r", stdin);
160     freopen("out.txt", "w", stdout);
161     #else
162     //freopen("bzoj_1014.in", "r", stdin);
163     //freopen("bzoj_1014.out", "w", stdout);
164     #endif
165     int opt;
166     init();
167     while(M--){
168         while(!isalpha(opt = getchar()));
169         if(opt == ‘Q‘){
170             Query();
171         }
172         else if(opt == ‘R‘)Change();
173         else Insert();
174     }
175     #if defined DEBUG
176     //cout << endl<< (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
177     #endif
178     return 0;
179 }
180 ?

  1 /**************************************************************
  2     Problem: 1014
  3     User: AsmDef
  4     Language: C++
  5     Result: Accepted
  6     Time:4528 ms
  7     Memory:4520 kb
  8 ****************************************************************/
  9  
 10 #include <cctype>
 11 #include <cstdio>
 12 #include <iostream>
 13 #include <ctime>
 14 #include <cstdlib>
 15 using namespace std;
 16 template<typename T>inline void getd(T &x){
 17     char c = getchar();
 18     bool minus = 0;
 19     while(!isdigit(c) && c != ‘-‘)c = getchar();
 20     if(c == ‘-‘)minus = 1, c = getchar();
 21     x = c - ‘0‘;
 22     while(isdigit(c = getchar()))x = x * 10 - ‘0‘ + c;
 23     if(minus)x = -x;
 24 }
 25 /*========================================================*/
 26 typedef unsigned long long ull;
 27 const int maxn = 100005;
 28 const ull p3 = 3127, p1 = 49999, p2 = 2147483647;
 29 char tmp[maxn];
 30 ull pow1[maxn];
 31 int M;
 32 struct Splay{
 33     int size, val;
 34     ull h1;
 35     Splay* init(int);
 36     Splay *son[2];
 37     int cmp(int k){
 38         if(k <= son[0]->size)return 0;
 39         if(k - son[0]->size == 1)return -1;
 40         return 1;
 41     }
 42     void update(){
 43         size = son[0]->size + son[1]->size + 1;
 44         h1 = son[0]->h1 + pow1[son[0]->size]*(p1 * son[1]->h1 + val);
 45     }
 46 }Nil, *Root, Pool[maxn];
 47 int iter = 0;
 48 Splay* Splay::init(int v){
 49     val = h1 = v;
 50     size = 1;
 51     son[0] = son[1] = &Nil;
 52     return this;
 53 }
 54 inline void rot(Splay* &o, bool lr){
 55     Splay *t = o->son[lr];o->son[lr] = t->son[lr^1];t->son[lr^1] = o;o->update();o = t;o->update();
 56 }
 57 inline void find(Splay* &o, int k){
 58     int c = o->cmp(k);
 59     if(c == -1)return;
 60     if(c)k -= o->son[0]->size + 1;
 61     int c2 = o->son[c]->cmp(k), k2 = k;
 62     if(~c2){
 63         if(c2)k2 -= o->son[c]->son[0]->size + 1;
 64         find(o->son[c]->son[c2], k2);
 65         if(c == c2)rot(o, c);
 66         else rot(o->son[c], c2);
 67     }
 68     rot(o, c);
 69 }
 70 inline Splay *newT(char *str, int len){
 71     if(len == 1){return Pool[iter++].init(*str - ‘a‘);}
 72     int mid = len >> 1;
 73     Splay *t = Pool[iter++].init(str[mid] - ‘a‘);
 74     t->son[0] = newT(str, mid);
 75     if(len - mid > 1)t->son[1] = newT(str + mid + 1, len - mid - 1);
 76     t->update();
 77     return t;
 78 }
 79 inline void init(){
 80     Nil.h1 = Nil.val = Nil.size = 0;
 81     int len = 1, i;
 82     while(!isalpha(*tmp = getchar()));
 83     while(isalpha(tmp[len] = getchar()))++len;
 84     getd(M);
 85     const int m = min(M + len, maxn - 1);
 86     *pow1 = 1;
 87     for(i = 1;i <= m;++i)
 88         pow1[i] = pow1[i-1]*p1;
 89     Root = newT(tmp, len);
 90 }
 91 inline bool check(int x, int y, int len){
 92     Splay *t;
 93     ull h11, h21;
 94     if(x == 1){
 95         find(Root, len + 1);
 96         t = Root->son[0];
 97     }
 98     else{
 99         find(Root, x - 1);
100         find(Root->son[1], len + 1);
101         t = Root->son[1]->son[0];
102     }
103     h11 = t->h1;
104      
105     find(Root, y - 1);
106     if(len == Root->son[1]->size)t = Root->son[1];
107     else{
108         find(Root->son[1], len + 1);
109         t = Root->son[1]->son[0];
110     }
111     h21 = t->h1;
112     if(h11 != h21)return 0;
113     return 1;
114 }
115 inline void Query(){
116     int l = 1, r, x, y, mid;
117     getd(x), getd(y);
118     if(x > y)x ^= y ^= x ^= y;
119     r = Root->size - y + 1;
120     if(x == y){
121         printf("%d", r);
122         if(M)putchar(‘\n‘);
123         return;
124     }
125     while(l <= r){
126         mid = (l + r) >> 1;
127         if(check(x, y, mid))l = mid + 1;
128         else r = mid - 1;
129     }
130     printf("%d", r);
131     if(M)putchar(‘\n‘);
132 }
133 inline void Change(){
134     int x, d;
135     getd(x);while(!isalpha(d = getchar()));d -= ‘a‘;
136     find(Root, x);
137     Root->val = d;
138     Root->update();
139 }
140 inline void Insert(){
141     int x, d;
142     getd(x);while(!isalpha(d = getchar()));
143     Splay *t = Pool[iter++].init(d - ‘a‘);
144     if(!x){
145         t->son[1] = Root;
146         Root = t;
147         Root->update();
148         return;
149     }
150     find(Root, x);
151     t->son[1] = Root->son[1];Root->son[1] = t;
152     t->update(); Root->update();
153 }
154 int main(){
155     #if defined DEBUG
156     freopen("test", "r", stdin);
157     freopen("out.txt", "w", stdout);
158     #else
159     //freopen("bzoj_1014.in", "r", stdin);
160     //freopen("bzoj_1014.out", "w", stdout);
161     #endif
162     int opt;
163     init();
164     while(M--){
165         while(!isalpha(opt = getchar()));
166         if(opt == ‘Q‘)
167             Query();
168 
169         else if(opt == ‘R‘)Change();
170         else Insert();
171     }
172     #if defined DEBUG
173     cout << endl<< (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
174     #endif
175     return 0;
176 }