竞赛讨论区 > T2 算法:前缀和和prim
头像
wylqh
发布于 2020-10-22 22:16
+ 关注

T2 算法:前缀和和prim

话说我当时一开始想的是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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐