链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
插入排序是一种非常常见且简单的排序算法。小ZZZ是一名大一的新生，今天HHH老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为O(1)O(1)O(1)，则插入排序可以以O(n2)O(n^2)O(n2)的时间复杂度完成长度为n 的数组的排序。不妨假设这nnn个数字分别存储在a1,a2,⋅⋅⋅,ana_1, a_2, · · · , a_na1,a2,⋅⋅⋅,an之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
这下面是C/C++ 的示范代码
for (int i = 1; i <= n; i++)
for (int j = i; j>=2; j‐‐)
if ( a[j] < a[j‐1] ){
int t = a[j‐1];
a[j‐1] = a[j];
a[j] = t;
}
这下面是Pascal 的示范代码
for i:=1 to n do for j:=i downto 2 do if a[j]<a[j‐1] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end;
为了帮助小 ZZZ 更好的理解插入排序，小 ZZZ的老师 HHH老师留下了这么一道家庭作业：
HHH老师给了一个长度为nnn的数组aaa，数组下标从111开始，并且数组中的所有元素均为非负整数。小 ZZZ 需要支持在数组aaa上的QQQ次操作，操作共两种，参数分别如下：
111 xvx vxv: 这是第一种操作，会将aaa的第xxx个元素，也就是axa_xax的值，修改为vvv。保证1≤x≤n,1≤v≤1091≤x≤n,1≤v≤10^91≤x≤n,1≤v≤109。 注意这种操作会改变数组的元素， 修改得到的数组会被保留， 也会影响后续的操作。
222 xxx: 这是第二种操作，假设 H 老师按照上面的伪代码对aaa数组进行排序，你需要告诉 HHH老师原来aaa的第xxx个元素，也就是axa_xax，在排序后的新数组所处的位置。保证1≤x≤n1≤x≤n1≤x≤n。 注意这种操作不会改变数组的元素， 排序后的数组不会被保留， 也不会影响后续的操作 。
HHH老师不喜欢过多的修改，所以他保证类型111的操作次数不超过500050005000。
小ZZZ没有学过计算机竞赛，因此小 ZZZ 并不会做这道题。他找到了你来帮助他解决这个问题。
sort.zip
输入描述:
输入的第一行包含两个正整数n,Qn, Qn,Q，表示数组长度和操作次数。保证1≤n≤8,000,1≤Q≤2×1051≤n≤8,000,1≤Q≤2×10^51≤n≤8,000,1≤Q≤2×105。
输入的第二行包含nnn个空格分隔的非负整数，其中第iii个非负整数表示aia_iai。保证1≤ai≤1091≤a_i≤10^91≤ai≤109。
接下来QQQ行，每行2∼32∼32∼3个正整数，表示一次操作，操作格式见题目描述。
输出描述:
对于每一次类型为222的询问，输出一行一个正整数表示答案。
示例1
输入
3 4 3 2 1 2 3 1 3 2 2 2 2 3
3 4 3 2 1 2 3 1 3 2 2 2 2 3
输出
1 1 2
1 1 2
说明
在修改操作之前，假设HHH老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是3,2,13,2,13,2,1。
在修改操作之前，假设 HHH老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是3,1,23,1,23,1,2。
注意虽然此时a2=a3a_2 =a_3a2=a3，但是我们不能将其视为相同的元素。
备注:
对于所有测试数据，满足1≤n≤8,000,1≤Q≤2×105,1≤x≤n,1≤v,ai≤1091≤n≤8,000,1≤Q≤2×10^5,1≤x≤n,1≤v,a_i≤10^91≤n≤8,000,1≤Q≤2×105,1≤x≤n,1≤v,ai≤109。对于所有测试数据，保证在所有QQQ次操作中，至多有 500050005000 次操作属于类型一。
各测试点的附加限制及分值如下表所示。
暴力：
修改操作O(1) 查询O(n) 最大查询次数为2×10^5次，每次复杂度为O(n),最大为8000，最坏复杂度就是1.6×10^9 TLE
被查询的数的位置 = 比他小的数 + 在他左边和他 一样大的数 + 1
例如 3 1 2 2 == >1 2 2 3
代码：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 8010;
ll n,q;
ll k,k1,k2;
ll cnt1,cnt2;
ll a[N];
int main() {
cin >> n >> q;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
while(q--) {
cnt1 = 0,cnt2 = 0;
scanf("%lld",&k);
if (k == 1) {
scanf("%lld %lld",&k1,&k2);
a[k1]=k2;//修改
}else {
scanf("%lld",&k1);
for(int i=1;i<k1;i++)
{
if(a[i]==a[k1]) cnt1++;
if(a[i]<a[k1]) cnt2++;
}
for(int i=k1+1;i<=n;i++)
{
if(a[i]<a[k1]) cnt2++;
}
printf("%lld\n",cnt1+cnt2+1);
}
}
return 0;
}优化：因为处理的次数不超过5000，我们可以做一个预处理，每次查询直接输出O(1),每次修改的时候去遍历维护我们的预处理数组O(n)
最坏复杂度大概是8000×8000(预处理)+5000×8000(修改)+(200000-5000)*1 大约是 1e8的复杂度
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 8010;
int n,q;
int k,k1,k2;
int cnt1,cnt2;
int a[N];
int left1[N],all1[N];
void cc(int k1, int k2) {
int cntt = 0,cntts = 0;//cntt 和修改点相等的 cntts 小于修改点的
for (int i = 1;i < k1;i++) {
if (a[i] == k2) cntt++;
if (a[i] < k2) cntts++;
if(a[i] > a[k1]) all1[i]--;
if(a[i] > k2) all1[i]++;
}
left1[k1] = cntt;
for (int i =k1+1;i <= n;i++) {
if (a[i] == a[k1]) left1[i]--;
if (a[i] == k2) left1[i]++;
if (a[i] > a[k1]) all1[i]--;
if (a[i] > k2) all1[i]++;
if (a[i] < k2) cntts++;
}
a[k1] = k2;
all1[k1] = cntts;
}
int main() {
cin >> n >> q;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i = 1;i <= n;i++) {
cnt1 = 0,cnt2 = 0;
for (int j = 1;j <= n;j++) {
if (a[j] == a[i]) cnt1++;
if (i-j==1) left1[i]=cnt1;
if(a[j]<a[i]) cnt2++;
}
all1[i] = cnt2;
}
while(q--) {
cnt1 = 0,cnt2 = 0;
scanf("%d",&k);
if (k == 1) {
scanf("%d %d",&k1,&k2);
cc(k1,k2);
}else {
scanf("%d",&k1);
printf("%d\n",left1[k1]+all1[k1]+1);
}
}
return 0;
}当一个点发生变化的时候
1.这个点的两个属性都会发生改变
2.这个点左右所有的点(比其小)这个属性会发生改变
3.这个点右边的点(左边和其相等这个属性)会发生改变
而这些属性的改变只要一个循环就能全部求出
只要每个点都遍历一遍
减去修改前点的影响再加上新点的影响即可
因此修改的复杂度是O(n)；
