#include <stdio.h> #include <algorithm> using namespace std; struct st{ int x,v; }a[8008],b[8008]; int c[8008]; int n; int fr(); // fast read void fw( int N ); // fast write void change_sort(int xa,int v); bool cmp(st x,st y) { return x.v<y.v; } int main() { int q,cmd,x,v; n=fr(); q=fr(); for (int i=1;i<=n;++i) { a[i].x=i; a[i].v=fr(); b[i].x=i; b[i].v=a[i].v; } // 初始排序 stable_sort (b+1,b+n+1,cmp); // b[] = sorted a[] for (int j=1; j<=n; j++) c[ b[j].x ]=j; // c[]表用于a[]-b[]位置转换 while (q--) { cmd=fr(); if (cmd==2) { x=fr(); fw( c[x] ) ; // 根据a-b转换表作位置转换 putchar('\n'); } if (cmd==1) { x=fr(); v=fr(); a[x].v=v; change_sort(x,v); //增量插入排序 } } return 0; } void change_sort(int xa,int v) // xa=a[]位置 { int i,j; int x=c[xa]; // x: b[] pos, xa在b[]的位置 b[x].v=v; if (v>b[x-1].v) // 向后搜索 { for ( i=x+1;i<=n;i++) if ( v<=b[i].v ) { while (v==b[i].v && xa > b[i].x) i++; i--; // 插入点=i for (j=x;j<i;j++) { b[j].v=b[j+1].v; b[j].x=b[j+1].x; } b[i].v=v; b[i].x=xa; break; } if (i==n+1) // 插入点=n { for (int j=x;j<n;j++) { b[j].v=b[j+1].v; b[j].x=b[j+1].x; } b[n].v=v; b[n].x=xa; } } else if ( x==n || v<b[x+1].v) // 向前搜索 { for ( int i=x-1;i>=0;--i) // v,b[i]>0 if ( v>=b[i].v ) { while (v==b[i].v && xa<b[i].x) --i; i++; // 插入点=i for (int j=x;j>=i+1;--j) { b[j].v=b[j-1].v; b[j].x=b[j-1].x; } b[i].v=v; b[i].x=xa; break; } } else // b[x-1].v= v = b[x+1].v { if ( xa > b[x+1].x ) // 按xa向后搜索 { i=x+2; while (v==b[i].v && xa > b[i].x) i++; i--; // 插入点=i for (j=x;j<i;j++) { b[j].v=b[j+1].v; b[j].x=b[j+1].x; } b[i].v=v; b[i].x=xa; } else if ( xa < b[x-1].x ) // 按xa向前搜索 { i=x-2; while (v==b[i].v && xa<b[i].x) --i; i++; // 插入点=i for (int j=x;j>=i+1;--j) { b[j].v=b[j-1].v; b[j].x=b[j-1].x; } b[i].v=v; b[i].x=xa; } //else{} // x位置不变 } for (j=1; j<=n; j++) c[ b[j].x ]=j; // 更新c-table; return ; } int fr() { int x=0; char ch; do { ch=getchar(); } while( ch<'0'||ch>'9' ); while( ch>='0'&& ch<='9' ){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x; } void fw( int N ) { if (N>9) fw( N/10 ); putchar( N%10 + '0' ); return; }