Java 解法, 执行用时: 1684ms, 内存消耗: 30504K, 提交时间: 2022-01-01 20:57:06

import java.util.*;
public class Main{
    static Scanner reader = new Scanner(System.in);
    static int[] nums = new int[100010];
    static int[] pos = new int[100010];
    //存放k<= 100 的答案
    static int[] buffer = new int[105];
    public static void main(String[] args){
        int n = reader.nextInt();
        for(int i = 1; i <= n; i++){
            nums[i] = reader.nextInt();
            pos[nums[i]] = i;
        }
        for(int i = 1; i <= Math.min(100,n); i++){
            buffer[i] = JY(i,n);
        }
        int g = reader.nextInt();
        for(int i = 0; i < g; i++){
            int way = reader.nextInt();
            if(way == 1){
                //处理交换
                int l = reader.nextInt();
                int r = reader.nextInt();
                change(nums[l], nums[r], n);
                swap(nums, l ,r);
                swap(pos, nums[l], nums[r]);
            } else {
                int k = reader.nextInt();
                if(k <= 100)System.out.println(buffer[k]);
                else System.out.println(JY(k,n));
            }
        }
    }
    
    public static void change(int x, int y,int n){
        if(x > y){
            int temp = x;
            x = y;
            y = temp;
        }
        //x小 y 大
        int cnt1,cnt2;
        for(int k = 1; k <= Math.min(100,n- 1); k++){
            cnt1 = 0;
            cnt2 = 0;
            if((x - 1) % k == 0){
                if(x - k >= 1) cnt1 += pos[x - k] > pos[x] ? 1 : 0;
                if(x + k <= n) cnt1 += pos[x] > pos[x + k] ? 1 : 0;
            }
            if((y - 1) % k == 0){
                if(y - k >= 1 && y - k != x) cnt1 += pos[y - k] > pos[y] ? 1 : 0;
                if(y + k <= n) cnt1 += pos[y] > pos[y + k] ? 1 : 0;
            }
            swap(pos, x, y);
            if((x - 1) % k == 0){
                if(x - k >= 1) cnt2 += pos[x - k] > pos[x] ? 1 : 0;
                if(x + k <= n) cnt2 += pos[x] > pos[x + k] ? 1 : 0;
            }
            if((y - 1) % k == 0){
                if(y - k >= 1 && y - k != x) cnt2 += pos[y - k] > pos[y] ? 1 : 0;
                if(y + k <= n) cnt2 += pos[y] > pos[y + k] ? 1 : 0;
            }
            swap(pos, x, y);
            buffer[k] = buffer[k] - cnt1 + cnt2;
        }
    }
    
    public static void swap(int[] arr, int l, int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    
    public static int JY(int key, int n){
        int res = 1;
        for(int i = 1 + key; i <= n; i+=key){
            if(pos[i] < pos[i - key]){
                res++;
            }
        }
        return res;
    }
}

C 解法, 执行用时: 1519ms, 内存消耗: 1416K, 提交时间: 2023-08-06 11:50:39

#include <stdio.h>

int a[1000005], mt[1000005];
int f, x, y, k, n, m;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mt[a[i]] = i;
    }
    
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &f);
        if (f == 1) {
            scanf("%d %d", &x, &y);
            mt[a[y]] = x;
            mt[a[x]] = y;
            int c = a[x];
            a[x] = a[y];
            a[y] = c;
        } else {
            int cnt = 0, p = 1, z = mt[1];
            scanf("%d", &k);
            while (p <= n) {
                if (mt[p + k] > z) {
                    z = mt[p + k];
                    p += k;
                } else {
                    cnt++;
                    z = mt[p + k];
                    p += k;
                }
            }
            printf("%d\n", cnt);
        }
    }
    
    return 0;
}

C++ 解法, 执行用时: 1125ms, 内存消耗: 1452K, 提交时间: 2022-05-15 17:40:23

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+4;
int f[N],a[N],n;
void dd(int x)
{
	int y=a[1],k=1,s=0;
	while(k<=n)
	{
		if(y<a[k+x])
		{
			y=a[k+x];
			k=k+x;
		}
		else
		{	
			s++;
			k=k+x;
			y=a[k];
		}
	}
	cout<<s<<endl;
}
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>f[i];
		a[f[i]]=i;
	}
	int t,x,y,m;
	cin>>m;
	while(m--)
	{
		cin>>t;
		if(t==1)
		{
			cin>>x>>y;
			a[f[x]]=y;
			a[f[y]]=x;
			swap(f[x],f[y]);
		}
		else
		{
			cin>>x;
			dd(x);
		}
	}
	return 0;
}