话说我当时一开始想的是dijkstra
先求出每个点到x的最长的边的长度,然后存入一个数组,离散化,最后每次二分查询就可以了
code
#include<bits/stdc++.h> using namespace std; #define ll long long #define N 500050 ll n,m,opt,x,dis[N],pre,vis[N],head[N],len,cnt,a[N],sum1[N],tot[N],qq,sum2[N],mod; int us[N]; struct node{ int c,id; }nod[N]; struct edge{ int v,nxt; ll w; }e[N<<1]; priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > >q; inline void dijkstra(){ memset(dis,9999999,sizeof dis); dis[x]=0; q.push(make_pair(dis[x],x)); while(!q.empty()){ int k=q.top().second; q.pop(); if(vis[k])continue; vis[k]=1; for(int i=head[k];i;i=e[i].nxt){ int v=e[i].v; if(dis[v]>max(e[i].w,dis[k])){ dis[v]=max(e[i].w,dis[k]); q.push(make_pair(dis[v],v)); } } } } inline void adde(int x,int y,int z){ e[++cnt].v=y; e[cnt].nxt=head[x]; e[cnt].w=z; head[x]=cnt; } inline ll read(){ ll x=0,f=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } inline bool cmp(node x,node y){ return dis[x.id]<dis[y.id]; } inline ll check(ll x){ int l=1,r=n; while(l<r){ int mid=(l+r)>>1; if(a[mid]<x)l=mid+1; else r=mid; } if(a[l]==x){ while(a[l]==a[l+1]&&l)++l; return sum1[l]; } while(a[l]==a[l-1]&&l)--l; return sum1[l-1]+(x-a[l-1])*tot[l-1]; } int main(){ n=read(),m=read(),qq=read(),x=read(),opt=read(); if(opt==0){ for(int i=1;i<=n;++i){ nod[i].c=read(),nod[i].id=i; } for(int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); adde(x,y,z),adde(y,x,z); } dijkstra(); sort(nod+1,nod+n+1,cmp); for(int i=1;i<=n;++i){ a[i]=dis[nod[i].id]; } sum1[0]=-1; for(int i=1;i<=n;++i){ tot[i]=tot[i-1]; if(!us[nod[i].c]){ us[nod[i].c]=1; sum1[i]=sum1[i-1]+tot[i]*(a[i]-a[i-1])+1; tot[i]=tot[i-1]+1; } else{ sum1[i]=tot[i]*(a[i]-a[i-1])+sum1[i-1]; } } while(qq--){ int l=read(),r=read(); printf("%lld\n",check(r)-check(l-1)); } } else{ mod=read(); for(int i=1;i<=n;++i){ nod[i].c=read(),nod[i].id=i; } for(int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); adde(x,y,z),adde(y,x,z); } dijkstra(); sort(nod+1,nod+n+1,cmp); for(int i=1;i<=n;++i){ a[i]=dis[nod[i].id]; } sum1[0]=-1; for(int i=1;i<=n;++i){ tot[i]=tot[i-1]; if(!us[nod[i].c]){ us[nod[i].c]=1; sum1[i]=sum1[i-1]+tot[i]*(a[i]-a[i-1])+1; tot[i]=tot[i-1]+1; } else{ sum1[i]=tot[i]*(a[i]-a[i-1])+sum1[i-1]; } } while(qq--){ int l=read(),r=read(); l=(l^pre)%mod+1,r=(r^pre)%mod+1; if(l>r)swap(l,r); pre=check(r)-check(l-1); printf("%lld\n",pre); } } return 0; }
全部评论
(7) 回帖