并不是一道很无聊的题2333

Description

给定n个串，支持：

1.区间在最前面压入一个串

2.区间求LCP

n<=50000,sum<=600000

Solution

区间压串，，？？

先考虑区间求LCP，相邻LCP最小值！

故维护区间height最小值mh

 

区间压串？

对于[l+1,r]mh都加上len

l,r+1要hei不知道怎么变

必须重新找LCP

必须知道原串具体情况

LCP还要修改，hash+二分！

 

考虑，

给整个区间打上一个串的标记。。。

下放？直接复制gg

标记永久化？有先后，不能合并！

还是下放？不能直接复制？可持久化！

可持久化线段树？merge复杂度感觉不太对，且空间太大

可持久化平衡树？可持久化平衡树！

fhq-treap可持久化一下，外层二分mid

内层找hash值：

wrk0，wrk1在边界时候特殊讨论

代码：

（借鉴yjc代码和细节提醒少了很多弯路，，，一遍AC）

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define uint unsigned int#define mid ((l+r)>>1)using namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=50000+5;const int M=600000+5;const int inf=0x3f3f3f3f;const uint base=131;int n,m;uint mi[M];struct treap{    int ls,rs;    int sz;    uint hsh;    uint v;    int pri;}t[18000000+5];int tpc;int nc(char v){    ++tpc;t[tpc].hsh=t[tpc].v=v;t[tpc].pri=rand();t[tpc].sz=1;return tpc;}int sta[M],top;void up(int x){    if(!x) return;    t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+1;    t[x].hsh=t[t[x].ls].hsh+(t[x].v+base*t[t[x].rs].hsh)*mi[t[t[x].ls].sz];}void dfs(int x){        if(!x) return;//    cout<
          
           <<" "<
           
            <<" "<
            
             <
             
              t[now].pri) las=sta[top],--top; if(sta[top]) t[sta[top]].rs=now; sta[++top]=now; t[now].ls=las;// cout<<" las "<
              
               <
               
                =k) return calc(t[x].ls,k); else{ return t[t[x].ls].hsh+(t[x].v+base*calc(t[x].rs,k-t[t[x].ls].sz-1))*mi[t[t[x].ls].sz]; }}int lcp(int x,int y){ //x y is treap's rt// cout<<" lcp "<
                
                 <<" "<
                 
                  <
                 
                
               
              
             
            
           
          
         
        
       
      
     

 区间标记还能这么打？

单个标记直接打

树套树标记永久化

但是可以有时可以用可持久化数据结构当做标记！时间空间多了一个logn而已