首页 > 代码库 > HDU-4879-ZCC loves march(map+set+并查集)
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.
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<m)
(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.
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<m)
(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
5 3 1 3 2 1 2 2 2 3 3 2 6 Q 1 L 0 2 L 5 2 Q 5 R 3 1 Q 3
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
思路:分别用map来维护与x坐标平行和垂直的线上面的集合,集合里面直接存对应元素的下标,并用并查集维护,根节点可以用来表示所在的集合。当移动一个元素时,先找到该元素下标对应的根,根对应的num-1,并把移动的元素插到新的位置上,他的根就是他自己。执行Q操作时,通过map找到同一行和同一列的所有集合进行计算,再把这些计算过的集合删掉,同时下标指向新的根(即移动之后形成的新的集合)。
#include <cstdio> #include <cmath> #include <set> #include <map> #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<LL,set<LL> >MX; map<LL,set<LL> >MY; set<LL>::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); } } } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。