- 题解
sorted
- 2024-10-6 16:22:19 @
#include<bits/stdc++.h> using namespace std; struct Node{ int pos,val; }a[100005]; int c[100005]; int Q,n; bool cmp(Node a,Node b){ if(a.val!=b.val) return a.val<b.val; return a.pos<b.pos; } void pz(){ for(int i=n;i>=1;i--){ if(a[i].val<a[i-1].val||(a[i].vala[i-1].val&&a[i].pos<a[i-1].pos)){ swap(a[i],a[i-1]); } } } void py(){ for(int i=1;i<n;i++){ if(a[i].val>a[i+1].val||(a[i].vala[i+1].val&&a[i].pos>a[i+1].pos)){ swap(a[i],a[i+1]); } } } int main(){ cin>>n>>Q; for(int i=1;i<=n;i++){ cin>>a[i].val; a[i].pos=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ c[a[i].pos]=i; } while(Q--){ int cz; cin>>cz; if(cz==1){ int x,t; cin>>x>>t; a[c[x]].val=t; pz(); py(); for(int i=1;i<=n;i++){ c[a[i].pos]=i; } } else{ int x; cin>>x; cout<<c[x]<<endl; } } return 0; }