T1咕了

 

 

 

线段树分治+李超树维护斜率优化

正常的斜率优化将f[i]定为b在这里我们将f[i]定位y就可以用李超树来维护了。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define ll long long 8 #define maxn 200000 9 using namespace std; 10 inline int read() { 11 int x=0,f=1;char ch=getchar(); 12 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; 13 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; 14 return x*f; 15 } 16 struct Edge { int to,nxt;}e[maxn*40]; 17 struct Seg { 18 ll k,b; 19 Seg (ll _=0,ll __=0){k=_,b=__;} 20 }t[maxn*4]; 21 int head[maxn*4],cnt; 22 void add(int u,int v){e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt++;} 23 int n,m,k; 24 ll p[maxn],a[maxn],b[maxn]; 25 void mark(int l,int r,int o,int L,int R,int id) { 26 if(L<=l&&R>=r) {add(o,id);return;} 27 int mid=l+r>>1,ls=o<<1,rs=ls+1; 28 if(L<=mid) mark(l,mid,ls,L,R,id); 29 if(R>mid) mark(mid+1,r,rs,L,R,id); 30 return ; 31 } 32 ll f[maxn]; 33 void build(int l,int r,int o) { 34 t[o]=Seg(0,2147483647000000ll); 35 if(l==r) return; 36 int mid=l+r>>1,ls=o<<1,rs=ls+1; 37 build(l,mid,ls);build(mid+1,r,rs); 38 } 39 ll cal(Seg now,ll x) { return now.k*x+now.b;} 40 ll sta[maxn*8],top; 41 void update(int l,int r,int o,Seg ad) { 42 sta[++top]=o; 43 if(cal(t[o],l)<=cal(ad,l)&&cal(t[o],r)<=cal(ad,r)) return; 44 if(cal(t[o],l)>=cal(ad,l)&&cal(t[o],r)>=cal(ad,r)) {t[o]=ad;return;} 45 if(l==r) { 46 if(cal(ad,l)
            
             >1,ls=o<<1,rs=ls+1; 50 if(cal(ad,mid)
             
              >1,ls=o<<1,rs=ls+1;ll ans=cal(t[o],x); 59 if(x<=mid) ans=min(ans,query(l,mid,ls,x)); 60 else ans=min(ans,query(mid+1,r,rs,x)); 61 return ans; 62 } 63 void clear() { while(top) {t[sta[top--]]=Seg(0,2147483647000000ll);}} 64 void insert(int l,int r,int o,int L,int R,Seg ad) { 65 if(L<=l&&R>=r) {update(l,r,o,ad);return;} 66 int mid=l+r>>1,ls=o<<1,rs=ls+1; 67 if(L<=mid) insert(l,mid,ls,L,R,ad); 68 if(R>mid) insert(mid+1,r,rs,L,R,ad); 69 } 70 void solve(int l,int r,int o) { 71 for(int i=head[o];i>=0;i=e[i].nxt) { 72 int to=e[i].to; 73 insert(1,m,1,p[to],m,(Seg){b[to],f[to]-b[to]*p[to]}); 74 insert(1,m,1,1,p[to],(Seg){-b[to],f[to]+b[to]*p[to]}); 75 } 76 if(head[o]>=0) { 77 for(int i=l;i<=r;i++) f[i]=min(f[i],query(1,m,1,p[i])+a[i]); 78 clear(); 79 } 80 if(l==r) return; 81 int mid=l+r>>1,ls=o<<1,rs=ls+1; 82 solve(l,mid,ls);solve(mid+1,r,rs); 83 } 84 int main() { 85 memset(head,-1,sizeof(head)); 86 n=read(),m=read(),k=read(); 87 for(int i=1;i<=n;i++) p[i]=read(); 88 for(int i=1;i<=n;i++) a[i]=read(); 89 for(int i=1;i<=n;i++) b[i]=read(); 90 for(int i=1;i<=n-1;i++) mark(1,n,1,i+1,min(i+k,n),i); 91 memset(f,27,sizeof(f));f[1]=a[1];build(1,m,1); 92 solve(1,n,1); 93 printf("%lld\n",f[n]); 94 } 95 /* 96 5 10 2 97 10 5 9 5 10 98 10 1 1 1 10 99 3 2 100 1 3100 */
             
            
           
          
         
        
       
      

 

 

 

后缀自动机+树链剖分

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define maxn 200005 8 #define mod 998244353 9 #define ll long long 10 using namespace std; 11 inline int read() { 12 int x=0,f=1;char ch=getchar(); 13 for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; 14 for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; 15 return x*f; 16 } 17 struct SUF { 18 int sz[maxn*2],link[maxn*2],step[maxn*2],son[maxn*2][26]; 19 int nxt[maxn*2],head[maxn*2],tto[maxn*2],tot,Son[maxn*2],f[maxn*2],dep[maxn*2]; 20 int cnt,last; 21 SUF() {last=cnt=1;memset(head,-1,sizeof(head));} 22 void extend(int c) { 23 int p=last,np=last=++cnt;step[np]=step[p]+1; 24 while(p&&!son[p][c]) son[p][c]=np,p=link[p]; 25 if(!p) link[np]=1; 26 else { 27 int q=son[p][c]; 28 if(step[q]==step[p]+1) link[np]=q; 29 else { 30 int nq=++cnt; 31 memcpy(son[nq],son[q],sizeof(son[q])); 32 link[nq]=link[q];link[q]=link[np]=nq; 33 step[nq]=step[p]+1; 34 while(son[p][c]==q&&p) son[p][c]=nq,p=link[p]; 35 } 36 } 37 } 38 inline void dfs(int x,int fa) { 39 sz[x]=1,dep[x]=dep[fa]+1; 40 for(int i=head[x];i>=0;i=nxt[i]) { 41 int to=tto[i];if(to==fa) continue; 42 dfs(to,x); 43 sz[x]+=sz[to]; 44 f[to]=x; 45 if(sz[Son[x]]
            
             =0;i=nxt[i]) { 56 int to=tto[i];if(to==fa||to==Son[x]) continue; 57 dfs1(to,x,to); 58 } 59 } 60 void pushup(int o) { 61 int ls=o<<1,rs=ls+1; 62 t[o].val=t[ls].val+t[rs].val; 63 t[o].sum=t[ls].sum+t[rs].sum; 64 } 65 void pushdown(int o) { 66 int ls=o<<1,rs=ls+1; 67 if(t[o].tag) { 68 t[ls].sum+=t[o].tag*t[ls].val;t[ls].sum%=mod; 69 t[rs].sum+=t[o].tag*t[rs].val;t[rs].sum%=mod; 70 t[ls].tag+=t[o].tag;t[rs].tag+=t[o].tag; 71 t[ls].tag%=mod;t[rs].tag%=mod; 72 t[o].tag=0; 73 } 74 } 75 void build(int l,int r,int o) { 76 if(l==r) { 77 t[o].val=step[rev[l]]-step[link[rev[l]]];t[o].val%=mod; 78 //cout<
             
              <<' '<
              
               <<' '<
               
                <
                
                 >1,ls=o<<1,rs=ls+1; 82 build(l,mid,ls);build(mid+1,r,rs); 83 pushup(o); 84 } 85 void update(int l,int r,int o,int L,int R) { 86 //cout<
                 
                  <<' '<
                  
                   <<' '<
                   
                    <<' '<
                    
                     <
                     
                      =r) {t[o].tag++;t[o].sum+=t[o].val;t[o].tag%=mod;t[o].sum%=mod;return;} 88 pushdown(o); 89 int mid=l+r>>1,ls=o<<1,rs=ls+1; 90 if(L<=mid) update(l,mid,ls,L,R); 91 if(R>mid) update(mid+1,r,rs,L,R); 92 pushup(o); 93 } 94 void change(int x) { 95 while(top[x]!=1) { 96 update(1,dis,1,seg[top[x]],seg[x]); 97 x=f[top[x]]; 98 } 99 update(1,dis,1,seg[1],seg[x]);100 }101 ll query(int l,int r,int o,int L,int R) {102 if(L<=l&&R>=r) { return t[o].sum%mod;}103 pushdown(o);ll ans=0;104 int mid=l+r>>1,ls=o<<1,rs=ls+1;105 if(L<=mid) ans+=query(l,mid,ls,L,R);106 if(R>mid) ans+=query(mid+1,r,rs,L,R);107 pushup(o);108 return ans%mod;109 }110 ll find(int x) {111 ll ans=0;112 while(top[x]!=1) {113 ans+=query(1,dis,1,seg[top[x]],seg[x]);ans%=mod;114 x=f[top[x]];115 }116 ans+=query(1,dis,1,seg[1],seg[x]);ans%=mod;117 return ans;118 }119 void add(int u,int v) {120 nxt[tot]=head[u];tto[tot]=v;head[u]=tot++;121 }122 }T;123 char ch[maxn];124 ll ans[maxn*2];125 int main() {126 scanf("%s",ch+1);int len=strlen(ch+1);127 for(int i=1;i<=len;i++) T.extend(ch[i]-'a');128 for(int i=2;i<=T.cnt;i++) if(T.link[i]) T.add(T.link[i],i);129 T.dfs(1,0);T.dfs1(1,0,1);T.build(1,T.dis,1);130 int now=1;131 for(int i=1;i<=len;i++) {132 now=T.son[now][ch[i]-'a'];133 ans[i]=T.find(now)+i;134 T.change(now);135 }136 for(int i=1;i<=len;i++) {137 ans[i]+=ans[i-1];ans[i]%=mod;138 }139 for(int i=1;i<=len;i++) {140 ans[i]+=ans[i-1];ans[i]%=mod;141 }142 int Q=read();143 while(Q--) {144 int x=read();145 printf("%lld\n",ans[x]);146 }147 }148 /*149 mmrmrcmrcmrc150 3151 2152 3153 12154 */