POJ1984(Navigation Nightmare)

链接：https://vjudge.net/problem/POJ-1984
思路：感觉kuangbin系列的并查集都是一个套路啊，维护与根节点的关系，不管是可传递的模加法还是距离实质都是一样的，本题我的做法是先把所有道路全部读入保存，然后再把所有查询读入保存，按照时间先后排序，然后遍历所有查询，每次查询前先把该时间点之前的所有道路都用并查集关系建立起来(在x，y上分别维护关系)，然后查询，如果二者的根节点相同说明之间有路，返回二者x，y距离差的绝对值的和即可，否则一定没有道路，返回-1，最后再按照之前的输入顺序输出答案即可。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 400000;
int par[maxn];
int relx[maxn];
int rely[maxn];
int n,m,q;

int getroot(int a){
    if(par[a]==a)return a;
    int px = par[a];
    par[a] = getroot(par[a]);
    relx[a] = relx[a] + relx[px];
    rely[a] = rely[a] + rely[px];
    return par[a];  
}

struct query{
    int a,b,t,id,res;
    bool operator<(const query& r)const{
        return t<r.t;
    }
}ask[maxn];

bool cmp(const query &r1,const query &r2){
    return r1.id<r2.id;
}

struct change{
    int a,b,dx,dy;
}cc[maxn];

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<=n;i++){
            par[i] = i;
            relx[i] = rely[i] = 0;
        }
        for(int i=0;i<m;i++){
            char ch[10];
            int d = 0;
            scanf("%d%d%d%s",&cc[i].a,&cc[i].b,&d,ch);
            if(ch[0]=='E')cc[i].dy = d,cc[i].dx = 0;
            else if(ch[0]=='W')cc[i].dy = -d,cc[i].dx = 0;
            else if(ch[0]=='N')cc[i].dx = -d,cc[i].dy = 0;
            else if(ch[0]=='S')cc[i].dx = d,cc[i].dy = 0;
        }
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d%d%d",&ask[i].a,&ask[i].b,&ask[i].t);
            ask[i].id = i;
        }
        sort(ask,ask+q);//按照时间先后顺序排序
        int nowi = 0;
        for(int i=0;i<q;i++){
            while(nowi+1<=ask[i].t){//将该时间点前的所有道路建立处理
                int a = cc[nowi].a;
                int b = cc[nowi].b;
                int p1 = getroot(a);
                int p2 = getroot(b);
                if(p1==p2)continue;
                par[p2] = p1;
                //x和y上分别维护关系
                relx[p2] = -relx[b]-cc[nowi].dx+relx[a];
                rely[p2] = -rely[b]-cc[nowi].dy+rely[a];
                nowi++;
            }
            int a = ask[i].a;
            int b = ask[i].b;
            int p1 = getroot(a);
            int p2 = getroot(b);
            if(p1==p2){
                ask[i].res = abs(relx[a]-relx[b])+abs(rely[a]-rely[b]);
            }
            else ask[i].res = -1;
        }
        sort(ask,ask+q,cmp);//还原原来的输入顺序
        for(int i=0;i<q;i++){
            printf("%d\n",ask[i].res);
        }
    }
    return 0;
}