Advertisement
Guest User

Untitled

a guest
Jul 19th, 2021
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define _ ios_base::sync_with_stdio(0);cin.tie(0);
  6.  
  7. typedef long long ll;
  8.  
  9. const int INF = 0x3f3f3f3f;
  10. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  11.  
  12. struct dyn_sa {
  13.     struct node {
  14.         int sa, lcp;
  15.         node *l, *r, *p;
  16.         int sz, mi;
  17.         node(int sa_, int lcp_, node* p_) : sa(sa_), lcp(lcp_),
  18.             l(NULL), r(NULL), p(p_), sz(1), mi(lcp) {}
  19.         void update() {
  20.             sz = 1, mi = lcp;
  21.             if (l) sz += l->sz, mi = min(mi, l->mi);
  22.             if (r) sz += r->sz, mi = min(mi, r->mi);
  23.         }
  24.     };
  25.  
  26.     node* root;
  27.     vector<ll> tag; // tag of a suffix (reversed id)
  28.     string s; // reversed
  29.     stack<ll> st;
  30.  
  31.     dyn_sa() : root(NULL) { st.push(0); }
  32.     dyn_sa(const string& s_) : dyn_sa() { for (char c : s_) push_front(c); }
  33.     ~dyn_sa() {
  34.         vector<node*> q = {root};
  35.         while (q.size()) {
  36.             node* x = q.back(); q.pop_back();
  37.             if (!x) continue;
  38.             q.push_back(x->l), q.push_back(x->r);
  39.             delete x;
  40.         }
  41.     }
  42.  
  43.     int size(node* x) { return x ? x->sz : 0; }
  44.     int mirror(int i) { return s.size()-1 - i; }
  45.     bool cmp(int i, int j) {
  46.         if (s[i] != s[j]) return s[i] < s[j];
  47.         if (i == 0 or j == 0) return i < j;
  48.         return tag[i-1] < tag[j-1];
  49.     }
  50.     void fix_path(node* x) { while (x) x->update(), x = x->p; }
  51.     void flatten(vector<node*>& v, node* x) {
  52.         if (!x) return;
  53.         flatten(v, x->l);
  54.         v.push_back(x);
  55.         flatten(v, x->r);
  56.     }
  57.     void build(vector<node*>& v, node*& x, node* p, int L, int R, ll l, ll r) {
  58.         if (L > R) return void(x = NULL);
  59.         int M = (L+R)/2;
  60.         ll m = (l+r)/2;
  61.         x = v[M];
  62.         x->p = p;
  63.         tag[x->sa] = m;
  64.         build(v, x->l, x, L, M-1, l, m-1), build(v, x->r, x, M+1, R, m+1, r);
  65.         x->update();
  66.     }
  67.     void fix(node*& x, node* p, ll l, ll r) {
  68.         if (3*max(size(x->l), size(x->r)) <= 2*size(x)) return x->update();
  69.         vector<node*> v;
  70.         flatten(v, x);
  71.         build(v, x, p, 0, v.size()-1, l, r);
  72.     }
  73.     node* next(node* x) {
  74.         if (x->r) {
  75.             x = x->r;
  76.             while (x->l) x = x->l;
  77.             return x;
  78.         }
  79.         while (x->p and x->p->r == x) x = x->p;
  80.         return x->p;
  81.     }
  82.     node* prev(node* x) {
  83.         if (x->l) {
  84.             x = x->l;
  85.             while (x->r) x = x->r;
  86.             return x;
  87.         }
  88.         while (x->p and x->p->l == x) x = x->p;
  89.         return x->p;
  90.     }
  91.  
  92.     int get_lcp(node* x, node* y) {
  93.         if (!x or !y) return 0; // change defaut value here
  94.         if (s[x->sa] != s[y->sa]) return 0;
  95.         if (x->sa == 0 or y->sa == 0) return 1;
  96.         return 1 + query(mirror(x->sa-1), mirror(y->sa-1));
  97.     }
  98.     void add_suf(node*& x, node* p, int id, ll l, ll r) {
  99.         if (!x) {
  100.             x = new node(id, 0, p);
  101.             node *prv = prev(x), *nxt = next(x);
  102.             node* nxtnxt = nxt ? next(nxt) : NULL;
  103.  
  104.             ll val = st.top();
  105.             if (nxt and prv) val -= max(0, nxt->lcp - prv->lcp);
  106.             if (nxtnxt) val -= max(0, nxtnxt->lcp - nxt->lcp);
  107.  
  108.             int lcp_cur = get_lcp(prv, x), lcp_nxt = get_lcp(x, nxt);
  109.             if (nxt) nxt->lcp = lcp_nxt, fix_path(nxt);
  110.             x->lcp = lcp_cur;
  111.             tag[id] = (l+r)/2;
  112.             x->update();
  113.  
  114.             if (prv) val += max(0, x->lcp - prv->lcp);
  115.             if (nxt) val += max(0, nxt->lcp - x->lcp);
  116.             if (nxtnxt) val += max(0, nxtnxt->lcp - nxt->lcp);
  117.  
  118.             st.push(val);
  119.  
  120.             return;
  121.         }
  122.         if (cmp(id, x->sa)) add_suf(x->l, x, id, l, tag[x->sa]-1);
  123.         else add_suf(x->r, x, id, tag[x->sa]+1, r);
  124.         fix(x, p, l, r);
  125.     }
  126.     void push_front(char c) {
  127.         s += c;
  128.         tag.push_back(-1);
  129.         add_suf(root, NULL, s.size() - 1, 0, 1e18);
  130.     }
  131.  
  132.     void rem_suf(node*& x, int id) {
  133.         if (x->sa != id) {
  134.             if (tag[id] < tag[x->sa]) return rem_suf(x->l, id);
  135.             return rem_suf(x->r, id);
  136.         }
  137.         node* nxt = next(x);
  138.         if (nxt) nxt->lcp = min(nxt->lcp, x->lcp), fix_path(nxt);
  139.  
  140.         node *p = x->p, *tmp = x;
  141.         if (!x->l or !x->r) {
  142.             x = x->l ? x->l : x->r;
  143.             if (x) x->p = p;
  144.         } else {
  145.             for (tmp = x->l, p = x; tmp->r; tmp = tmp->r) p = tmp;
  146.             x->sa = tmp->sa, x->lcp = tmp->lcp;
  147.             if (tmp->l) tmp->l->p = p;
  148.             if (p->l == tmp) p->l = tmp->l;
  149.             else p->r = tmp->l;
  150.         }
  151.         fix_path(p);
  152.         delete tmp;
  153.     }
  154.     void pop_front() {
  155.         if (!s.size()) return;
  156.         s.pop_back();
  157.         rem_suf(root, s.size());
  158.         tag.pop_back();
  159.         st.pop();
  160.     }
  161.  
  162.     int query(node* x, ll l, ll r, ll a, ll b) {
  163.         if (!x or tag[x->sa] == -1 or r < a or b < l) return s.size();
  164.         if (a <= l and r <= b) return x->mi;
  165.         int ans = s.size();
  166.         if (a <= tag[x->sa] and tag[x->sa] <= b) ans = min(ans, x->lcp);
  167.         ans = min(ans, query(x->l, l, tag[x->sa]-1, a, b));
  168.         ans = min(ans, query(x->r, tag[x->sa]+1, r, a, b));
  169.         return ans;
  170.     }
  171.     int query(int i, int j) { // lcp(s[i..], s[j..])
  172.         if (i == j) return s.size() - i;
  173.         ll a = tag[mirror(i)], b = tag[mirror(j)];
  174.         int ret = query(root, 0, 1e18, min(a, b)+1, max(a, b));
  175.         return ret;
  176.     }
  177.     // optional: get nrk[i], sa[i] and lcp[i]
  178.     int isa(int i) {
  179.         i = mirror(i);
  180.         node* x = root;
  181.         int ret = 0;
  182.         while (x) {
  183.             if (tag[x->sa] < tag[i]) {
  184.                 ret += size(x->l)+1;
  185.                 x = x->r;
  186.             } else x = x->l;
  187.         }
  188.         return ret;
  189.     }
  190.     pair<int, int> operator[](int i) {
  191.         node* x = root;
  192.         while (1) {
  193.             if (i < size(x->l)) x = x->l;
  194.             else {
  195.                 i -= size(x->l);
  196.                 if (!i) return {mirror(x->sa), x->lcp};
  197.                 i--, x = x->r;
  198.             }
  199.         }
  200.     }
  201. };
  202.  
  203. int main() { _
  204.     dyn_sa sa;
  205.     string s; cin >> s;
  206.     for (char c : s) sa.push_front(c);
  207.     cout << sa.st.top() << endl;
  208.     cin >> s;
  209.     for (char c : s) {
  210.         if (c == '-') sa.pop_front();
  211.         else sa.push_front(c);
  212.         cout << sa.st.top() << endl;
  213.     }
  214.     exit(0);
  215. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement