Guest User

Untitled

a guest
Sep 19th, 2017
386
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. const int BUBEN = (int)110;
  9.  
  10. struct Data {
  11.   int goLeft[BUBEN], goRight[BUBEN];
  12.   int res;
  13.   int length;
  14.   Data(int x) {
  15.     x = min(x, BUBEN - 1);
  16.     res = x;
  17.     length = 1;
  18.     for (int i = 0; i < BUBEN; i++) {
  19.       if (i <= x) {
  20.         goLeft[i] = goRight[i] = 1;
  21.       } else {
  22.         goLeft[i] = goRight[i] = 0;
  23.       }
  24.     }
  25.   }
  26.   Data() {}
  27. };
  28.  
  29. void merge(const Data &l, const Data &r, Data &res) {
  30.   res.res = max(l.res, r.res);
  31.   res.length = l.length + r.length;
  32.   for (int i = 0; i < BUBEN; i++) {
  33.     res.goLeft[i] = l.goLeft[i];
  34.     if (res.goLeft[i] == l.length) res.goLeft[i] += r.goLeft[i];
  35.     res.goRight[i] = r.goRight[i];
  36.     if (res.goRight[i] == r.length) res.goRight[i] += l.goRight[i];
  37.     if (r.goLeft[i] || l.goRight[i]) {
  38.       res.res = max(res.res, i * (r.goLeft[i] + l.goRight[i] + 1));
  39.     }
  40.   }
  41. }
  42.  
  43. struct SegmentTree {
  44.   Data *t;
  45.   Data tmp, tmp2;
  46.   int n;
  47.   SegmentTree(int n) : n(n) {
  48.     t = new Data[4 * n + 3];
  49.   }
  50.   SegmentTree() {}
  51.   void change(int v, int tl, int tr, int pos, int val) {
  52.     if (tl == tr) {
  53.       t[v] = Data(val);
  54.     } else {
  55.       int tm = (tl + tr) >> 1;
  56.       if (pos <= tm) {
  57.         change(v + v, tl, tm, pos, val);
  58.       } else {
  59.         change(v + v + 1, tm + 1, tr, pos, val);
  60.       }
  61.       merge(t[v + v], t[v + v + 1], t[v]);
  62.     }
  63.   }
  64.   void build(int v, int tl, int tr, int *a) {
  65.     if (tl == tr) {
  66.       t[v] = Data(a[tl]);
  67.     } else {
  68.       int tm = (tl + tr) >> 1;
  69.       build(v + v, tl, tm, a);
  70.       build(v + v + 1, tm + 1, tr, a);
  71.       merge(t[v + v], t[v + v + 1], t[v]);
  72.     }
  73.   }
  74.   void build(int *a) {
  75.     build(1, 1, n, a);
  76.   }
  77.   void change(int pos, int val) {
  78.     change(1, 1, n, pos, val);
  79.   }
  80.   void get(int v, int tl, int tr, int l, int r) {
  81.     if (r < tl || l > tr) return;
  82.     if (tl >= l && tr <= r) {
  83.       merge(tmp, t[v], tmp2);
  84.       memcpy(&tmp, &tmp2, sizeof(tmp));
  85.     } else {
  86.       int tm = (tl + tr) >> 1;
  87.       get(v + v, tl, tm, l, r);
  88.       get(v + v + 1, tm + 1, tr, l, r);
  89.     }
  90.   }
  91.   int solve(int l, int r) {
  92.     memset(&tmp, 0, sizeof(tmp));
  93.     memset(&tmp2, 0, sizeof(tmp2));
  94.     get(1, 1, n, l, r);
  95.     return tmp.res;
  96.   }
  97. };
  98.  
  99.  
  100. int solveHistogram(const vector<int> &a) {
  101.   int n = (int)a.size();
  102.   vector<int> gol(n), gor(n);
  103.   vector<int> st;
  104.   st.reserve(n);
  105.   for (int i = 0; i < n; i++) {
  106.     while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
  107.     if (st.empty()) {
  108.       gol[i] = 0;
  109.     } else {
  110.       gol[i] = st.back() + 1;
  111.     }
  112.     st.push_back(i);
  113.   }
  114.   st.clear();
  115.   for (int i = n - 1; i >= 0; i--) {
  116.     while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
  117.     if (st.empty()) {
  118.       gor[i] = n - 1;
  119.     } else {
  120.       gor[i] = st.back() - 1;
  121.     }
  122.     st.push_back(i);
  123.   }
  124.   int res = 0;
  125.   for (int i = 0; i < n; i++) {
  126.     res = max(res, a[i] * (gor[i] - gol[i] + 2));
  127.   }
  128.   return res;
  129. }
  130.  
  131. struct LargeSolver {
  132.   int *a;
  133.   int n;
  134.   set<int> largePoses;
  135.   LargeSolver(int n) : n(n) {
  136.     a = new int[n + 1];
  137.   }
  138.   LargeSolver() {}
  139.   void change(int pos, int val) {
  140.     if (a[pos] >= BUBEN) {
  141.       largePoses.erase(pos);
  142.     }
  143.     a[pos] = val;
  144.     if (a[pos] >= BUBEN) {
  145.       largePoses.insert(pos);
  146.     }
  147.   }
  148.   int solve(int l, int r) {
  149.     auto it = largePoses.lower_bound(l);
  150.     int res = 0;
  151.     vector<int> cur;
  152.     int lst = -1;
  153.     while (it != largePoses.end() && (*it) <= r) {
  154.       int curPos = (*it);
  155.       if (curPos != lst + 1 && !cur.empty()) {
  156.         res = max(res, solveHistogram(cur));
  157.         cur.clear();
  158.       }
  159.       cur.push_back(a[curPos]);
  160.       lst = curPos;
  161.       it++;
  162.     }
  163.     if (!cur.empty()) {
  164.       res = max(res, solveHistogram(cur));
  165.     }
  166.     return res;
  167.   }
  168. };
  169.  
  170. struct MaxSegmentTree {
  171.   int *t;
  172.   int n;
  173.   MaxSegmentTree(int n) : n(n) {
  174.     t = new int[4 * n + 3];
  175.   }
  176.   MaxSegmentTree() {}
  177.   void change(int v, int tl, int tr, int pos, int val) {
  178.     if (tl == tr) {
  179.       t[v] = val;
  180.     } else {
  181.       int tm = (tl + tr) >> 1;
  182.       if (pos <= tm) {
  183.         change(v + v, tl, tm, pos, val);
  184.       } else {
  185.         change(v + v + 1, tm + 1, tr, pos, val);
  186.       }
  187.       t[v] = max(t[v + v], t[v + v + 1]);
  188.     }
  189.   }
  190.   void change(int pos, int val) {
  191.     change(1, 1, n, pos, val);
  192.   }
  193.   int getMax(int v, int tl, int tr, int l, int r) {
  194.     if (r < tl || l > tr) return 0;
  195.     if (tl >= l && tr <= r) return t[v];
  196.     int tm = (tl + tr) >> 1;
  197.     return max(getMax(v + v, tl, tm, l, r), getMax(v + v + 1, tm + 1, tr, l, r));
  198.   }
  199.   int getMax(int l, int r) {
  200.     return getMax(1, 1, n, l, r);
  201.   }
  202. };
  203.  
  204. struct DynamicHystogramSolver {
  205.   SegmentTree st;
  206.   LargeSolver ls;
  207.   DynamicHystogramSolver() {}
  208.   DynamicHystogramSolver(int *a, int n) {
  209.     st = SegmentTree(n);
  210.     st.build(a);
  211.     ls = LargeSolver(n);
  212.     for (int i = 1; i <= n; i++) {
  213.       ls.change(i, a[i]);
  214.     }
  215.   }
  216.   void change(int pos, int val) {
  217.     st.change(pos, val);
  218.     ls.change(pos, val);
  219.   }
  220.   int getMax(int l, int r) {
  221.     if (l > r) return 0;
  222.     return max(st.solve(l, r), ls.solve(l, r));
  223.   }
  224. };
  225.  
  226. int getLCP(const string &s, const string &t) {
  227.   int ptr = 0;
  228.   while (ptr < (int)min(s.size(), t.size()) && s[ptr] == t[ptr]) ptr++;
  229.   return ptr;
  230. }
  231. struct Solver {
  232.   string *s;
  233.   int *lcp;
  234.   int n;
  235.   DynamicHystogramSolver dhs;
  236.   MaxSegmentTree st;
  237.   Solver(const vector<string> &a) {
  238.     n = a.size();
  239.     s = new string[n + 1];
  240.     lcp = new int[n + 1];
  241.     for (int i = 1; i <= n; i++) {
  242.       s[i] = a[i - 1];
  243.     }
  244.     for (int i = 1; i < n; i++) {
  245.       lcp[i] = getLCP(s[i], s[i + 1]);
  246.     }
  247.     dhs = DynamicHystogramSolver(lcp, n);
  248.     st = MaxSegmentTree(n);
  249.     for (int i = 1; i <= n; i++) {
  250.       st.change(i, (int)s[i].size());
  251.     }
  252.   }
  253.   void change(int pos, const string &str) {
  254.     s[pos] = str;
  255.     if (pos != 1) {
  256.       lcp[pos - 1] = getLCP(s[pos - 1], s[pos]);
  257.       dhs.change(pos - 1, lcp[pos - 1]);
  258.     }
  259.     if (pos != n) {
  260.       lcp[pos] = getLCP(s[pos], s[pos + 1]);
  261.       dhs.change(pos, lcp[pos]);
  262.     }
  263.     st.change(pos, (int)str.size());
  264.   }
  265.   int solve(int l, int r) {
  266.     return max(dhs.getMax(l, r - 1), st.getMax(l, r));
  267.   }
  268. };
  269.  
  270. const int MX = 300 * 1000 + 7;
  271.  
  272. char buf[MX];
  273.  
  274. string getString() {
  275.   scanf("%s", buf);
  276.   return string(buf);
  277. }
  278.  
  279. int main() {
  280. #ifdef LOCAL
  281.   freopen("input.txt", "r", stdin);
  282. #endif
  283.   int n, q;
  284.   scanf("%d %d", &n, &q);
  285.   vector<string> s(n);
  286.   for (int i = 0; i < n; i++) {
  287.     s[i] = getString();
  288.   }
  289.   Solver solver(s);
  290.   for (int i = 0; i < q; i++) {
  291.     int type;
  292.     scanf("%d", &type);
  293.     if (type == 1) {
  294.       int l, r;
  295.       scanf("%d %d", &l, &r);
  296.       printf("%d\n", solver.solve(l, r));
  297.     } else {
  298.       int pos;
  299.       scanf("%d ", &pos);
  300.       solver.change(pos, getString());
  301.     }
  302.   }
  303.   return 0;
  304. }
RAW Paste Data