程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-4879-ZCC loves march(map+set+並查集)

HDU-4879-ZCC loves march(map+set+並查集)

編輯：C++入門知識

HDU-4879-ZCC loves march(map+set+並查集)

Description

On a m*m land stationed n troops, numbered from 1 to n. The i-th troop's position can be described by two numbers (xi,yi) (1<=xi<=m,1<=yi<=m). It is possible that more than one troop stationed in the same place.
Then there are t minutes, in each minute one of the following two events will occur:
(1)the x-th troop moves towards a direction( Up(U) Down(D) Left(L) Right(R))for d units;(You can suppose that the troops won't move out of the boundary)
(2)the x-th troop needs to regroup the troops which stations in the same row or column with the x-th troop. That is, these troops need to move to the x-th troop's station.
Suggest the cost of i-th troop moving to the j-th troop is (xi-xj)^2+(yi-yj)^2, every time a troop regroups, you should output the cost of the regrouping modulo 10^9+7.

Input

The first line: two numbers n,m(n<=100000,m<=10^18)
Next n lines each line contain two numbers xi,yi(1<=xi,yi<=m)
Next line contains a number t.(t<=100000)
Next t lines, each line's format is one of the following two formats:
(1)S x d, S∈{U,L,D,R}, indicating the first event(1<=x<=n,0<=d (2)Q x, indicating the second event(1<=x<=n)
In order to force you to answer the questions online, each time you read x', x=x'?lastans("?" means "xor"), where lastans is the previous answer you output. At the beginning lastans=0.

Output

Q lines, i-th line contain your answer to the i-th regrouping event.(modulo 10^9+7)

Sample Input

Sample Output

 1
1
7

Hint

The input after decode: Q 1 L 1 2 L 4 2 Q 4 R 2 1 Q 2 vc2s0rvQ0LrNzazSu8HQtcTL+dPQvK+6z7340NC8xsvjo6zU2bDR1eLQqbzGy+O5/bXEvK+6z8m+tfSjrM2syrHPwrHq1rjP8tDCtcS4+aOovLTSxrav1q6689DOs8m1xNDCtcS8r7rPo6mhozwvcD4KPHA+PGJyPgo8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include 
#include 
#include 
#include 
#define LL long long
#define mod 1000000007
using namespace std;

struct TROOP{
LL x,y,num;
TROOP(){}
TROOP(LL nx,LL ny,LL nnum){x=nx,y=ny,num=nnum;}
}troop[200005];

map >MX;
map >MY;
set::iterator it;

LL node[200005];

LL findroot(LL x)
{
    if(node[x]!=x) node[x]=findroot(node[x]);

    return node[x];
}

int main()
{
    LL m,x,y,n,i,t,cnt,root,a,b,ans;
    char s[5];

    while(~scanf("%I64d%I64d",&n,&m))
    {
        MX.clear();
        MY.clear();

        for(i=1;i<=n;i++)
        {
            scanf("%I64d%I64d",&x,&y);

            troop[i].x=x;
            troop[i].y=y;
            troop[i].num=1;

            node[i]=i;

            MX[x].insert(i);
            MY[y].insert(i);
        }

        cnt=n+1;

        ans=0;

        scanf("%I64d",&t);

        while(t--)
        {
            scanf("%s",s);

            if(s[0]=='Q')
            {
                scanf("%I64d",&a);

                a^=ans;

                root=findroot(a);//找到a所在的集合

                x=troop[root].x;
                y=troop[root].y;

                LL num=0;

                ans=0;

                for(it=MX[x].begin();it!=MX[x].end();it++)
                {
                    num+=troop[*it].num;

                    LL temp=abs(troop[*it].y-y);

                    temp%=mod;

                    ans=(temp*temp%mod*troop[*it].num%mod+ans)%mod;

                    node[*it]=cnt;//指向cnt，cnt是執行Q操作之後新的根，用來標記新的集合

                    MY[troop[*it].y].erase(*it);//*it已經計算過，從MY[]集合裡刪掉，避免重復計算
                }

                for(it=MY[y].begin();it!=MY[y].end();it++)
                {
                    num+=troop[*it].num;

                    LL temp=abs(troop[*it].x-x);

                    temp%=mod;

                    ans=(temp*temp%mod*troop[*it].num%mod+ans)%mod;

                    node[*it]=cnt;//同理

                    MX[troop[*it].x].erase(*it);//同理
                }

                node[cnt]=cnt;//指向自己，別忘了
                troop[cnt]=TROOP(x,y,num);//執行Q操作之後形成的新集合
                MX[x].clear();
                MY[y].clear();
                MX[x].insert(cnt);//在目標集合中插入
                MY[y].insert(cnt);

                cnt++;

                printf("%I64d\n",ans);
            }
            else
            {
                scanf("%I64d%I64d",&a,&b);

                a^=ans;

                root=findroot(a);//找到a所在的集合，即a的根節點

                x=troop[root].x;
                y=troop[root].y;

                troop[root].num--;//集合裡的計數減一

                if(!troop[root].num)//如果集合的計數為0則把該集合刪掉
                {
                    MX[x].erase(root);
                    MY[y].erase(root);
                }

                if(s[0]=='U')
                {
                    troop[a]=TROOP(x-b,y,1);

                    node[a]=a;//a指向自己，作為新的根

                    MX[x-b].insert(a);//在目標位置插入
                    MY[y].insert(a);
                }
                else if(s[0]=='L')//以下同理
                {
                    troop[a]=TROOP(x,y-b,1);

                    node[a]=a;

                    MX[x].insert(a);
                    MY[y-b].insert(a);
                }
                else if(s[0]=='D')
                {
                    troop[a]=TROOP(x+b,y,1);

                    node[a]=a;

                    MX[x+b].insert(a);
                    MY[y].insert(a);
                }
                else if(s[0]=='R')
                {
                    troop[a]=TROOP(x,y+b,1);

                    node[a]=a;

                    MX[x].insert(a);
                    MY[y+b].insert(a);
                }
            }
        }
    }
}