题目
vjudge
You have a square grid of size $m×m$. There are $n$ troops placed on this grid, each with coordinates $(x_i,y_i)$.
Over t minutes, the following events occur:
Move: A troop numbered x moves in a direction (up, down, left, or right) for d units. Troops cannot move outside the grid.
Regroup: Troop x gathers all other troops that share the same row or column as troop x. These troops move to troop x’s location.
The cost of moving troop $i$ to troop $j$ is calculated as: $(x_i−x_j)^2+(y_i−y_j)^2$.
For each regrouping event, output the total cost of all troop movements during that regrouping, modulo $10^9+7$.
思路
我们对于每一个横坐标/纵坐标，记录下它们对应的纵坐标/横坐标（由于 $m$ 会很大，我们考虑把这些坐标离散化）。使用并查集，记录每一个士兵属于的块（即祖先节点），以及该块的大小。接下来开始操作。首先使用一个小技巧：对于每次操作，再开一个新点，这样就不用讨论该块的祖先节点是否改动。
对于操作1（对应下面操作S）非常好处理，将原来块大小减一，再将其放置到新快中；
对于操作2（对应下面操作Q），我们把当前士兵的位置作为新的块，依次遍历所有和它同行同列的块，这里要注意，对于与该士兵同样位置的士兵会在两次遍历中都被加入新块，要减一次。
想通这些部分，问题就迎刃而解了，只需模拟我们上述的思路即可。
Warnings:
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,mod=1e9+7;
ll n,m,t;
struct node
{
ll x,y;
} a[N*2];
ll ans;
ll tox,toy;
map<ll,ll> mx,my;
vector<ll> ex[N*2],ey[N*2];
ll id[N];
ll cn[N*2],par[N*2];
ll find(ll x)
{
return par[x]==x?x:par[x]=find(par[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
id[i]=i;
if(!mx[a[i].x])
{
mx[a[i].x]=++tox;
}
if(!my[a[i].y])
{
my[a[i].y]=++toy;
}
ex[mx[a[i].x]].push_back(i);
ey[my[a[i].y]].push_back(i);
par[i]=i;
cn[i]++;
}
cin>>t;
for(ll i=n+1;i<=n+t;i++)
{
char c;
ll p;
cin>>c>>p;
p^=ans;
ll fp=find(id[p]);
ll cx=a[fp].x,cy=a[fp].y;
if(c=='Q')
{
ans=0;
a[i].x=cx,a[i].y=cy;
ll cn2=0;
for(auto q:ex[mx[cx]])
{
ll fq=find(q);
ll val=(a[fq].y-cy)%mod;
val=val*val%mod;
ans=(ans+val*cn[fq]%mod)%mod;
cn[i]+=cn[fq];
if(a[fq].y==cy)
{
cn2+=cn[fq];
}
else
{
par[fq]=i;
}
}
ex[mx[cx]].clear();
for(auto q:ey[my[cy]])
{
ll fq=find(q);
ll val=(a[fq].x-cx)%mod;
val=val*val%mod;
ans=(ans+val*cn[fq]%mod)%mod;
cn[i]+=cn[fq];
if(a[fq].x!=cx)
{
par[fq]=i;
}
}
ey[my[cy]].clear();
cn[i]-=cn2;
ex[mx[cx]].push_back(i);
ey[my[cy]].push_back(i);
par[i]=i;
cout<<ans<<"\n";
}
else
{
ll d;
cin>>d;
if(c=='L')
{
cy-=d;
}
else if(c=='R')
{
cy+=d;
}
else if(c=='U')
{
cx-=d;
}
else if(c=='D')
{
cx+=d;
}
if(!mx[cx])
{
mx[cx]=++tox;
}
if(!my[cy])
{
my[cy]=++toy;
}
a[i]={cx,cy};
cn[fp]--;
ex[mx[cx]].push_back(i);
ey[my[cy]].push_back(i);
cn[i]++;
par[i]=i;
}
id[p]=i;
}
return 0;
}
|
做了我2d，纯纯可恶 (σ｀д′)σ