hdu6703 array

题意

给定一个1到\(n\)的全排列，两种操作，将\(a_{pos}\)修改为\(a_{pos}+1000000\)，询问第一个大于等于\(k\)的且不在\(a_1...a_r\)的数。

分析

由于\(k<=n\)，因此操作二询问的答案最大是\(n+1\)，因此操作一就相当于删去一个数。
考虑用权值线段树维护下标(权值区间下标最大值)，操作一就将下标置为\(n+1\)，而操作二就是在值域\([k,n]\)之间查询下标大于\(r\)的最小数。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+50;

const int INF=0x3f3f3f3f;

int T,n,m,a[N],idx[N],o,p,r,k;

struct VCT{

#define ls i<<1

#define rs i<<1|1

#define mid (l+r)/2

    int mx[N*4];

    void pushup(int i){

        mx[i]=max(mx[ls],mx[rs]);

    }

    void build(int i,int l,int r){

        if(l==r){

            mx[i]=idx[l];

            return;

        }

        build(ls,l,mid);

        build(rs,mid+1,r);

        pushup(i);

    }

    void update(int i,int l,int r,int p){

        if(l==r && l==p){

            mx[i]=n+1;

            return;

        }

        if(p<=mid){

            update(ls,l,mid,p);

        }else{

            update(rs,mid+1,r,p);

        }

        pushup(i);

    }

    //查询值域[ql,qr]中第一个大于k的下标

    int query(int i,int l,int r,int k,int x){

        if(l==r){

            return l;

        }

        int ans=n+1;

        if(k<=mid){

            if(mx[ls]>x){

                ans=min(ans,query(ls,l,mid,k,x));

                //因为要找满足条件最小的值，左子树满足直接返回

                if(ans<n+1){

                    return ans;

                }

            }

        }

        //这里不能else并列，因为进入左子树查询也有可能查到n+1

        if(mx[rs]<=x){

            return ans;

        }

        return query(rs,mid+1,r,k,x);

    }

#undef ls

#undef rs

#undef mid

}wa;

int main(){

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

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

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

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

            idx[a[i]]=i;

        }

        idx[n+1]=INF;

        n++;

        wa.build(1,1,n);

        int lst=0;

        while(m--){

            scanf("%d",&o);

            if(o==1){

                scanf("%d",&p);

                p=p^lst;

                wa.update(1,1,n,a[p]);

            }else if(o==2){

                scanf("%d%d",&r,&k);

                r=r^lst;

                k=k^lst;

                lst=wa.query(1,1,n,k,r);

                printf("%d\n",lst);

            }

        }

    }

    return 0;

}

hdu6704 K-th occurence

题意

给定一个字符串，多次询问其中一个子串第\(k\)次出现的位置。

分析

子串出现位置考虑后缀数组，第\(k\)小考虑主席树。
对于后缀数组来说，\(sa[i]\)表示后缀出现的位置，那么如果这个后缀对应的\(h[i]\)满足给定子串的长度，那就相当于这个子串出现的位置了。
所以可以二分找到这个子串出现的位置区间，然后主席树维护后缀的出现位置\(sa[i]\)，查询第\(k\)小即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+50;

int T,n,m,l,r,k,s[N];

char str[N];

int sa[N],rk[N],h[N];

int t[N],t2[N],c[N];

int tr[N];

int dp[N][25];

void build_sa(int n,int m=128){

    n++;

    int *x=t,*y=t2;

    for(int i=0;i<m;i++){

        c[i]=0;

    }

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

        c[x[i]=s[i]]++;

    }

    for(int i=1;i<m;i++){

        c[i]+=c[i-1];

    }

    for(int i=n-1;i>=0;i--){

        sa[--c[x[i]]]=i;

    }

    for(int k=1;k<=n;k<<=1){

        int p=0;

        for(int i=n-k;i<n;i++){

            y[p++]=i;

        }

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

            if(sa[i]>=k){

                y[p++]=sa[i]-k;

            }

        }

        for(int i=0;i<m;i++){

            c[i]=0;

        }

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

            c[x[y[i]]]++;

        }

        for(int i=1;i<m;i++){

            c[i]+=c[i-1];

        }

        for(int i=n-1;i>=0;i--){

            sa[--c[x[y[i]]]]=y[i];

        }

        swap(x,y);

        p=1;

        x[sa[0]]=0;

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

            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

        }

        if(p>=n){

            break;

        }

        m=p;

    }

    n--;

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

        rk[sa[i]]=i;

    }

    int k=0;

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

        if(k){

            k--;

        }

        int j=sa[rk[i]-1];

        while(s[i+k]==s[j+k]){

            k++;

        }

        h[rk[i]]=k;

    }

}

void debug(){

    //sa 0~n 包括一个特殊字符

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

        printf("%d ",sa[i]);

    }

    printf("\n");

    //rk 0~n-1 后缀[i...n-1]的排名

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

        printf("%d ",rk[i]);

    }

    printf("\n");

    //h 1~n 排名为i的后缀与排名为i-1的后缀的LCP

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

        printf("%d ",h[i]);

    }

    printf("\n");

}

struct CT{

#define mid (l+r)/2

    int tot,sum[N*30],lr[N*30],rr[N*30];

    void init(){

        tot=0;

    }

    int build(int l,int r){

        int rt=++tot;

        sum[rt]=lr[rt]=rr[rt]=0;

        if(l==r){

            return tot;

        }

        lr[rt]=build(l,mid);

        rr[rt]=build(mid+1,r);

        return rt;

    }

    int update(int pre,int l,int r,int v){

        int rt=++tot;

        sum[rt]=sum[pre]+1;

        lr[rt]=lr[pre];

        rr[rt]=rr[pre];

        if(l>=r){

            return rt;

        }

        if(v<=mid){

            lr[rt]=update(lr[pre],l,mid,v);

        }else{

            rr[rt]=update(rr[pre],mid+1,r,v);

        }

        return rt;

    }

    int query(int u,int v,int l,int r,int k){

        if(l>=r){

            return l;

        }

        if(sum[v]-sum[u]<k){

            return -1;

        }

        int lc=sum[lr[v]]-sum[lr[u]];

        if(k<=lc){

            return query(lr[u],lr[v],l,mid,k);

        }else{

            return query(rr[u],rr[v],mid+1,r,k-lc);

        }

    }

#undef mid

}ac;

void init(){

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

        dp[i][0]=h[i];

    }

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

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

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

        }

    }

}

int rmq(int l,int r){

    int k=0;

    while((1<<(k+1))<=r-l+1){

        k++;

    }

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

}

int solve(int l,int r){

    if(l==r){

        return n-sa[l];

    }

    if(l>r){

        swap(l,r);

    }

    return rmq(l+1,r);

}

int main(){

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

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        scanf("%s",str);

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

            s[i]=str[i]-'a'+1;

        }

        s[n]=0;

        build_sa(n);

//        debug();

        ac.init();

        tr[0]=ac.build(1,n);

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

            tr[i]=ac.update(tr[i-1],1,n,sa[i]+1);

        }

        init();

        while(m--){

            scanf("%d%d%d",&l,&r,&k);

            l--;

            r--;

            int len=r-l+1;

            int R=rk[l];

            int ql=R,qr=R;

            int ll=1,rr=R;

            while(ll<=rr){

                int md=(ll+rr)/2;

                if(solve(md,R)>=len){

                    ql=md;

                    rr=md-1;

                }else{

                    ll=md+1;

                }

            }

            ll=R,rr=n;

            while(ll<=rr){

                int md=(ll+rr)/2;

                if(solve(R,md)>=len){

                    qr=md;

                    ll=md+1;

                }else{

                    rr=md-1;

                }

            }

            if(qr-ql+1<k){

                printf("-1\n");

                continue;

            }

            int ans=ac.query(tr[ql-1],tr[qr],1,n,k);

            printf("%d\n",ans);

        }

    }

    return 0;

}

hdu6705 path

题意

给一个有向图，求第\(k\)小的路径。

分析

这种题似乎都是优先队列来的...
首先把所有点出边排序，最小的放进优先队列里，然后每次取出一条边\((u,v)\)，加入\(u\)的下一条边和\(v\)的第一条边(如果有的话)。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5e4+50;

struct Edge{

    int v;

    ll w;

    bool operator <(const Edge &rhs)const{

        return w<rhs.w;

    }

};

vector<Edge> g[N];

int T,n,m,q,k,u,v,w;

struct node{

    int u,id;

    ll w;

    bool operator <(const node &rhs)const{

        return w>rhs.w;

    }

};

int que[N];

ll ans[N];

priority_queue<node> pq;

int main(){

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

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&q);

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

            g[i].clear();

        }

        for(int i=1;i<=m;i++){

            scanf("%d%d%d",&u,&v,&w);

            g[u].push_back(Edge{v,1ll*w});

        }

        int mx=0;

        for(int i=1;i<=q;i++){

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

            mx=max(mx,que[i]);

        }

        while(!pq.empty()){

            pq.pop();

        }

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

            sort(g[i].begin(),g[i].end());

            if(g[i].size()>0){

                pq.push(node{i,0,g[i][0].w});

            }

        }

        int kk=0;

        //取一条加两条

        while(!pq.empty()){

            node tmp=pq.top();

            pq.pop();

            kk++;

            ans[kk]=tmp.w;

            /**

             * if(kk==que[i].k){

             *      i++;

             *      if(i>q){

             *          break;

             *      }

             * }

             * 这种写法是错的，如果有多个相同的k，只会计算第一个的答案，后面死循环

             */

            if(kk==mx){

                break;

            }

            int u=tmp.u;

            int id=tmp.id;

            int v=g[u][id].v;

            ll w=tmp.w;

            if(g[u].size()>id+1){

                pq.push(node{u,id+1,w-g[u][id].w+g[u][id+1].w});

            }

            if(g[v].size()>0){

                pq.push(node{v,0,w+g[v][0].w});

            }

        }

        for(int i=1;i<=q;i++){

            printf("%lld\n",ans[que[i]]);

        }

    }

    return 0;

}

巴特西

hdu6703_array

hdu6703 array

题意

分析

代码

hdu6704 K-th occurence

题意

分析

代码

hdu6705 path

题意

分析

代码

最新文章

热门文章