寻宝-题解

· · 题解

题意：给出一个图，存在两种边：区间连边和一些特殊的边，特殊边的边权是起点与终点编号差的绝对值乘以一个与起点编号有关的数

算法1

看到n,m都很小，暴力连边+Dijkstra即可

时间复杂度O(n^2m)

期望得分：5分

算法2

当然可以用数据结构进行区间连边，但是还有不用数据结构的做法 对于每组边，建一个中转节点，把这组边的所有起点向中转节点连一条边权为$w$的边，再从中转节点向这组边的所有终点连一条边权为$0$的边，剩下的部分还是暴力连边 时间复杂度$O(nm)

期望得分：15分

算法3

针对subtask3

发现这时区间连边变成了单点连边，而且能连特殊边的所有点，v_i都相同

考虑用分层图：

首先把单点连边部分连好，然后对于每个点建另一个节点

如果这个点能连边，那么向对应节点连一条双向边，边权为0

否则，就从对应节点向这个节点连一条边权为0的单向边

随后，将所有对应节点按顺序相连，边权为非零的v_i，这些边形成一条链

这样，特殊边都可以通过走到对应节点，然后沿着这条链前进，再回到普通节点，长度恰好满足要求

时间复杂度O(m \log n)

期望得分11分，结合算法2期望得分26分

算法4

针对subtask4

这部分没有特殊边

所以数据结构优化建图即可，注意要加中转节点，否则复杂度多一个log

时间复杂度O(m \log^2 n)

期望得分10分，结合算法2期望得分25分

算法5

针对subtask5

发现只有特殊边

直接贪心

每到一个点，根据当前边v_i值和到达点的v_i值，决定是否开始挖一条新的边，如果到达的点v_i较小，就挖新的边

这时候，往回挖一定不是最优解，因为可以在到达那个点时就挖新的隧道，往回挖只会导致重复经过某条隧道，浪费时间

期望得分12分，结合算法2期望得分27分

算法6

针对subtask9

区间连边按照算法4做，这部分没问题

然后考虑特殊边

考虑批量增广：李超树

当从堆中取出一个v_i \neq 0的点时，发现到其它所有节点的最小值都和一个特定值取了min

这个值在左半边是递减的等差数列，右半边是递增的等差数列

所以，对李超树作一些修改，用它代替堆

需要维护：

取出最小值以及位置，并删除这个点

区间与一个等差数列取min

对于李超树上的一个节点，记录这个点维护区间内编号最小和最大的点，以及区间内最小值，并记录区间内点是否全部被删除

当一个节点维护的整个区间需要与一个等差数列取min时，根据新的等差数列与原有等差数列的情况处理

如果每个区间内的位置，都满足一个数列比另一个数列大，那么就换掉一个数列

否则，比较中心点，中心点位置值小的留下来，大的则选择可能更优的一边递归处理

随后，用数列更新区间内最小值

对于区间与等差数列取min，先按普通线段树递归到对应节点，然后按上面的方法处理

对于取出位置，根据两个孩子节点最小值的大小关系，到达对应的孩子，取出值并加上删除标记

这样，就能用这个李超树代替堆了

当然，也可以用堆/线段树处理普通边，需要根据两个数据结构中最小值决定取出哪一部分的节点

时间复杂度取决于具体实现方法

std使用ST表优化区间连边，用线段树维护普通边部分，时间复杂度：O(n \log ^2 n + m\log n)

期望得分：100分

p.s:出题人写题解时突然意识到Subtask6-8原来的部分分算法可能有问题，于是就没写这部分的做法

AC代码：

#include<cstdio>
const int N=200007;
const bool DEBUG=0;
const long long INF=(1LL<<62)-1;
long long read(){
    long long num=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return num;
}
char res[25];
void write(long long num){
    if(num==0){putchar('0');return;}
    if(num<0){putchar('-');num=-num;}
    int t=0;
    while(num){res[t++]=num%10+'0';num/=10;}
    while(t--)putchar(res[t]);
}
template<typename T>
T min(T a,T b){
    if(a<b)return a;
    return b;
}

int n,m;
long long v[N];
int head[N*40],next[N*44],ver[N*44],tot;
long long edge[N*44];
long long dis[N*40];
int fr[N*40];
void add(int a,int b,long long w){
    tot++;
    edge[tot]=w;
    ver[tot]=b;
    next[tot]=head[a];
    head[a]=tot;
}

int log2[N];
#define gid1(x,k) ((k)*n+(x))
#define gid2(x,k) ((k)*n+(x)+n*20)
#define maxid (n*40+1)
void gen(){
    for(int k=0;;k++){
        for(int i=(1<<k);i<(1<<(k+1))&&i<=n;i++){
            log2[i]=k;
        }
        if((1<<(k+1))>n)break;
    }
    for(int i=1;i<=n;i++){
        add(gid2(i,0),gid1(i,0),0);
    }
    for(int k=0;;k++){
        if((1<<k)>n)break;
        for(int i=1;i<=n-(1<<k);i++){
            add(gid1(i,k),gid1(i,k+1),0);
            add(gid1(i+(1<<k),k),gid1(i,k+1),0);
            add(gid2(i,k+1),gid2(i,k),0);
            add(gid2(i,k+1),gid2(i+(1<<k),k),0);
        }
    }
}
void radd(int l1,int r1,int l2,int r2,long long w){
    int len1=r1-l1+1;
    int k1=log2[len1];
    int p11=gid1(l1,k1);
    int p12=gid1(r1+1-(1<<k1),k1);

    int len2=r2-l2+1;
    int k2=log2[len2];
    int p21=gid2(l2,k2);
    int p22=gid2(r2+1-(1<<k2),k2);

    add(p11,p21,w);
    add(p12,p21,w);
    add(p11,p22,w);
    add(p12,p22,w);
}
#define gmid() int mid=((ll+rr)>>1)
int resp;
namespace seg1{
    long long minn[N*40*4];
    int fr[N*40*4];
    void clr(int id,int ll,int rr){
        minn[id]=INF;
        if(ll==rr)return;
        gmid();
        clr(id<<1,ll,mid);
        clr((id<<1)|1,mid+1,rr);
    }
    void pushup(int id,int ll,int rr){
        minn[id]=min(minn[id<<1],minn[(id<<1)|1]);
    }
    void pset(int pl,long long num,int f,int id,int ll,int rr){
        if(ll==rr){
            if(minn[id]>num){
                minn[id]=num;
                fr[id]=f;
            }
            return;
        }
        gmid();
        if(pl<=mid)pset(pl,num,f,id<<1,ll,mid);
        else pset(pl,num,f,(id<<1)|1,mid+1,rr);
        pushup(id,ll,rr);
    }
    int gid(int id,int ll,int rr){
        if(ll==rr){
            minn[id]=INF;
            resp=fr[id];
            return ll;
        }
        gmid();
        int ans;
        if(minn[id<<1]<minn[(id<<1)|1])ans=gid(id<<1,ll,mid);
        else ans=gid((id<<1)|1,mid+1,rr);
        pushup(id,ll,rr);
        return ans;
    }
}
namespace seg2{
    #undef maxid
    int maxid[N*4],minid[N*4],fr[N*4];
    long long minn[N*4],k[N*4],b[N*4];
    bool del[N*4];
    int resid,resfr;long long resdis;
    void build(int id,int ll,int rr){
        k[id]=0;
        b[id]=INF;
        maxid[id]=rr;
        minid[id]=ll;
        del[id]=0;
        minn[id]=INF;
        fr[id]=0;
        if(ll==rr){
            return;
        }
        int mid=((ll+rr)>>1);
        build(id<<1,ll,mid);
        build((id<<1)|1,mid+1,rr);
    }
    void pushup(int id,int ll,int rr){
        if(ll==rr){
            if(del[id])return;
            maxid[id]=minid[id]=ll;
            minn[id]=k[id]*ll+b[id];
            return;
        }
        if(del[id<<1]&&del[(id<<1)|1]){
            del[id]=1;
            minn[id]=INF;
            return;
        }
        if(!del[id<<1])minid[id]=minid[id<<1];
        else minid[id]=minid[(id<<1)|1];

        if(!del[(id<<1)|1])maxid[id]=maxid[(id<<1)|1];
        else maxid[id]=maxid[id<<1];

        minn[id]=INF;
        if(!del[id<<1])minn[id]=min(minn[id],minn[id<<1]);
        if(!del[(id<<1)|1])minn[id]=min(minn[id],minn[(id<<1)|1]);
        if(b[id]!=INF){
            if(k[id]>0)minn[id]=min(minn[id],k[id]*minid[id]+b[id]);
            else minn[id]=min(minn[id],k[id]*maxid[id]+b[id]);
        }
    }
    void addseq(int id,int ll,int rr,long long nk,long long nb,int f){
        if(del[id])return;
        if(b[id]==INF){
            k[id]=nk;
            b[id]=nb;
            fr[id]=f;
            pushup(id,ll,rr);
            return;
        }
        long long lp,ln,rp,rn;
        lp=k[id]*minid[id]+b[id];
        ln=nk*minid[id]+nb;
        rp=k[id]*maxid[id]+b[id];
        rn=nk*maxid[id]+nb;
        if(lp<=ln&&rp<=rn)return;
        if(lp>=ln&&rp>=rn){
            k[id]=nk;
            b[id]=nb;
            fr[id]=f;
            pushup(id,ll,rr);
            return;
        }
        int mid=((ll+rr)>>1);
        long long mp,mn;
        mp=k[id]*mid+b[id];
        mn=nk*mid+nb;
        if(mp>=mn){
            if(lp>=ln){
                addseq((id<<1)|1,mid+1,rr,k[id],b[id],fr[id]);
            }else{
                addseq(id<<1,ll,mid,k[id],b[id],fr[id]);
            }
            k[id]=nk;
            b[id]=nb;
            fr[id]=f;
        }else{
            if(rp>=rn){
                addseq((id<<1)|1,mid+1,rr,nk,nb,f);
            }else{
                addseq(id<<1,ll,mid,nk,nb,f);
            }
        }
        pushup(id,ll,rr);
        return;
    }
    void pushdown(int id,int ll,int rr){
        if(del[id])return;
        if(b[id]==INF)return;
        if(ll==rr)return;
        int mid=((ll+rr)>>1);
        addseq(id<<1,ll,mid,k[id],b[id],fr[id]);
        addseq((id<<1)|1,mid+1,rr,k[id],b[id],fr[id]);
        k[id]=0;
        b[id]=INF;
        fr[id]=0;
        pushup(id,ll,rr);
        return;
    }
    void gid(int id,int ll,int rr){
        if(ll==rr){
            resdis=minn[id];
            resfr=fr[id];
            resid=ll;
            del[id]=1;
            minn[id]=INF;
            return;
        }
        pushdown(id,ll,rr);
        int mid=((ll+rr)>>1);
        if(del[(id<<1)|1]||minn[id<<1]<minn[(id<<1)|1]){
            gid(id<<1,ll,mid);
        }else{
            gid((id<<1)|1,mid+1,rr);
        }
        pushup(id,ll,rr);
    }
    void change(int id,int ll,int rr,int l,int r,long long nk,long long nb,int f){
        if(l<=ll&&rr<=r){
            addseq(id,ll,rr,nk,nb,f);
            return;
        }
        if(r<ll||rr<l)return;
        if(del[id])return;
        pushdown(id,ll,rr);
        int mid=((ll+rr)>>1);
        change(id<<1,ll,mid,l,r,nk,nb,f);
        change((id<<1)|1,mid+1,rr,l,r,nk,nb,f);
        pushup(id,ll,rr);
    }
    #define maxid (n*40+1)
}
int ans[N],c;
int main(){
    n=read();m=read();
    gen();
    for(int i=1;i<=n;i++)v[i]=read();
    while(m--){
        int l1,r1,l2,r2;long long w;
        l1=read();r1=read();l2=read();r2=read();w=read();
        radd(l1,r1,l2,r2,w);
    }
    dis[1]=0;
    for(int i=2;i<=maxid;i++)dis[i]=INF;
    seg1::clr(1,1,maxid);
    seg1::pset(1,0,-1,1,1,maxid);
    seg2::build(1,1,n);
    while(seg1::minn[1]!=INF||seg2::minn[1]!=INF){
        int cur;
        if(seg1::minn[1]>=seg2::minn[1]){
            seg2::gid(1,1,n);
            cur=seg2::resid;
            if(fr[cur])continue;
            fr[cur]=seg2::resfr;
            dis[cur]=seg2::resdis;
        }else{
            cur=seg1::gid(1,1,maxid);
            if(fr[cur])continue;
            fr[cur]=resp;
        }
        if(cur==n)break;
        for(int i=head[cur];i;i=next[i]){
            if(dis[ver[i]]>dis[cur]+edge[i]){
                dis[ver[i]]=dis[cur]+edge[i];
                seg1::pset(ver[i],dis[ver[i]],cur,1,1,maxid);
            }
        }
        if(cur<=n&&v[cur]!=0){
            if(cur!=1)seg2::change(1,1,n,1,cur-1,-v[cur],dis[cur]+v[cur]*cur,cur);
            if(cur!=n)seg2::change(1,1,n,cur+1,n,v[cur],dis[cur]-v[cur]*cur,cur);
        }
    }
    if(dis[n]==INF){
        puts("-1");
        return 0;
    }
    write(dis[n]);
    putchar('\n');
    for(int i=n;i!=-1;i=fr[i]){
        if(i<=n)ans[c++]=i;
    }
    write(c);
    putchar('\n');
    for(int i=c-1;i>=0;i--){
        write(ans[i]);
        putchar(' ');
    }
    if(DEBUG)return 1;
}