插入排序（CSP-J 2021 T2）我有新思路了，链接：https://www.cnblogs.com/wjk53233/p/16533752.html

我有新思路了，链接：https://www.cnblogs.com/wjk53233/p/16533752.html

这道题目很长但只要·二个数组就能解决数组一：a（a数组只是用来存数是无序的） p（p数组是用来记录数的位置的，p[i]表示第i个数的排序）

题目有两种操作，查询和顶替。

在查询时进行数组操作会爆因为Q * n达到了 1.6*10^10,亿秒肯定会爆，所以要在顶替操作时改变p数组，操作次数为4*10^7,运算量大幅度减少。

二种操作

1.顶替：

（一）先将要替换的点删除，要替换点的p数组内的数初始化为1并将比删除点的p数组内的数大（或等于，但一定i要大于替换点的下标）的p数组内的数-1；

（二）再将要替换的点换上新值新制（在替换操作后），并将比替换点的p数组内的数大（或等于，但一定i要大于替换点的下标）的p数组内的数+1；

（三）如果a[i]==v&&i<x或a[i]<v p[x]就++；

2.查找

（一）输入n1；

（二）输出p[n1]；

剩下只有开头p数组要初始化为一之后就是小细节了

程序：

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<cstdio>

 4 #include<cmath>

 5 #include<map>

 6 #include<vector>

 7 #include<queue>

 8 #include<set>

 9 #define LL long long

10 using namespace std;

11 int main()

12 {

13 //    freopen("1.in","r",stdin);

14 //    freopen("1.out","w",stdout);

15     int n,q,a[9000]={0},p[9000]={0};

16     scanf("%d%d",&n,&q);

17     for(int i=1;i<=n;i++)

18     {

19         scanf("%d",&a[i]);

20         p[i]=1;

21     }

22     for(int i=1;i<=n;i++)

23     {

24         for(int j=1;j<=n;j++)

25         {

26             if(i==j) continue;

27             else

28             {

29                 if(a[j]<a[i]) p[i]++;

30                 else if(a[j]==a[i]&&i>j) p[i]++;

31             }

32         }

33     }

34     while(q--)

35     {

36         int l;

37         scanf("%d",&l);

38         if(l==1)

39         {

40             int x,v;

41             scanf("%d%d",&x,&v);

42             p[x]=1;

43             for(int i=1;i<=n;i++)

44             {

45                 if(i==x) continue;

46                 if(a[i]>a[x])

47                 {

48                     p[i]--;

49                 }

50                 if(a[i]==a[x]&&x<i)

51                 {

52                     p[i]--;

53                 }

54                 if(a[i]>v)

55                 {

56                     p[i]++;

57                 }

58                 if(a[i]==v&&i>x)

59                 {

60                     p[i]++;

61                 }

62                 if(a[i]<v)

63                 {

64                     p[x]++;

65                 }

66                 if(a[i]==v&&i<x)

67                 {

68                     p[x]++;

69                 }

70             }

71             a[x]=v;

72         }

73         else

74         {

75             int n1;

76             scanf("%d",&n1);

77             printf("%d\n",p[n1]);

78         }

79     }

80     return 0;

81 }

巴特西

插入排序（CSP-J 2021 T2）我有新思路了，链接：https://www.cnblogs.com/wjk53233/p/16533752.html

最新文章

热门文章