2022.02.20 SA

如果我还能看见明天黎明，如果我还能再爬起来，我仍会走我的路，哪怕这条路已经荒废许久，也许我们无法拥有感情，我们甚至无法像个正常人一样接受太阳的洗礼，但是我依然会执行我的条约，哪怕不会有人记得我，哪怕我们并不会记入编年史，我们的名字也许会成为辱骂的对象，我依然执行我的信条当其他人都盲目追寻真理的时候，记住，万事皆虚，当其他人的思想都被法律与道德所束缚的时候，记住，万事皆允。我们躬耕于黑暗却服侍于，并非是我选择了这样的一生，而是一生选了我。——《刺客信条》

SA:

http://www.yhzq-blog.cc/后缀数组算法总结/

段错误：

https://blog.csdn.net/lotluck/article/details/42948593

https://www.cnblogs.com/smalltigerlee/archive/2011/10/26/2225183.html

Step 1 模板代码

1.1 前置知识基数排序

https://www.cnblogs.com/Cherish486/p/15394442.html

1.2 代码如下（SA模板1.0）

https://www.luogu.com.cn/problem/P4248

#include<bits/stdc++.h>

using namespace std;

#define Ri register

const int N=5e5+10;

typedef long long ll;

int n,m,wa[N],wb[N],wv[N],wsi[N],sa[N],ranki[N],r[N];

int height[N],h[N];

int stacki[N],top;

char s[N];

ll ans[N];

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&r[a+len]==r[b+len];

}

inline void SA(int *r,int *sa,int n,int m){

	m=129;

	int *x=wa,*y=wb,*t;

	for(Ri int i=0;i<m;i++)wsi[i]=0;

	for(Ri int i=0;i<n;i++)++wsi[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wsi[i]+=wsi[i-1];

	for(Ri int i=n-1;~i;i--)sa[--wsi[x[i]]]=i;

	/*cout<<"r "<<endl;

	for(Ri int i=0;i<n;i++)cout<<r[i]<<" ";cout<<endl;

	cout<<"x "<<endl;

	for(Ri int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;

	cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;*/

	int p=1;

	for(Ri int j=1;p<n;j*=2,m=p){

		//cout<<"len j "<<j<<endl;

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		//这里是按照第一次sa数组的排序，然后记录它前一个的位置，这样就是对suf第二个字符进行排序

		//y中存第二个关键词排序后的结果

		/*cout<<"sa "<<endl;

		for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

		cout<<"x "<<endl;

		for(Ri int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;

		cout<<"y "<<endl;

		for(Ri int i=0;i<p;i++)cout<<y[i]<<" ";cout<<endl;*/

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		//根据第二关键词更新了第一关键词的顺序，就是根据第二关键词，找第一关键词

		//x中存第一关键词排序的顺序

		/*cout<<"wv "<<endl;

		for(Ri int i=0;i<n;i++)cout<<wv[i]<<" ";cout<<endl;*/

		for(Ri int i=0;i<m;i++)wsi[i]=0;

		for(Ri int i=0;i<n;i++)++wsi[wv[i]];

		for(Ri int i=1;i<m;i++)wsi[i]+=wsi[i-1];

		for(Ri int i=n-1;~i;i--)sa[--wsi[wv[i]]]=y[i];

		//y中存的是W位置，sa中需要存的就是位置

		/*cout<<"sa "<<endl;

		for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;*/

		t=x,x=y,y=t;

		p=1;

		x[sa[0]]=0;

		for(Ri int i=1;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		//x是两个关键词排序后的新序号

		/*cout<<"x before y ranki "<<endl;

		for(Ri int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;*/

	}

}

inline void find_height(int *r,int *sa,int n){

	int k=0,j;

	for(Ri int i=1;i<n;i++)ranki[sa[i]]=i;

	/*cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;*/

	for(Ri int i=0;i<n-1;height[ranki[i++]]=k)

	for(k?k--:0,j=sa[ranki[i]-1];r[i+k]==r[j+k];k++);

	/*cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

}

signed main(){

	scanf("%s",s);

	n=strlen(s);

	ll fin=1ll*n*(n+1)*(n-1)/2;

	for(Ri int i=0;i<n;i++)r[i]=s[i];

	r[n++]=0;

	SA(r,sa,n,m);

	find_height(r,sa,n);

	for(Ri int i=0;i<n;i++){

		while(top&&height[i]<height[stacki[top]])--top;

		int j=stacki[top];

		ans[i]=ans[j]+1ll*(i-j)*height[i];

		fin-=2*ans[i];

		stacki[++top]=i;

	}

	cout<<fin;

	return 0;

}

1.3 重点

1.3.1 关于判断越界

有两种方法：

手动判断越界

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&

	(a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]);

}

字符串末尾加0表示结束

r[n++]=0;

Step 2 练习题

P2178 [NOI2015] 品酒大会

https://www.luogu.com.cn/problem/P2178

https://www.cnblogs.com/refun/p/8679198.html

100pts（别人的）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define MAXN (300000+100)

using namespace std;

int wt[MAXN],wa[MAXN],wb[MAXN];

int SA[MAXN],Rank[MAXN],Height[MAXN];

char r[MAXN];

int a[MAXN],cnt;

int ID[MAXN],Father[MAXN];

long long Size[MAXN],Max[MAXN],Min[MAXN],Ans[MAXN][2],INF;

int n,m=130;

bool cmp(int *y,int a,int b,int k)

{

    int arank1=y[a];

    int brank1=y[b];

    int arank2=a+k>=n?-1:y[a+k];

    int brank2=b+k>=n?-1:y[b+k];

    return arank1==brank1 && arank2==brank2;

}

void Build_SA()

{

    int *x=wa,*y=wb;

    for (int i=0;i<m;++i) wt[i]=0;

    for (int i=0;i<n;++i) wt[x[i]=r[i]]++;

    for (int i=1;i<m;++i) wt[i]+=wt[i-1];

    for (int i=n-1;i>=0;--i) SA[--wt[x[i]]]=i;

    for (int j=1;j<=n;j<<=1)

    {

        int p=0;

        for (int i=n-j;i<n;++i) y[p++]=i;

        for (int i=0;i<n;++i) if (SA[i]>=j) y[p++]=SA[i]-j;

        for (int i=0;i<m;++i) wt[i]=0;

        for (int i=0;i<n;++i) wt[x[y[i]]]++;

        for (int i=1;i<m;++i) wt[i]+=wt[i-1];

        for (int i=n-1;i>=0;--i) SA[--wt[x[y[i]]]]=y[i];

        m=1;swap(x,y);

        x[SA[0]]=0;

        for (int i=1;i<n;++i)

            x[SA[i]]=cmp(y,SA[i],SA[i-1],j)?m-1:m++;

        if (m>=n) break;

    }

}

void Build_Height()

{

    for (int i=0;i<n;++i) Rank[SA[i]]=i;

    int k=0;

    Height[0]=0;

    for (int i=0;i<n;++i)

    {

        if (!Rank[i]) continue;

        if (k) k--;

        int j=SA[Rank[i]-1];

        while (r[i+k]==r[j+k]) k++;

        Height[Rank[i]]=k;

    }

}

int Find (int x) {return Father[x]==x?x:Father[x]=Find(Father[x]);}

void Merge (int x,int y)

{

    int f1=Find(x),f2=Find(y);

    int k=Height[x];

    Ans[k][0]+=Size[f2]*Size[f1];

    Ans[k][1]=max(max(Max[f2]*Max[f1],Min[f2]*Min[f1]),Ans[k][1]);

    Min[f1]=min(Min[f1],Min[f2]);

    Max[f1]=max(Max[f1],Max[f2]);

    Father[f2]=f1;

    Size[f1]+=Size[f2];

}

void Solve()

{

    for (int i=0;i<n;++i)

    {

        Father[i]=i;

        Size[i]=1;

        Max[i]=Min[i]=a[SA[i]];

    }

    for (int i=0;i<=n-1;++i)

        if (Find(ID[i])!=Find(ID[i]-1))

            Merge(ID[i],ID[i]-1);

}

bool cmp1(int x,int y)

{

    return Height[x]>Height[y];

}

int main()

{

    memset(&INF,0x7f,sizeof(INF));

    scanf("%d",&n);

    scanf("%s",r);

    for (int i=0;i<n;++i)

        scanf("%d",&a[i]);

    Build_SA();

    Build_Height();

    for (int i=0;i<n;++i)

    {

        ID[i]=i;

        Ans[i][0]=0;

        Ans[i][1]=-INF;

    }

    sort(ID,ID+n,cmp1);

    Solve();

    for (int i=n-2;i>=0;--i)

    {

        Ans[i][0]+=Ans[i+1][0];

        Ans[i][1]=max(Ans[i][1],Ans[i+1][1]);

    }

    for (int i=0;i<n;++i)

        printf("%lld %lld\n",Ans[i][0],Ans[i][0]==0?0:Ans[i][1]);

}

90pts（我的）

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define Ri register

const int N=3e6+1000;

const int inf=1e18;

int n,m,a[N];

int r[N],wa[N],wb[N],wv[N],t[N],sa[N],ranki[N];

int height[N];

int fa[N],sizei[N],maxn[N],minn[N],ans[N][2],id[N];

char s[N];

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&r[a+len]==r[b+len];

}

inline void SA(int *r,int *sa,int n,int m){

	m=400;

	int *x=wa,*y=wb;

	for(Ri int i=0;i<m;i++)t[i]=0;

	for(Ri int i=0;i<n;i++)++t[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)t[i]+=t[i-1];

	for(Ri int i=n-1;~i;i--)sa[--t[x[i]]]=i;

	//cout<<"Case 1 "<<endl;

	int p=1;

	for(Ri int j=1;p<n&&j<=n;j<<=1,m=p){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)t[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++t[wv[i]];

		for(Ri int i=1;i<m;i++)t[i]+=t[i-1];

		for(Ri int i=n-1;~i;i--)sa[--t[wv[i]]]=y[i];

		int *t;

		t=x;x=y;y=t;

		x[sa[0]]=0;

		p=1;

		for(Ri int i=1;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

	}

	//for(Ri int i=0;i<n;i++)cout<<sa[i]<<endl;

}

inline void calc(int *r,int *sa,int n){

	//cout<<"Case 2"<<endl;

	int k=0,j;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	for(Ri int i=0;i<n;height[ranki[i++]]=k)//if(ranki[i])

	for(k?--k:0,j=sa[ranki[i]-1];r[i+k]==r[j+k];++k);

	/*cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;

	cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

	//for(Ri int i=0;i<n;i++)cout<<sa[i]<<endl;

}

inline int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

inline void merge(int x,int y){

	int xi=find(x),yi=find(y);

	int k=height[x];

	ans[k][0]+=sizei[xi]*sizei[yi];

	ans[k][1]=max(ans[k][1],max(maxn[xi]*maxn[yi],minn[xi]*minn[yi]));

	maxn[xi]=max(maxn[xi],maxn[yi]);

	minn[xi]=min(minn[xi],minn[yi]);

	fa[yi]=xi;

	sizei[xi]+=sizei[yi];

}

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline int cmp1(int x,int y){

	return height[x]>height[y];

}

signed main(){

	//freopen("P2178_3.in","r",stdin);

	//freopen("P2178.out","w",stdout);

	n=read();

	//cout<<n<<endl;

	scanf("%s",s);

	for(Ri int i=0;i<n;i++)r[i]=s[i];

	//r[n++]=0;

	SA(r,sa,n,m);calc(r,sa,n);

	//--n;

	//cout<<"Case 3"<<endl;

	for(Ri int i=0;i<n;i++){

		a[i]=read();

		id[i]=i;

		ans[i][0]=0;

		ans[i][1]=-inf;

	}

	sort(id,id+n,cmp1);

	//cout<<"Case 4"<<endl;

	//cout<<n<<endl;

	for(Ri int i=0;i<n;i++)fa[i]=i,sizei[i]=1,minn[i]=maxn[i]=a[sa[i]];

	//cout<<"Case 6"<<endl;

	for(Ri int i=0;i<n;i++)if(find(id[i])!=find(id[i]-1)&&id[i]-1>-1)merge(id[i],id[i]-1);

	//cout<<"Case 5"<<endl;

	for(int i=n-2;i>=0;i--)ans[i][0]+=ans[i+1][0],ans[i][1]=max(ans[i][1],ans[i+1][1]);

	for(Ri int i=0;i<n;i++)cout<<ans[i][0]<<" "<<(ans[i][0]==0?0:ans[i][1])<<endl;

	return 0;

}

P4051 [JSOI2007]字符加密

https://www.luogu.com.cn/problem/P4051

100pts（标准求SA模板2.0）

#include<bits/stdc++.h>

using namespace std;

#define Ri register

const int N=2e5+10;

int n,m,r[N],sa[N],wa[N],wb[N],wv[N],wt[N],ranki[N],height[N];

char s[N];

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&r[a+len]==r[b+len];

}

inline void SA(int *r,int *sa,int n,int m){

	m=400;

	int *x=wa,*y=wb,*t,p=1;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;~i;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<=n;j<<=1,m=p){

        //更改处：改为根据j和p共同判断是否跳出循环

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;~i;i--)sa[--wt[wv[i]]]=y[i];

		t=x;x=y;y=t;

		p=1;

		x[sa[0]]=0;

		for(Ri int i=1;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		if(p>=n)break;

	}

	//for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

}

signed main(){

	scanf("%s",s);

	n=strlen(s);

	for(Ri int i=0;i<n;i++)s[i+n]=s[i];

	n<<=1;

	//for(Ri int i=0;i<n;i++)cout<<s[i];cout<<endl;

	for(Ri int i=0;i<n;i++)r[i]=s[i];

	SA(r,sa,n,m);

	for(Ri int i=0;i<n;i++)if(sa[i]<n/2)cout<<s[sa[i]+n/2-1];

	return 0;

}

SP694 DISUBSTR - Distinct Substrings

https://www.luogu.com.cn/problem/SP694

100pts（SA模板3.0）

#include<bits/stdc++.h>

using namespace std;

#define Ri register

#define ll long long

const int N=5e4+10;

int T,n,m,r[N],sa[N],wa[N],wb[N],wv[N],wt[N],ranki[N],height[N];

char s[N];

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&(a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]);

    //更改处1：增加比较超过n的地方

}

inline void SA(int *r,int *sa,int n,int m){

	int p=1,*x=wa,*y=wb,*t;

	m=1010;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<=n;j<<=1){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;i>=0;i--)sa[--wt[wv[i]]]=y[i];

		p=1;

		t=x;x=y;y=t;

		x[sa[0]]=0;

		for(Ri int i=1;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		//cout<<"len "<<j<<endl;

		//for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

		m=p;

		if(p>=n)break;

	}

}

inline void calc(int *r,int *sa,int n){

	int k=0,j;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	//height[0]=0;

	for(Ri int i=0;i<n;i++){

		if(ranki[i]==0)continue;

		if(k)--k;

		j=sa[ranki[i]-1];

		while(i+k<n&&j+k<n&&r[i+k]==r[j+k])++k;

		height[ranki[i]]=k;

	}

    //更改处2：更改为i为循环元素

	/*for(Ri int i=0;i<n-1;height[ranki[i++]]=k)

	for(k?k--:0,j=sa[ranki[i]-1];r[i+k]==r[j+k];k++);*/

	//for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;

	//for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;

}

signed main(){

	cin>>T;

	while(T--){

		scanf("%s",s);

		n=strlen(s);

		for(Ri int i=0;i<n;i++)r[i]=s[i];

		SA(r,sa,n,m);calc(r,sa,n);

		ll ans=n-sa[0];

		for(Ri int i=1;i<n;i++)ans+=n-sa[i]-height[i];

		cout<<ans<<endl;

	}

	return 0;

}

P2852 [USACO06DEC]Milk Patterns G(重复的K次最长字串：RMQ+SA)

https://www.luogu.com.cn/problem/P2852

100pts：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<bits/stdc++.h>

using namespace std;

#define Ri register

const int N=2e4+10;

const int inf=0x3f3f3f3f;

int n,m,K;

int r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];

int a[N],f[N][20],logi[N];

inline int cmp(int *r,int a,int b,int len){

	return r[a]==r[b]&&(a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]);

}

inline void SA(int *r,int *sa,int n,int m){

	m=500;

	int *x=wa,*y=wb,*t,p=1;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<=n;j*=2,m=p){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;i>=0;i--)sa[--wt[wv[i]]]=y[i];

		p=1;

		t=x;x=y;y=t;

		x[sa[0]]=0;

		for(Ri int i=1;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		if(p>=n)break;

	}

}

inline void calc(int *r,int *sa,int n){

	int k=0,j=1;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	height[0]=0;

	for(Ri int i=0;i<n;i++){

		if(!ranki[i])continue;

		if(k)--k;

		j=sa[ranki[i]-1];

		while(max(i,j)+k<n&&r[i+k]==r[j+k])++k;

		height[ranki[i]]=k;

	}

	/*cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

	cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

}

inline int find(int minn){

	int tot=0,maxn=-1;

	for(Ri int i=1;i<n;i++)

	if(height[i]<0)maxn=max(maxn,tot),tot=0;

	else{

		if(height[i-1]<minn)tot=2;

		else ++tot;

	}

	return maxn>=K;

}

inline int erfen(int l,int r){

	int L=l,R=r+1,mid,ans;

	while(L<=R){

		mid=(L+R)>>1;

		cout<<"L "<<L<<" R "<<R<<" mid "<<mid<<" ans "<<ans<<" a[ans] "<<a[ans]<<endl;

		if(find(mid))L=ans=mid;

		else R=mid-1;

	}

	return a[ans];

}

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline int query(int l,int r){

	int k=logi[r-l];

	return min(f[l][k],f[r-(1<<k)+1][k]);

}

signed main(){

	memset(f,inf,sizeof(f));

	n=read();K=read();

	logi[1]=0;logi[2]=1;

	for(Ri int i=2;i<=n;i++)logi[i]=logi[i/2]+1;

	//cout<<"logi "<<endl;

	//for(Ri int i=1;i<=n;i++)cout<<logi[i]<<" ";cout<<endl;

	for(Ri int i=0;i<n;i++)r[i]=read();

	SA(r,sa,n,m);calc(r,sa,n);

	for(Ri int i=1;i<n;i++)f[i][0]=a[i]=height[i];

	sort(a+1,a+n+1);

	int len=unique(a+1,a+n)-a-1;

	//cout<<"a "<<endl;

	//for(Ri int i=1;i<=len;i++)cout<<a[i]<<" ";cout<<endl;

	for(Ri int i=1;i<=15;i++)

	for(Ri int j=1;j+(1<<(i))-1<n;j++)

	f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);

	/*cout<<"f "<<endl;

	for(Ri int i=1;i<n;i++){

		for(Ri int j=0;j<=4;j++)cout<<f[i][j]<<" ";

		cout<<endl;

	}

	cout<<endl;*/

	//int ans=erfen(1,len);

	int ans=-1;

	for(Ri int i=1;i+K-2<n;i++){

		int x=query(i,i+K-2);

		//cout<<i<<" "<<i+K-2<<" "<<x<<endl;

		ans=max(ans,x);

	}

	cout<<ans;

	return 0;

}

2022.02.20 SA

2022.02.20 SA

Step 1 模板代码

1.1 前置知识基数排序

1.2 代码如下（SA模板1.0）

1.3 重点

1.3.1 关于判断越界

Step 2 练习题

P2178 [NOI2015] 品酒大会

100pts（别人的）

90pts（我的）

P4051 [JSOI2007]字符加密

100pts（标准求SA模板2.0）

SP694 DISUBSTR - Distinct Substrings

100pts（SA模板3.0）

P2852 [USACO06DEC]Milk Patterns G(重复的K次最长字串：RMQ+SA)

100pts：

2022.02.20 SA的相关教程结束。

相关推荐

nsa+sa模式要不要开

5g手机从哪看出来是NSA和SA

SA网络专属流量都能干什么

SQL2000中的默认sa帐号的修改与删除方法

2022.02.21 UB

2022.02.21 SA

SQL SERVER 2008 windows、sa账户同时不能登录

sqlserver添加sa用户和密码的实现

2022.02.20 SA

2022.02.20 SA

Step 1 模板代码

1.1 前置知识 基数排序

1.2 代码如下（SA模板1.0）

1.3 重点

1.3.1 关于判断越界

Step 2 练习题

P2178 [NOI2015] 品酒大会

100pts（别人的）

90pts（我的）

P4051 [JSOI2007]字符加密

100pts（标准求SA模板2.0）

SP694 DISUBSTR - Distinct Substrings

100pts（SA模板3.0）

P2852 [USACO06DEC]Milk Patterns G(重复的K次最长字串：RMQ+SA)

100pts：

2022.02.20 SA的相关教程结束。

相关推荐

nsa+sa模式要不要开

5g手机从哪看出来是NSA和SA

SA网络专属流量都能干什么

SQL2000中的默认sa帐号的修改与删除方法

2022.02.21 UB

2022.02.21 SA

SQL SERVER 2008 windows、sa账户同时不能登录

sqlserver添加sa用户和密码的实现

1.1 前置知识基数排序