看到这个题第一反应肯定是模拟啊
每次查询前都排一次查询后再复原
很显然是超时的
（但好像修改的时候进行排序和复原会更优一点）
（反正都会超时无所谓了）
考场也确实是这个分（悲）
那我们进入正题
先看一下超时代码
1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 #define ll long long
5 using namespace std;
6 int n,x;
7 //数组中所有数都是非负整数
8 //归纳总结:稳定排序与不稳定排序
9 ll q,v;
10
11 struct neww{
12 ll num;
13 ll data;
14 }past[8010],a[8010];
15 int ffind(ll x)
16 {
17 for(ll i=1;i<=n;i++)
18 if(past[x].num==a[i].num)
19 return i;
20 }
21 bool cmp(neww x,neww y)
22 {
23 if(x.data!=y.data)
24 return x.data<y.data;
25 return x.num<y.num;
26 }
27 int main()
28 {
29 cin>>n>>q;
30 for(ll i=1;i<=n;i++)
31 {
32 cin>>past[i].data;
33 past[i].num=i;
34 a[i]=past[i];
35 }
36 int temp;
37 for(ll i=1;i<=q;i++)
38 {
39 cin>>temp;
40 if(temp==1)
41 {
42 cin>>x>>v;
43 a[x].data=v;
44 past[x].data=v;//对未来有影响
45 }
46 if(temp==2)
47 {
48 cin>>x;
49 // stable_sort(a+1,a+n+1,cmp);
50 sort(a+1,a+n+1,cmp);
51 cout<<ffind(x)<<endl;
52 for(ll i=1;i<=n;i++)
53 a[i]=past[i];//对未来无影响
54 }
55 }
56 return 0;
57 }
50行那个写的不错（乐）——sort自定义真的很好用！
我们来分析一下他为什么超时
首先每次都排序肯定是不行的，一下子就O（n2）直接要命
可以看到，题目要求说，只要求知道原来编号几的元素现在在哪个位置
我们沿用上面第二个思路，只要在每次修改的时候将修改的那个元素放入有序队列中即可（也就是题目的来源——插入排序）
判断修改的这个元素和有序序列中间元素的大小（当然不判断也无所谓）
然后来往前往后交换位置达到目的
这样一下就已经很快了！
然后我们看那个ffind函数
每次调用都是O（n）的复杂度（天）
不炸算我运气好（悲）
经典永流传了家人们——空间换时间
我们新建一个数组，在这个数组里，wei[i]=j 连接编号与下标
编号为i的下标为多少，每次修改完，都存下来
这样就可以O（n）调用而不用次次O（n）了！
然后你就可以愉快地AC了！
1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cmath>
5 #define ll long long
6 using namespace std;
7 int n,x;
8 //数组中所有数都是非负整数
9 //归纳总结:稳定排序与不稳定排序
10 ll q,v;
11
12 struct neww{
13 ll num;
14 ll data;
15 }a[8010];
16
17 int wei[8010]; //wei[i] 代表编号为ｉ所在的下标
18 //a[i].num代表下标为ｉ的编号
19 //a[i].data 代表下标为ｉ的数据
20 //a[wei[i]].data代表编号为ｉ的数据
21 bool cmp(neww x,neww y)
22 {
23 if(x.data!=y.data)
24 return x.data<y.data;
25 return x.num<y.num;
26 }
27
28 void csort(int k)
29 {
30 for(int i=1;i<n;i++)
31 {
32 if(cmp(a[i+1],a[i]))
33 swap(a[i+1],a[i]);
34 }
35 for(int i=n-1;i>=1;i--)
36 {
37 if(cmp(a[i+1],a[i]))
38 swap(a[i+1],a[i]);
39 }
40 }
41
42 int main()
43 {
44 cin>>n>>q;
45 for(ll i=1;i<=n;i++)
46 {
47 scanf("%d",&a[i].data);
48 a[i].num=i;
49 }
50 sort(a+1,a+n+1,cmp);//手动稳定起来!
51 for(int i=1;i<=n;i++)
52 wei[a[i].num]=i;
53
54 int temp;
55 for(ll i=1;i<=q;i++)
56 {
57 scanf("%d",&temp);
58 if(temp==1)
59 {
60 scanf("%d%d",&x,&v);
61 a[wei[x]].data=v;
62 csort(x);
63 for(int i=1;i<=n;i++)
64 wei[a[i].num]=i;
65 }
66 if(temp==2)
67 {
68 scanf("%d",&x);
69 printf("%d\n",wei[x]);
70 }
71 }
72 return 0;
73 }
标签：下标,int,插入排序,T2,past,2022J,include,data,ll From： https://www.cnblogs.com/xdzxxintong/p/16748246.html