建网站怎么分类,长沙市做网站,手机平台,wordpress 空间CF464E The Classic Problem \(\bigstar\texttt{Hint}\)#xff1a;发现没有什么好的突破口#xff1f;为什么不想想怎样才能实现题目中 \(2^x\) 的加减法呢#xff1f; 可见每次加减法#xff0c;我们要做的是将添加的 \(1\) 和右边的连续的 \(1\) 合并为一整段#xff0… CF464E The Classic Problem \(\bigstar\texttt{Hint}\)发现没有什么好的突破口为什么不想想怎样才能实现题目中 \(2^x\) 的加减法呢 可见每次加减法我们要做的是将添加的 \(1\) 和右边的连续的 \(1\) 合并为一整段可以用线段树 \(\mathcal{O(\log n)}\) 实现。 怎样比较大小呢考虑如何找到两个串第一个不同的位置则我们需要的就是二分区间、比较这两段区间是否相同。用一个 Hash 即可。 然后就成为了屎题 #define Maxn 100005
#define Maxm 1800005
#define mod 1000000007
int n,m,s,t,tot,MAX,tp,All;
int uu[Maxn],vv[Maxn],dd[Maxn],Pow2[Maxm];
int hea[Maxn],nex[Maxn1],ver[Maxn1],edg[Maxn1];
int pre[Maxn],sta[Maxn];
bool vis[Maxn];
inline void add(int x,int y,int d){ ver[tot]y,nex[tot]hea[x],hea[x]tot,edg[tot]d; }
struct TREE
{int Hash,ls,rs,rmost,laz; // pushdown !!!!TREE(int H0,int Ls0,int Rs0,int Rmost-1,int Laz-1):Hash(H),ls(Ls),rs(Rs),rmost(Rmost),laz(Laz){}inline void Push(int x,int nl,int nr){if(x0) Hash0,rmostnr,lazx;else Hash(Pow2[nr-nl1]-1mod)%mod,rmost-1,lazx;}
}tree[Maxm4];
inline void pushdown(int p,int nl,int nr)
{if(tree[p].laz!-1){int mid(nlnr)1;tree[p].lsAll,tree[tree[p].ls].Push(tree[p].laz,nl,mid);tree[p].rsAll,tree[tree[p].rs].Push(tree[p].laz,mid1,nr);tree[p].laz-1;}
}
inline void pushup(int p,int nl,int nr)
{int lsontree[p].ls,rsontree[p].rs,mid(nlnr)1;tree[p].Hash(1ll*tree[lson].Hash*Pow2[nr-mid]%modtree[rson].Hash)%mod;tree[p].rmostmax(tree[lson].rmost,tree[rson].rmost);
}
bool Comp(int pl,int pr,int nl,int nr)
{if(nlnr) return tree[pl].Hashtree[pr].Hash;pushdown(pl,nl,nr),pushdown(pr,nl,nr);int mid(nlnr)1;if(tree[tree[pl].ls].Hash!tree[tree[pr].ls].Hash)return Comp(tree[pl].ls,tree[pr].ls,nl,mid);else return Comp(tree[pl].rs,tree[pr].rs,mid1,nr);
}
int Find(int p,int nl,int nr,int l,int r)
{if(nll nrr) return tree[p].rmost;pushdown(p,nl,nr);int mid(nlnr)1,ret-inf;if(midl) retmax(ret,Find(tree[p].ls,nl,mid,l,r));if(midr) retmax(ret,Find(tree[p].rs,mid1,nr,l,r));return ret;
}
bool Check0(int p,int nl,int nr,int x)
{if(nlnr) return tree[p].Hash0;pushdown(p,nl,nr);int mid(nlnr)1;if(midx) return Check0(tree[p].ls,nl,mid,x);return Check0(tree[p].rs,mid1,nr,x);
}
void change(int pl,int pr,int nl,int nr,int l,int r,int x)
{if(nll nrr) { tree[pr].Push(x,nl,nr); return; }pushdown(pl,nl,nr);tree[pr]tree[pl];int mid(nlnr)1;if(midl)tree[pr].lsAll,tree[All]tree[tree[pl].ls],change(tree[pl].ls,tree[pr].ls,nl,mid,l,r,x);if(midr)tree[pr].rsAll,tree[All]tree[tree[pl].rs],change(tree[pl].rs,tree[pr].rs,mid1,nr,l,r,x);pushup(pr,nl,nr);
}
struct NODE
{int num,dist_rt;NODE(int N0,int D0):num(N),dist_rt(D){}bool friend operator (NODE x,NODE y){ return Comp(y.dist_rt,x.dist_rt,1,MAX); }int friend operator (NODE p,int x){int n2All;if(Check0(p.dist_rt,1,MAX,x)) change(p.dist_rt,n2,1,MAX,x,x,1);else{int posFind(p.dist_rt,1,MAX,1,x),n1All;change(p.dist_rt,n1,1,MAX,pos1,x,0);change(n1,n2,1,MAX,pos,pos,1);}return n2;}
}ds[Maxn];
inline void Short_path()
{priority_queueNODE q;ds[s]NODE(s,1);for(int i1;in;i) if(i!s) ds[i]NODE(i,2);q.emplace(s,0);while(!q.empty()){NODE curq.top(); q.pop();int Nowcur.num;if(vis[Now]) continue;vis[Now]true;for(int ihea[Now];i;inex[i]){NODE tmpNODE(ver[i],ds[Now]edg[i]);if(ds[ver[i]]tmp)ds[ver[i]]tmp,pre[ver[i]]Now,q.push(ds[ver[i]]);}}
}
int main()
{nrd(),mrd(),All2;for(int i1;im;i) uu[i]rd(),vv[i]rd(),dd[i]rd(),MAXmax(MAX,dd[i]);MAXMAX*log2(n)1000;for(int i1;im;i)add(uu[i],vv[i],MAX-dd[i]),add(vv[i],uu[i],MAX-dd[i]);srd(),trd(),Pow2[0]1;for(int i1;iMAX;i) Pow2[i]Pow2[i-1]*2%mod;if(st) { printf(0\n1\n%d\n,s); return 0; }memset(pre,-1,sizeof(pre));tree[1].Push(0,1,MAX);tree[2].Push(1,1,MAX);Short_path();if(pre[t]-1) printf(-1\n);else{sta[tp]t;for(int xpre[t];x!-1;xpre[x]) sta[tp]x;printf(%d\n%d\n,tree[ds[t].dist_rt].Hash,tp);for(int itp;i1;i--) printf(%d ,sta[i]);printf(\n);}return 0;
}
