HDU 5361 In Touch

迈不过友情╰ 2022-08-03 12:59 10阅读 0赞

首先的想法是线段树，因为是区间更新的，所以就是一边dij一边query和update。  
今天想了一想，觉得似乎不要用这么麻烦的方法。  
下面证明通过某种排序方式使得每个点只要被更新过了，就必定是最近距离。因此我们可以将更新过的点压缩掉。

> 每个点连出去的边权是**相同的**，那么我们只需要按照dis\[u\]\+cost\[u\]从小到大排序就可以保证接下来更新的点距离一定是最小，因为下一个点的更新方式为dis\[v\]=dis\[u\]\+cost\[u\]，那么我们取出来的dis\[u\]\+cost\[u\]是最小的，那么dis\[v\]也就是所以可能值的最小值，因此以后就不用更新了。

那么我们的压缩方式可以有很多，比如并查集进行路径压缩，比如用set存还没有访问的点，然后二分出\[L,R\]，直接更新，然后直接删除。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=200010;
    
    ll L[MAXN],R[MAXN],cost[MAXN],dis[MAXN];
    int n,fa[MAXN];
    
    struct Node
    {
        ll dis,cost;
        int u;
        bool operator < (const Node& b) const
        {
            return dis+cost>b.dis+b.cost;
        }
        Node(ll dis=0,ll cost=0,int u=0):dis(dis),cost(cost),u(u) {}
    };
    
    priority_queue<Node> Q;
    
    void init()
    {
        for(int i=0 ; i<n+10; i++)
        {
            dis[i]=LLINF;
            fa[i]=i;
        }
        while(!Q.empty())   Q.pop();
    }
    
    int find_fa(int x)
    {
        if(fa[x]==x)    return x;
        return fa[x]=find_fa(fa[x]);
    }
    
    void merge(int x,int y)
    {
        x=find_fa(x),y=find_fa(y);
        if(x==y)    return;
        fa[x]=y;
    }
    
    void dij(int st)
    {
        dis[st]=0;
        Q.push(Node(0LL,cost[st],st));
        while(!Q.empty())
        {
            Node tmp=Q.top();
            Q.pop();
            int u=tmp.u;
            //cout<<u<<endl;
            for(int i=-1; i<=1; i += 2)
            {
                int le=L[u]*i+u;
                int ri=R[u]*i+u;
                if(le>ri)
                    swap(le,ri);
                if(le>n || ri<=0)    continue;
                for(int v=max(le,1); ; v++)
                {
                    v=find_fa(v);
                    if(v>min(n,ri))
                        break;
                    if(dis[v]>dis[u]+cost[u])
                    {
                        dis[v]=dis[u]+cost[u];
                        Q.push(Node(dis[v],cost[v],v));
                    }
                    merge(v,v+1);
                }
            }
        }
    }
    
    int main()
    {
        int T;
        read(T);
        while(T--)
        {
            read(n);
            init();
            for(int i=1; i<=n; i++)
                read(L[i]);
            for(int i=1; i<=n; i++)
                read(R[i]);
            for(int i=1; i<=n; i++)
                read(cost[i]);
            dij(1);
            printf("0");
            for (int i=2; i<=n; i++)
                printf(" %I64d",dis[i]!=LLINF?dis[i]:-1);
            printf("\n");
        }
        return 0;
    }

线段树写法：  
区间更新，但是要注意的是，更新的时候，有可能有些已经在dij松弛完全集合中的点不能被更新。处理方法有很多，比如设置一个特别大的值，比如INF，这样push\_up的时候不会受到影响；比如设置一个域记录这个区间有多少个可以用得点，如果可以用的点为0，就不用更新了。

得，贴一份队友的代码，自己写的还没过…这个好难写啊

#include <iostream>
    #include <cstdio>
    #include <stack>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    //#include <unordered_map>
    #define N 200010
    #define lson x<<1
    #define rson x<<1|1
    #define mid ((lt[x].l+lt[x].r)/2)
    //#define ID(x, y) ((x)*m+(y))
    //#define CHECK(x, y) ((x)>=0 && (x)<n && (y)>=0 && (y)<m)
    using namespace std;
    typedef pair<long long,long long > PII;
    const long long INF=0x3f3f3f3f3f3f3f3f;
    void Open()
    {
        #ifndef ONLINE_JUDGE
            freopen("D:/in.txt","r",stdin);
            //freopen("D:/my.txt","w",stdout);
        #endif // ONLINE_JUDGE
    }
    struct node
    {
        long long l, r, mi, ma, lazy;
        node(long long l = 0, long long r = 0,long long mi = 0, long long ma = 0, long long lazy = 0):l(l), r(r), mi(mi), ma(ma), lazy(lazy){}
    }lt[N*8];
    long long n;
    long long L[N], R[N], c[N];
    long long ans[N];
    void push_up(long long x)
    {
        lt[x].mi = min(lt[lson].mi, lt[rson].mi);
    // lt[x].lazy = max(lt[lson].lazy, lt[rson].lazy);
    }
    void push_down(long long x)
    {
        lt[lson].lazy = min(lt[lson].lazy, lt[x].lazy);
        lt[rson].lazy = min(lt[rson].lazy, lt[x].lazy);
        if(lt[lson].mi != INF) lt[lson].mi = min(lt[lson].mi, lt[x].lazy);
        if(lt[rson].mi != INF) lt[rson].mi = min(lt[rson].mi, lt[x].lazy);
    }
    void build(long long l, long long r, long long x)
    {
        lt[x] = node(l, r, INF/2, INF/2, INF/2);
        if(l == r){
            return ;
        }
        build(l, mid, lson);
        build(mid+1, r, rson);
    }
    void update(long long l, long long r, long long val, long long x)
    {
        if(lt[x].lazy <= val) return ;
        if(lt[x].mi == INF) return ;
        if(lt[x].l >= l && lt[x].r <= r)
        {
            lt[x].lazy = min(lt[x].lazy, val);
            lt[x].mi = min(lt[x].mi, val);
            return ;
        }
        push_down(x);
        if(r <= mid) update(l, r, val, lson);
        else if(l > mid) update(l, r, val, rson);
        else update(l, mid, val, lson), update(mid+1, r, val, rson);
        push_up(x);
    }
    void updateONE(long long idx, long long x)
    {
        if(lt[x].l == idx && lt[x].r == idx)
        {
            lt[x].mi = INF;
            lt[x].lazy = INF;
            return ;
        }
        push_down(x);
        if(idx <= mid) updateONE(idx, lson);
        else updateONE(idx, rson);
        push_up(x);
    }
    PII query(long long x)
    {
        if(lt[x].l == lt[x].r)
        {
            return PII(lt[x].mi, lt[x].l);
        }
        push_down(x);
        PII tmp;
        if(lt[lson].mi <= lt[rson].mi) tmp = query(lson);
        else tmp = query(rson);
        push_up(x);
        return tmp;
    }
    int main()
    {
        Open();
        long long T;
        scanf("%I64d", &T);
        while(T--)
        {
            scanf("%I64d", &n);
            memset(ans, -1, sizeof(ans));
            for(long long i=1;i<=n;i++) scanf("%I64d", L+i);
            for(long long i=1;i<=n;i++) scanf("%I64d", R+i);
            for(long long i=1;i<=n;i++) scanf("%I64d", c+i);
            build(1, n, 1);
            update(1, 1, 0, 1);
            while(true)
            {
                PII pp = query(1);
                long long curc = pp.first, idx = pp.second;
                if(curc >= INF/2) break;
                ans[idx] = curc;
                updateONE(idx, 1);
                long long costc = c[idx];
                long long l = idx - R[idx];
                long long r = idx - L[idx];
                if(r >= 1)
                    update(max(1LL, l), r, curc + costc, 1);
                l = idx + L[idx];
                r = idx + R[idx];
                if(l <= n)
                    update(l, min(r, n), curc + costc, 1);
            }
            for(long long i=1;i<=n;i++){
    // if(ans[i] >= INF/2) printf("-1");
    // else printf("%I64d", ans[i]);
                printf("%I64d", ans[i]);
                if(i == n) printf("\n");
                else printf(" ");
            }
        }
        return 0;
    }