rt

之前找 lcp 时写的二分 TLE on #14，改成线段树上维护左端点最长 1 段就 WA on #10 了，求助一下哪里写挂了

提交记录

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define N 200005
#define LL long long
#define MOD 1000000007

using namespace std;
int n,m,S,T; LL mul[N];

int cnt,head[N];
struct Node { int to,nxt,dis; }e[N];

void add(int u,int v,int w) { e[++cnt]=Node{v,head[u],w},head[u]=cnt; }

int tcnt,rt[N];
struct Tree { LL sum; int len,siz,ls,rs; }t[N<<7];

void upd(int &x,int y,int l,int r,int pos) {
    t[x=++tcnt]=t[y]; t[x].siz=(r-l+1);
    if (l==r) return t[x].sum=mul[l],t[x].len=1,void();
    int mid=(l+r>>1);
    if (pos<=mid) upd(t[x].ls,t[y].ls,l,mid,pos);
    else upd(t[x].rs,t[y].rs,mid+1,r,pos);
    t[x].sum=(t[t[x].ls].sum+t[t[x].rs].sum)%MOD;
    if (t[x].ls and t[t[x].ls].siz)
        t[x].len=(t[t[x].ls].len==t[t[x].ls].siz?t[t[x].ls].len+t[t[x].rs].len:t[t[x].ls].len);
    else t[x].len=0;
}

void upd(int &x,int y,int l,int r,int L,int R) {
    if (L<=l and r<=R) return x=0,void();
    t[x=++tcnt]=t[y]; t[x].siz=(r-l+1);
    int mid=(l+r>>1);
    if (L<=mid) upd(t[x].ls,t[y].ls,l,mid,L,R);
    if (R>mid) upd(t[x].rs,t[y].rs,mid+1,r,L,R);
    t[x].sum=(t[t[x].ls].sum+t[t[x].rs].sum)%MOD;
    if (t[x].ls and t[t[x].ls].siz)
        t[x].len=(t[t[x].ls].len==t[t[x].ls].siz?t[t[x].ls].len+t[t[x].rs].len:t[t[x].ls].len);
    else t[x].len=0;
}

bool ask(int x,int l,int r,int pos) {
    if (!x) return 0;
    if (l==r) return 1;
    int mid=(l+r>>1);
    if (pos<=mid) return ask(t[x].ls,l,mid,pos);
    else return ask(t[x].rs,mid+1,r,pos);
}

Tree pushup(Tree a,Tree b) { return {(a.sum+b.sum)%MOD,(a.siz?(a.len==a.siz?a.len+b.len:a.len):0),a.siz+b.siz,0,0}; }

Tree find(int x,int l,int r,int L,int R) {
    if (!x or L>R or R<l or L>r) return t[0];
    if (L<=l and r<=R) return t[x];
    int mid=(l+r>>1);
    if (R<=mid) return find(t[x].ls,l,mid,L,R);
    else if (L>mid) return find(t[x].rs,mid+1,r,L,R);
    else return pushup(find(t[x].ls,l,mid,L,R),find(t[x].rs,mid+1,r,L,R));
}

bool cmp(int x,int y,int l,int r) {
    if (!x) return 0;
    if (!y) return 1;
    if (l==r) return t[x].len>t[y].len;
    int mid=(l+r>>1);
    if (t[t[x].rs].sum==t[t[y].rs].sum 
    and t[t[x].rs].len==t[t[y].rs].len
    and t[t[x].rs].siz==t[t[y].rs].siz)
        return cmp(t[x].ls,t[y].ls,l,mid);
    else return cmp(t[x].rs,t[y].rs,mid+1,r);
}

void Add(int &x,int y,int w,int u,int v) {
    if (!ask(y,0,N-1,w)) upd(x,y,0,N-1,w);
    else {
        Tree tmp=find(y,0,N-1,w,N-1);
        int res=tmp.len+w-1;
        // printf("sum: %lld len: %d siz: %d\n",tmp.sum,tmp.len,tmp.siz);
        // printf("u: %d v: %d (%d, %d) %lld\n",u,v,w,res,t[y].sum);
        // if (!ask(y,0,N-1,res) or ask(y,0,N-1,res+1)) exit(-1);
        upd(x,y,0,N-1,w,res); upd(x,x,0,N-1,res+1);
    }
}

struct Q {
    int u,rt;

    bool operator<(const Q tmp) const { return cmp(rt,tmp.rt,0,N-1); }
};

LL dis[N]; bool vis[N]; int to[N];
priority_queue<Q> q;

void dij() {
    memset(dis,-1,sizeof dis);
    memset(vis,0,sizeof vis);
    q.push({S,rt[S]=++tcnt}); dis[S]=0;
    while (!q.empty()) {
        int u=q.top().u; q.pop();
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].to,w=e[i].dis,tmp;
            Add(tmp,rt[u],w,u,v);
            if (Q{0,rt[v]}<Q{0,tmp} or dis[v]==-1) {
                // printf("u: (%d, %lld, %lld) v: (%d, %lld)\n",u,t[tmp].sum,t[rt[u]].sum,v,dis[v]);
                dis[v]=t[tmp].sum,rt[v]=tmp,to[v]=u;
                q.push({v,rt[v]});
            }
        }
    }
}

void dfs(int u,int dep) {
    if (!u) return printf("%d\n",dep),void();
    dfs(to[u],dep+1);
    printf("%d ",u);
}

int main() {
    scanf("%d%d",&n,&m);
    mul[0]=1; for (int i=1;i<N;i++) mul[i]=mul[i-1]*2%MOD;
    for (int i=1,u,v,w;i<=m;i++) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w); add(v,u,w);
    }
    scanf("%d%d",&S,&T);
    dij();
    if (dis[T]==-1) printf("-1\n");
    else {
        printf("%lld\n",dis[T]);
        dfs(T,0); printf("\n");
    }
    return 0;
}