Description&Data Constraint
(1le Kle 2 imes 10^5)。
Solution
首先建议去做一下银组的弱化版：P7299 [USACO21JAN] Dance Mooves S。
银组的做法是：
记录 (K) 次交换后每个点的位置，初末位置连边，则会形成一些环。
由于时间无限，则环上的每个点的答案是一样的，因此可以开个 ( ext{vector}) 记录每个点走过的位置，最后开个 ( ext{set}) 维护即可。
这两道题的区别在于金组的这道题目增加了时间的限制，这就意味着有些环是无法走完的。
先求出在时间限制下 (K) 次换位完整的进行了多少轮，记为 (times)，同时求出还剩下多少次换位 (other)。
按照银组的做法先将环弄出来，记录每个环上有哪些点。
对于环的大小小于等于 (times) 的，做法同银组，因为这些环是能够在 (times) 轮 (K) 次换位后，每个点至少回到原点一次，所以这个环上的答案都是一样的。（可能有点绕）
那么现在就思考那些环的大小大于 (times) 的。
思考在这些环上的点是怎么移动的。
对于一个点 (i)，它在 (K) 次换位后到达的点记为 (nxt_i)，那么这次换位中 (i) 所经过的点可以用个 ( ext{vector}) 记录下来，然后对于 (times) 轮 (K)，每次就可以记录下从 (i) 到 (nxt_i) 中经过的点，然后再从 (times) 轮后的位置再往下走 (other) 次换位，最后统计答案就好。
但是这个方法的时间复杂度十分的高，达到了 (mathcal O(NK))。
那么优化就可以考虑破环成链，将环复制一次，开个双指针，每次移动前删除当前 (l) 的贡献和 (r+1) 的剩下贡献。然后移动，加入新的 (r) 的贡献和 (r+1) 的剩下贡献。（注意贡献和剩下贡献是不一样的）（其实就是滑动窗口维护）。
最后把贡献挂在 (l) 上就可以了。
Code
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
#define N 200005
using namespace std;
vector<int> spot[N],rest[N],ring[N];
int n,num,a[N],b[N],pos[N],fro[N],ans[N],buck[N],len[N];
ll m,k,times,other;
bool isin[N];
void getring(int x)
{
int now=x;
do
{
isin[now]=true;
ring[num].push_back(now);
now=fro[now];
}while (now!=x);
len[num]=ring[num].size();
}
void calcring(int now)
{
int res=0;
if ((ll)len[now]<=times)
{
for (int i=0;i<len[now];++i)
{
int x=ring[now][i];
for (int j=0;j<spot[x].size();++j)
{
int y=spot[x][j];
if (!buck[y]++) ++res;
}
}
for (int i=0;i<len[now];++i)
ans[ring[now][i]]=res;
for (int i=0;i<len[now];++i)
{
int x=ring[now][i];
for (int j=0;j<spot[x].size();++j)
{
int y=spot[x][j];
buck[y]=0;
}
}
return;
}
for (int i=0;i<len[now];++i)
ring[now].push_back(ring[now][i]);
for (int i=0;i<times;++i)
{
int x=ring[now][i];
for (int j=0;j<spot[x].size();++j)
{
int y=spot[x][j];
if (!buck[y]++) ++res;
}
}
for (int i=0;i<rest[ring[now][times]].size();++i)
{
int x=rest[ring[now][times]][i];
if (!buck[x]) ++res;
++buck[x];
}
ans[ring[now][0]]=res;
int l=0,r=times-1;
while (l<len[now]-1)
{
int x=ring[now][l];
if (l<=r)
{
for (int i=0;i<spot[x].size();++i)
{
int y=spot[x][i];
if (buck[y]==1) --res;
--buck[y];
}
}
x=ring[now][r+1];
for (int i=0;i<rest[x].size();++i)
{
int y=rest[x][i];
if (buck[y]==1) --res;
--buck[y];
}
++l;++r;
x=ring[now][r];
if (l<=r)
{
for (int i=0;i<spot[x].size();++i)
{
int y=spot[x][i];
if (!buck[y]++) ++res;
}
}
x=ring[now][r+1];
for (int i=0;i<rest[x].size();++i)
{
int y=rest[x][i];
if (!buck[y]++) ++res;
}
ans[ring[now][l]]=res;
}
for (int i=l;i<=r;++i)
{
int x=ring[now][i];
for (int j=0;j<spot[x].size();++j)
buck[spot[x][j]]=0;
}
for (int i=0;i<rest[ring[now][r+1]].size();++i)
{
int x=rest[ring[now][r+1]][i];
buck[x]=0;
}
memset(buck,0,sizeof(buck));
}
int main()
{
scanf("%d%lld%lld",&n,&k,&m);
times=m/k;other=m%k;
for (int i=1;i<=k;++i)
scanf("%d%d",&a[i],&b[i]);
for (int i=1;i<=n;++i)
spot[i].push_back(i),rest[i].push_back(i),pos[i]=i;
for (int i=1;i<=k;++i)
{
spot[pos[a[i]]].push_back(b[i]);
spot[pos[b[i]]].push_back(a[i]);
if (i<=other)
{
rest[pos[a[i]]].push_back(b[i]);
rest[pos[b[i]]].push_back(a[i]);
}
swap(pos[a[i]],pos[b[i]]);
}
for (int i=1;i<=n;++i)
{
fro[pos[i]]=i;
if (spot[i].size()!=1) spot[i].pop_back();
}
for (int i=1;i<=n;++i)
if (!isin[i]) ++num,getring(i);
for (int i=1;i<=num;++i)
calcring(i);
for (int i=1;i<=n;++i)
printf("%d
",ans[i]);
return 0;
}