T1：

考虑反悔贪心，可以发现
要么是$(2,1)->(2,4),$即可以一次操作$+3$
或者$(1,2)*2->(2,1,0)+(0,2,1)+(0,1,2)/+(0,1,2)*3$即可以把一次$+3$改成多给后面2个$+3$的机会

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define bg beginnamespace IO{cs int RLEN=1<<20|1;
char ibuf[RLEN],*ib,*ob;inline char gc(){(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;
}inline int read(){char ch=gc();int res=0;bool f=0;while(!isdigit(ch))f=(ch=='-'),ch=gc();while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();return f?-res:res;
}inline int readstring(char *s){int top=0;char ch=gc();while(isspace(ch))ch=gc();while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();return top;
}}
using IO::read;
using IO::readstring;template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}cs int N=1000005;
int n,h[N];
ll a[N];
int main(){#ifdef Stargazerfreopen("lx.in","r",stdin);#endifn=read();ll res=0;for(int i=1;i<=n;i++)h[i]=read();for(int i=1;i<=n;i++){chemx(h[i],0);ll t1=min(a[i],(ll)h[i]/3),t2,t3;h[i]-=t1*3;t2=h[i]>>1,t3=h[i]&1;h[i+1]-=t2+t3*2;a[i+1]=t1*2+t2;res+=t1+t2+t3;}cout<<res;return 0;
}

T2：

倍增爱怎么做怎么做，可能分类讨论写的会比较复杂

code

T3：

要求可以写作$lcp,lcs$的限制
正反建两个$Sa$
一个启发式合并线段树合并维护另一个即可

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define bg begin
namespace IO{cs int RLEN=1<<20|1;
char ibuf[RLEN],*ib,*ob;
inline char gc(){(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ib==ob)?EOF:*ib++;
}	
inline int read(){char ch=gc();int res=0;bool f=0;while(!isdigit(ch))f=(ch=='-'),ch=gc();while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();return f?-res:res;
}
inline int readstring(char *s){int top=0;char ch=gc();while(isspace(ch))ch=gc();while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();return top;
}}
using IO::read;
using IO::readstring;template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}cs int N=100005;
int rt[N],ans[N],n,m;
namespace Seg{cs int N=::N*100;int lc[N],rc[N],tag[N],sz[N],tot;inline void pushnow(int u,int k){tag[u]+=k;}void pushdown(int u){if(!tag[u])return;if(lc[u])pushnow(lc[u],tag[u]);if(rc[u])pushnow(rc[u],tag[u]);tag[u]=0;}void insert(int &u,int l,int r,int p){if(!u)u=++tot;sz[u]++;if(l==r)return;int mid=(l+r)>>1;(p<=mid)?insert(lc[u],l,mid,p):insert(rc[u],mid+1,r,p);}void merge(int &u,int r1,int r2,int l,int r){if(!r1||!r2){u=r1+r2;return;}u=r1,sz[u]+=sz[r2];if(l==r)return;pushdown(r1),pushdown(r2);int mid=(l+r)>>1;merge(lc[u],lc[r1],lc[r2],l,mid);merge(rc[u],rc[r1],rc[r2],mid+1,r);}int query(int u,int l,int r,int st,int des){if(!u)return 0;if(st<=l&&r<=des)return pushnow(u,1),sz[u];int res=0,mid=(l+r)>>1;;if(st<=mid)res+=query(lc[u],l,mid,st,des);if(mid<des)res+=query(rc[u],mid+1,r,st,des);return res;}int qry(int u,int l,int r,int p){if(l==r)return tag[u];//pushdown(u);int mid=(l+r)>>1;return ((p<=mid)?qry(lc[u],l,mid,p):qry(rc[u],mid+1,r,p))+tag[u];}void get(int u,int l,int r,int *p){if(l==r){if(p[l]-m+1>0)ans[p[l]-m+1]+=tag[u];return;}int mid=(l+r)>>1;pushdown(u);get(lc[u],l,mid,p);get(rc[u],mid+1,r,p);}
}
int buc[N],lg[N];
inline void init(){for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;
}
struct Sa{int sa[N],sa2[N],rk[N],a[N],m,n,ht[N];int st[18][N];inline void rev(){reverse(rk+1,rk+n+1);for(int i=1;i<=n;i++)sa[i]=n-sa[i]+1;}inline void Sort(){for(int i=1;i<=n;i++)buc[rk[sa2[i]]]++;for(int i=1;i<=m;i++)buc[i]+=buc[i-1];for(int i=n;i>=1;i--)sa[buc[rk[sa2[i]]]--]=sa2[i];for(int i=1;i<=m;i++)buc[i]=0;}inline void build(char *s,int _n,int cas){n=_n,m=26;for(int i=1;i<=n;i++)a[i]=s[i]-'a'+1,sa2[i]=i,rk[i]=a[i];Sort();for(int i=1,pos=0;i<=n&&pos<n;i<<=1){pos=0;for(int j=n-i+1;j<=n;j++)sa2[++pos]=j;for(int j=1;j<=n;j++)if(sa[j]>i)sa2[++pos]=sa[j]-i;Sort();swap(rk,sa2),rk[sa[1]]=1,pos=1;for(int j=2;j<=n;j++)rk[sa[j]]=(sa2[sa[j]]==sa2[sa[j-1]]&&sa2[sa[j]+i]==sa2[sa[j-1]+i])?pos:++pos;m=pos;}for(int i=1,j,k=0;i<=n;ht[rk[i++]]=k)for(k?k--:0,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);if(cas==0)return;//	for(int i=1;i<=n;i++)cout<<ht[i]<<" ";puts("");for(int i=1;i<=n;i++)st[0][i]=ht[i];for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);//	cout<<"End\n";}inline int qy(int l,int r){l++;int t=lg[r-l+1];return min(st[t][l],st[t][r-(1<<t)+1]);}inline int ql(int p,int k){int l=1,r=p-1,res=p;while(l<=r){int mid=(l+r)>>1;if(qy(mid,p)>=k)res=mid,r=mid-1;else l=mid+1;}return res;}inline int qr(int p,int k){int l=p+1,r=n,res=p;while(l<=r){int mid=(l+r)>>1;if(qy(p,mid)>=k)res=mid,l=mid+1;else r=mid-1;}return res;}
}t1,t2;
int id[N],fa[N],l[N],r[N];
char str[N];
vector<int> nd[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline bool comp(int i,int j){return t1.ht[i]>t1.ht[j];}
inline void merge(int i,int j,int k){if(r[i]-l[i]<r[j]-l[j])swap(i,j);fa[j]=i;chemn(l[i],l[j]),chemx(r[i],r[j]);for(int t=l[j];t<=r[j];t++)if(t1.sa[t]+m-1<=n){int l=t2.ql(t2.rk[t1.sa[t]+m-1],k),r=t2.qr(t2.rk[t1.sa[t]+m-1],k);ans[t1.sa[t]]+=Seg::query(rt[i],1,n,l,r);//	cout<<t<<" "<<l<<" "<<r<<" "<<t1.sa[t]<<" "<<ans[t1.sa[t]]<<'\n';}Seg::merge(rt[i],rt[i],rt[j],1,n);
}
inline void solve(){for(int i=1;i<n;i++)id[i]=i+1;for(int i=1;i<=n;i++){fa[i]=i,l[i]=i,r[i]=i;if(t1.sa[i]+m-1<=n)Seg::insert(rt[i],1,n,t2.rk[t1.sa[i]+m-1]);}sort(id+1,id+n,comp);for(int t=1;t<n;t++){int i=id[t];//cout<<i<<'\n';merge(find(i),find(i-1),m-t1.ht[i]-1);//chemn(l[i],l[find(i-1)]),chemx(r[i],r[find(i-1)]);}Seg::get(rt[find(1)],1,n,t2.sa);
}
int main(){#ifdef Stargazerfreopen("lx.in","r",stdin);freopen("my.out","w",stdout);#endifn=read(),m=read();init(),readstring(str);t1.build(str,n,0);reverse(str+1,str+n+1);t2.build(str,n,1);t2.rev();solve();for(int i=1;i<=n-m+1;i++)cout<<ans[i]<<" ";puts("");return 0;
}