啊今天的题一道不会……
所以只把标程代码放上来……
当然如果有一天我研究明白了会给标程附上注释的……
不要指望我自己写题解了（
原题在这里↓
（由于破pdf复制不出来所以纯手打的！知道吗！）
题目描述
给出一个长度为n的正整数数组A，有m次操作，操作有两种：修改和询问
修改：修改A[i]；
询问：输出数组中第k小的正整数的值。
输入输出格式
输入格式
第一行一个正整数n；
第二行n个正整数，第i个数表示A[i]的值；
第三行一个正整数m；
接下来m行，首先读入一个整数op，
op = 1表示修改，接下来读入两个正整数x，y表示把A[i]修改成y
op = 2表示询问，接下来读入一个正整数k，然后输出第k小正整数的值
输出格式
包括若干行，每行一个正整数，表示每个询问的结果
emmmmmm
改题啊在这里（
题目描述
给出含有n个幻想乡少(da)女(ma)的年龄的数组A，有m次操作，操作有两种：修改和询问
修改：修改第i个少女的年龄；
询问：输出数组中第k小的年龄的值。
输入输出格式
输入格式
第一行一个正整数n；
第二行n个正整数，第i个数表示第i个少女的年龄；
第三行一个正整数m；
接下来m行，首先读入一个整数op，
op = 1表示修改，接下来读入两个正整数x，y表示把第i个少女的年龄修改成y
op = 2表示询问，接下来读入一个正整数k，然后输出第k小年龄的值
输出格式
包括若干行，每行一个正整数，表示每个询问的结果
说明
100%:A[i]∈(0,+∞sdfasdfdsgdasfdsgdsfkjhajkewhfkhkfhdkjhfkasjhfsdkfjs
啊那个我也不知道最后怎么了说不定是紫m
不等等我还没把标程题解放上来啊！
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define N 500005 5 using namespace std; 6 int t[N*4],n,m,x,y,a[N],op; 7 int query(int p,int k) 8 { 9 int l=1,r=500000,mid; 10 while (l<r) 11 { 12 mid=(l+r)>>1; 13 if (t[2*p]>=k) p=2*p,r=mid; 14 else k-=t[2*p],p=2*p+1,l=mid+1; 15 } 16 return l; 17 } 18 void insert(int p,int x,int y) 19 { 20 int l=1,r=500000,mid; 21 while (l<r) 22 { 23 mid=(l+r)>>1; 24 t[p]+=y; 25 if (x<=mid) p=2*p,r=mid; 26 else p=2*p+1,l=mid+1; 27 } 28 t[p]+=y; 29 } 30 int main() 31 { 32 freopen("kth.in","r",stdin); 33 freopen("kth.out","w",stdout); 34 scanf("%d",&n); 35 for (int i=1;i<=n;i++) scanf("%d",&a[i]),insert(1,a[i],1); 36 scanf("%d",&m); 37 while (m--) 38 { 39 scanf("%d",&op); 40 if (op==2) 41 scanf("%d",&x),printf("%d ",query(1,x)); 42 else scanf("%d%d",&x,&y),insert(1,a[x],-1),insert(1,a[x]=y,1); 43 } 44 return 0; 45 }
请不要管我 偷懒 因为我 还没吃饭