8-1作业/重写ren_gao_zu

· · 个人记录

作业

P1816 忠诚

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,a[N],lg[N];
int f[N][25];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i][0]=a[i];
    }
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        int j=lg[len];
        if(f[l][j]>f[r-(1<<j)+1][j])cout<<f[r-(1<<j)+1][j]<<" ";
        else cout<<f[l][j]<<" ";
    }
    return 0;
}

P1440 求m区间内的最小值

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e6+5;
int n,m,a[N];
int lg[N],f[N][30];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i][0]=a[i];
    }
    for(int j=1;j<=25;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++){
        int l,r;
        r=i-1;
        if(r>=m)l=r-m+1;
        else l=1;
        int len=r-l+1,j=lg[len];
        if(f[l][j]>f[r-(1<<j)+1][j])cout<<f[r-(1<<j)+1][j]<<endl;
        else cout<<f[l][j]<<endl;
    }
    return 0;
}

CF622C Not Equal on a Segment

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,a[N],lg[N],xiao[N][25],da[N][25];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>a[1];
    xiao[1][0]=1;
    da[1][0]=1;
    for(int i=2;i<=n;i++){
        cin>>a[i];
        xiao[i][0]=i;
        da[i][0]=i;
        lg[i]=lg[i/2]+1;
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            int a1=xiao[i][j-1],b1=xiao[i+(1<<j-1)][j-1],a2=da[i][j-1],b2=da[i+(1<<j-1)][j-1];
            if(a[a1]>a[b1])xiao[i][j]=b1;
            else xiao[i][j]=a1;
            if(a[a2]>a[b2])da[i][j]=a2;
            else da[i][j]=b2;
        }
    }
    while(m--){
        int l,r,x;
        cin>>l>>r>>x;
        int len=r-l+1,j=lg[len],mi,ma;
        if(a[xiao[l][j]]>a[xiao[r-(1<<j)+1][j]]){
            mi=xiao[r-(1<<j)+1][j];
        }
        else mi=xiao[l][j];
        if(a[da[l][j]]>a[da[r-(1<<j)+1][j]]){
            ma=da[l][j];
        }
        else ma=da[r-(1<<j)+1][j];
        if(a[ma]==x&&a[mi]==x)cout<<-1<<endl;
        else if(a[ma]!=x)cout<<ma<<endl;
        else if(a[mi]!=x)cout<<mi<<endl;
    }
    return 0;
}

重写

P2412 查单词

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,m,lg[100005];
string f[N][20],a[N];
map<string,string>mp; 
string xiao(string s){
    string x=s;
    for(int i=0;i<x.size();i++){
        if(x[i]>='A'&&x[i]<='Z')x[i]+=' ';
    }
    return x;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]=xiao(a[i]);
    }
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            string s1=f[i][j-1];
            string s2=f[i+(1<<(j-1))][j-1];
            if(mp[s1]>mp[s2])f[i][j]=f[i][j-1];
            else f[i][j]=f[i+(1<<(j-1))][j-1];
        }
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        int j=lg[len];
        string ans;
        if(mp[f[l][j]]>mp[f[r-(1<<j)+1][j]])ans=f[l][j];
        else ans=f[r-(1<<j)+1][j];
        cout<<ans<<endl;
    }
    return 0;
}

P1198 [JSOI2008] 最大数

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,m,d,t,f[N][20],a[N],lg[N];
int cinn(int l,int r){
    int j=lg[r-l+1];
    int ans;
    ans=max(f[l][j],f[r-(1<<j)+1][j]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>m>>d;
    for(int i=2;i<=m;i++)lg[i]=lg[i/2]+1;
    while(m--){
        char c;
        int x;
        cin>>c>>x;
        if(c=='A'){
            n++;
            a[n]=(t+x)%d;
            int j=0;
            while((1<<j)<=n){
                int i=n-(1<<j)+1;
                if(j==0)f[i][j]=a[n];
                else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
                j++;
            }
        }
        if(c=='Q'){
            t=cinn(n-x+1,n);
            cout<<t<<endl;
        }

    }

    return 0;
}