吐槽:
原意是发个题解,但我发现这代码洛谷上AC,青藤超时了!只有76分...
这到底是青藤的原因还是青藤的原因啊...这数据点创的也是绝了
题目做法:
对于每个修改操作,直接修改。
对于每个查询操作,暴力查询,从头向后查找,按题意模拟。
时间复杂度 O(nq)。
但是在青藤上是错的,可以去洛谷上提交哈
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
freopen("sort.in", "r", stdin);
freopen("sort.out", "w", stdout);
int n,q,x,l,r;
scanf("%d%d", &n, &q);
for(int i=1;i<=n;i++)scanf("%d", &a[i]);
for(int i=1;i<=q;i++){
scanf("%d", &x);
if(x==1){
scanf("%d%d", &l, &r);
a[l]=r;
}
else{
scanf("%d", &l);
int sum=n;
for(int j=1;j<l;j++){
if(a[j]>a[l])sum--;
}
for(int j=l+1;j<=n;j++){
if(a[j]>=a[l])sum--;
}
cout<<sum<<"\n";
}
}
return 0;
}