7/26 thinking +dp+ suffix array learning

C. The Third Problem

The question : Given an array a, Array required a And an array b be similar , Similar requirements : For any interval , The minimum nonnegative integer values of the two arrays are the same , Ask how many arrays meet the requirements b
Ideas ：
1. Record array a in 0~n-1 The subscript position of the value ;
2. from 0 To n-1 enumeration i, And record 0 To i-1 The leftmost and rightmost endpoints of the number of occurrences [L,R]
3. if a[i] Appear in number i-1 In the leftmost and rightmost endpoints of , be r-l+1（ The number of numbers , Interval length ）-i( Number of fixed position values )

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n,a[N];

signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            int x;cin>>x;
            a[x]=i;
        }
        int l=N,r=-1,ans=1;
        for(int i=0;i<n;i++)
        {
    
            if(a[i]>=l&&a[i]<=r)
                ans*=(r-l+1-i),ans%=mod;
            l=min(a[i],l); // Record a[i] Left and right endpoint values of 
            r=max(a[i],r);
            //cout<<l<<" "<<r<<" "<<ans<<endl;
        }
        cout<<ans<<endl;
    }
	return 0;
}

D. Increase Sequence

The question ： Will array a The values in are converted to h, And the left and right intervals can only appear once .
Ideas ：
1. If the difference between adjacent numbers of the array is greater than 1, Then there is no method to meet the meaning of the question ;a[i]=h-x
2. Set the state of :dp[i] Express the a[1]~a[i] All become 0 Minimum number of operations
3. State shift :
d=0, The available operands are a[i]+1（1 It means that i-1 Out end , stay i Out start ）
d=-1, The available operands are a[i-1], stay i-1 At the end of
d==1, Need to open a new section ,dp[i]=dp[i-1]

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n,h,a[N],dp[2005];  //dp[i] Express the a[1]~a[i] All become 0 Minimum number of operations 

signed main()
{
    
    cin>>n>>h;
    for(int i=1;i<=n;i++)
    {
    
        int x;cin>>x;
        a[i]=h-x;
    }
    dp[0]=1;
    int flag=0;
    n++;
    for(int i=1;i<=n;i++)
    {
    
        int res=a[i]-a[i-1];
        if(abs(res)>=2)
            flag=1;
        if(res==0)
            dp[i]=dp[i-1]*(a[i]+1)%mod;
        if(res==-1)
            dp[i]=dp[i-1]*a[i-1]%mod;
        if(res==1)
            dp[i]=dp[i-1];
    }
    if(flag)
        cout<<0<<endl;
    else
        cout<<dp[n]<<endl;
	return 0;
}

The suffix array

Templates ：( Annotations are in the code )

const int N=1e5+5;
const int mod=1e9+7;
int n,k;
int rk[N];   // With i Ranking of the beginning suffix 
char s[N]; 
int sa[N];   // Express sa[i] Indicates the ranking i The beginning subscript of the suffix of 

// Solve each with i Rank of suffix string for starting subscript 
bool cmp(int i,int j)
{
    
    if(rk[i]!=rk[j])
        return rk[i]<rk[j];
    int ri=(i+k<=n ? rk[i+k]:-1);
    int rj=(i+k<=n ? rk[j+k]:-1);
    return ri<rj
}
void getsa(int n,char *str)
{
    
    int rk2[N];
    for(int i=1;i<=n;i++)
        sa[i]=i,rk[i]=s[i];  // utilize ASCLL code 
    for(k=1;k<=n;k*=2)
    {
    
        sort(sa+1,sa+1+n;cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++)
            rk2[sa[i]]=rk2[[sa[i-1]]]+cmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++)
            rk[i]=rk2[i];
    }
}

int ht[N]   // Maintain array rk Two adjacent suffixes lcp(i-1 and i The longest public prefix of )
void getht(int n,char *s)
{
    
    for(int i=1;i<=n;i++)
        rk[sa[i]]=1;
    int h=0;
    ht[1]=0;
    for(int i=1;i<=n;i++)
    {
    
        int j=sa[rk[i]-1];
        if(h>0)
            h--;
        for(;j+h<=n&&i+h<=n;h++)
            if(s[j+n]!=s[i+h])
                break;
        ht[rk[i]]=h;
    }
}

P4248 [AHOI2013] differences

The knowledge used in this question ： The suffix array + Monotonic stack
i and j The longest public prefix of ：i~j Within the interval ht[i] The minimum value of
tricks ： The sum of the interval minimum values of each interval , Use monotone stack to solve .
ll[i]: It means looking to the left , Less than or equal to h[i] The subscript position of
rr[i]: From i Look to the right , Less than or equal to h[i] The subscript position of
Calculate h[i] The number of intervals that are the minimum is :(i-ll[i])*(rr[i]-i)
Maybe the data has been updated , This practice will re, The reason lies in cmp The sorting rules of add complexity .

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+5;
const int mod=1e9+7;
int n,k;
int rk[N],rk2[N];   // With i Ranking of the beginning suffix 
char s[N];
int sa[N];   // Express sa[i] Indicates the ranking i The beginning subscript of the suffix of 

// Solve each with i Rank of suffix string for starting subscript 
bool cmp(int i,int j)
{
    
    if(rk[i]!=rk[j])
        return rk[i]<rk[j];
    int ri=(i+k<=n ? rk[i+k]:-1);
    int rj=(j+k<=n ? rk[j+k]:-1);
    return ri<rj;
}
void getsa(int n,char *str)
{
    
    for(int i=1;i<=n;i++)
        sa[i]=i,rk[i]=s[i];  // utilize ASCLL code 
    for(k=1;k<=n;k*=2)
    {
    
        sort(sa+1,sa+1+n,cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++)
            rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++)
            rk[i]=rk2[i];
    }
}

int ht[N];   // Maintain array rk Two adjacent suffixes lcp(i-1 and i The longest public prefix of )
void getht(int n,char *s)
{
    
    for(int i=1;i<=n;i++)
        rk[sa[i]]=i;
    int h=0;
    ht[1]=0;
    for(int i=1;i<=n;i++)
    {
    
        int j=sa[rk[i]-1];
        if(h>0)
            h--;
        for(;j+h<=n&&i+h<=n;h++)
            if(s[j+h]!=s[i+h])
                break;
        ht[rk[i]]=h;
    }
}
int top,ll[N],rr[N],sk[N],ans;
signed main()
{
    
    scanf("%s",s+1);
    n=strlen(s+1);
    getsa(n,s);
    getht(n,s);
    top=1,sk[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        while(top&&ht[sk[top]]>ht[i])
            rr[sk[top]]=i,top--;
        ll[i]=sk[top];
        sk[++top]=i;
    }
    while(top)
        rr[sk[top]]=n+1,top--;
    ans=n*(n-1)*(n+1)*1ll/2;
    for(int i=1;i<=n;i++)
        ans-=2*(i-ll[i])*(rr[i]-i)*ht[i];
    printf("%lld\n",ans);
	return 0;
}

P3809 【 Templates 】 Suffix sort

For each subscript i After sorting the suffixes of , The output rank is i The subscript of the first character of

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int n,k;
int rk[N],rk2[N];   // With i Ranking of the beginning suffix 
char s[N];
int sa[N];   // Express sa[i] Indicates the ranking i The beginning subscript of the suffix of 

// Solve each with i Rank of suffix string for starting subscript 
bool cmp(int i,int j)
{
    
    if(rk[i]!=rk[j])
        return rk[i]<rk[j];
    int ri=(i+k<=n ? rk[i+k]:-1);
    int rj=(j+k<=n ? rk[j+k]:-1);
    return ri<rj;
}
void getsa(int n,char *str)
{
    
    for(int i=1;i<=n;i++)
        sa[i]=i,rk[i]=s[i];  // utilize ASCLL code 
    for(k=1;k<=n;k*=2)
    {
    
        sort(sa+1,sa+1+n,cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++)
            rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++)
            rk[i]=rk2[i];
    }
}

int ht[N];   // Maintain array rk Two adjacent suffixes lcp(i-1 and i The longest public prefix of )
void getht(int n,char *s)
{
    
    for(int i=1;i<=n;i++)
        rk[sa[i]]=i;
    int h=0;
    ht[1]=0;
    for(int i=1;i<=n;i++)
    {
    
        int j=sa[rk[i]-1];
        if(h>0)
            h--;
        for(;j+h<=n&&i+h<=n;h++)
            if(s[j+h]!=s[i+h])
                break;
        ht[rk[i]]=h;
    }
}
int top,ll[N],rr[N],sk[N],ans;
signed main()
{
    
    scanf("%s",s+1);
    n=strlen(s+1);
    getsa(n,s);
    for(int i=1;i<=n;i++)
        printf("%lld ",sa[i]);
    printf("\n");
    //getht(n,s);

	return 0;
}