Guest User

Untitled

a guest
Sep 19th, 2017
285
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. const int SQ=150;
  6. const int MAXN=100001;
  7. const int MAXLEN=300002;
  8.  
  9. struct snode
  10. {
  11.     int maxl[SQ],maxr[SQ],maxi,len;
  12.     snode(int x)
  13.     {
  14.         x=min(x,SQ-1);
  15.         for(int i=0;i<SQ;i++)
  16.         {
  17.             maxl[i]=maxr[i]=(i<=x);
  18.             len=1; maxi=x;
  19.         }
  20.     }
  21.     snode()
  22.     {
  23.         maxi=len=0;
  24.         for(int i=0;i<SQ;i++) maxl[i]=maxr[i]=0;
  25.     }
  26.     snode operator+(const snode& other) const
  27.     {
  28.         snode res;
  29.         res.maxi=max(maxi,other.maxi);
  30.         res.len=len+other.len;
  31.         for(int i=0;i<SQ;i++)
  32.         {
  33.             res.maxl[i]=maxl[i];
  34.             if(maxl[i]==len) res.maxl[i]+=other.maxl[i];
  35.             res.maxr[i]=other.maxr[i];
  36.             if(other.maxr[i]==other.len) res.maxr[i]+=maxr[i];
  37.             if(maxr[i]||other.maxl[i]) res.maxi=max(res.maxi,i*(maxr[i]+other.maxl[i]+1));
  38.         }
  39.         return res;
  40.     }
  41. };
  42.  
  43. snode stree[4*MAXN];
  44. int mtree[4*MAXN];
  45. int lcparr[MAXN];
  46. string arr[MAXN];
  47. set<int> active;
  48. int n,q;
  49. char buf[MAXLEN];
  50.  
  51. void build(int sq,int node,int l,int r)
  52. {
  53.     if(l>r) return;
  54.     if(l==r)
  55.     {
  56.         if(sq==-1) mtree[node]=arr[l].size();
  57.         else stree[node]=snode(lcparr[l]);
  58.         return;
  59.     }
  60.     int mid=(l+r)/2;
  61.     build(sq,node*2,l,mid);
  62.     build(sq,node*2+1,mid+1,r);
  63.     if(sq==-1) mtree[node]=max(mtree[node*2],mtree[node*2+1]);
  64.     else stree[node]=stree[node*2]+stree[node*2+1];
  65. }
  66.  
  67. void update(int sq,int node,int l,int r,int ind)
  68. {
  69.     if(ind<l||ind>r||l>r) return;
  70.     if(l==r)
  71.     {
  72.         if(sq==-1) mtree[node]=arr[l].size();
  73.         else stree[node]=snode(lcparr[l]);
  74.         return;
  75.     }
  76.     int mid=(l+r)/2;
  77.     update(sq,node*2,l,mid,ind);
  78.     update(sq,node*2+1,mid+1,r,ind);
  79.     if(sq==-1) mtree[node]=max(mtree[node*2],mtree[node*2+1]);
  80.     else stree[node]=stree[node*2]+stree[node*2+1];}
  81.  
  82. snode query(int sq,int node,int l,int r,int ql,int qr)
  83. {
  84.     if(r<ql||qr<l||l>r) return snode();
  85.     if(ql<=l&&r<=qr)
  86.         return stree[node];
  87.     int mid=(l+r)/2;
  88.     return query(sq,node*2,l,mid,ql,qr)+query(sq,node*2+1,mid+1,r,ql,qr);
  89. }
  90.  
  91. int query(int node,int l,int r,int ql,int qr)
  92. {
  93.     if(r<ql||qr<l||l>r) return 0;
  94.     if(ql<=l&&r<=qr) return mtree[node];
  95.     int mid=(l+r)/2;
  96.     return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
  97. }
  98.  
  99. int solve1(int l,int r)
  100. {
  101.     if(r<l) return arr[l].size();
  102.     int maxi=query(1,1,0,n-2,l,r).maxi;
  103.     return max(maxi,query(1,0,n-1,l,r+1));
  104. }
  105.  
  106. int lb[2*MAXN],rb[2*MAXN];
  107. stack<int> ll,rr;
  108. vector<int> v;
  109.  
  110. int solve2(int l,int r)
  111. {
  112.     if(r<l) return arr[l].size();
  113.     int last=-2;
  114.     v.clear();
  115.     for(auto it=active.lower_bound(l);it!=active.upper_bound(r);it++)
  116.     {
  117.         if((*it)!=last+1) v.push_back(0);
  118.         last=(*it);
  119.         v.push_back(lcparr[last]);
  120.     }
  121.     if(v.empty()) return 0;
  122.     while(!ll.empty()) ll.pop();
  123.     while(!rr.empty()) rr.pop();
  124.     int i;
  125.     for(i=0;i<v.size();i++)
  126.     {
  127.         while(!ll.empty()&&v[ll.top()]>=v[i]) ll.pop();
  128.         if(ll.empty()) lb[i]=-1;
  129.         else lb[i]=ll.top();
  130.         ll.push(i);
  131.     }
  132.     for(i=v.size()-1;i>=0;i--)
  133.     {
  134.         while(!rr.empty()&&v[rr.top()]>=v[i]) rr.pop();
  135.         if(rr.empty()) rb[i]=v.size();
  136.         else rb[i]=rr.top();
  137.         rr.push(i);
  138.     }
  139.     int ans=0;
  140.     for(i=0;i<v.size();i++)
  141.     {
  142.         ans=max(ans,v[i]*(rb[i]-lb[i]));
  143.     }
  144.     return ans;
  145. }
  146.  
  147. void update(int ind,int las)
  148. {
  149.     if(las>=SQ&&lcparr[ind]<SQ)
  150.         active.erase(ind);
  151.     if(las<SQ&&lcparr[ind]>=SQ)
  152.         active.insert(ind);
  153.     int i;
  154.     /*for(i=las+1;i<min(SQ,lcparr[ind]+1);i++)
  155.         update(i,1,0,n-2,ind);
  156.     for(i=min(SQ-1,lcparr[ind]+1);i<=las;i++)
  157.         update(i,1,0,n-2,ind);*/
  158.     update(1,1,0,n-2,ind);
  159. }
  160.  
  161. int lcp(int x,int y)
  162. {
  163.     int ans=0;
  164.     while(ans<arr[x].size()&&ans<arr[y].size()&&arr[x][ans]==arr[y][ans]) ans++;
  165.     return ans;
  166. }
  167.  
  168. int main()
  169. {
  170.     scanf("%d %d",&n,&q);
  171.     int i;
  172.     for(i=0;i<n;i++)
  173.     {
  174.         scanf("%s",buf);
  175.         arr[i]=buf;
  176.     }
  177.     for(i=0;i<n-1;i++)
  178.         lcparr[i]=lcp(i,i+1);
  179.     build(1,1,0,n-2);
  180.     build(-1,1,0,n-1);
  181.     for(i=0;i<n-1;i++)
  182.     {
  183.         if(lcparr[i]>=SQ) active.insert(i);
  184.     }
  185.     while(q--)
  186.     {
  187.         int t;
  188.         scanf("%d",&t);
  189.         if(t==1)
  190.         {
  191.             int l,r; scanf("%d %d",&l,&r); l--; r--;
  192.             printf("%d\n",max(solve1(l,r-1),solve2(l,r-1)));
  193.             fflush(stdout);
  194.         }
  195.         else
  196.         {
  197.             int ind;
  198.             scanf("%d %s",&ind,buf);
  199.             ind--;
  200.             arr[ind]=buf;
  201.             update(-1,1,0,n-1,ind);
  202.             if(ind-1>=0)
  203.             {
  204.                 int tmp=lcparr[ind-1];
  205.                 lcparr[ind-1]=lcp(ind-1,ind);
  206.                 update(ind-1,tmp);
  207.             }
  208.             if(ind+1<n)
  209.             {
  210.                 int tmp=lcparr[ind];
  211.                 lcparr[ind]=lcp(ind,ind+1);
  212.                 update(ind,tmp);
  213.             }
  214.         }
  215.     }
  216. }
RAW Paste Data