【分块优化】H. Permutation and Queries

【分块优化】H. Permutation and Queries

给定一个序列ne。

ne[i]代表着若当前位置为i的下一个跳转的位置为ne[i],比如ne[3]=5代表着说当前位置为3的下一个要跳转到的位置为5.

并进行q次操作，操作类型分为两种。

• 一种是swap(ne[i],ne[j])
• 另外一种是move(x,k),需要输出将x=ne[x]进行k次迭代后的结果。

思路：

使用分块维护x在跳转\(int(\sqrt q)\)后的结果。

在使用swap操作后要进行更新维护。

（类似对两个链表交换中间某两个结点的操作）

#include 
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i>n>>q;
    len = int(sqrt(n));
    repd(i,1,n) cin>>ne[i];
    repd(i,1,n) pre[ne[i]] = i;
    repd(i,1,n) jmp[i] = move(i,len);
	repd(i,1,q)
    {
        cin>>opt>>x>>y;
        if(opt==1)
        {
           swap(pre[ne[x]],pre[ne[y]]);
		   swap(ne[x],ne[y]);
		   modi(x);modi(y); 	
		}
		else if(opt==2)
		{
		    while(y-len>=0) x = jmp[x],y -= len;
		    cout<