题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5412
题意
给定一个序列a[1..N]，然后有M个操作。
1 x y：将第x个元素的值改为y
2 x y k：输出[x，y]的第k大元素
解题
不会主席树套树状数组。
用分块水一水。
维护块内有序。
对于查询区间第k大的话，二分答案key。如果key在区间[x，y]中有不少于k个元素比key小，那么key就是可能的答案。R=key，继续二分；否则，key不可能是答案，L=key+1.
而查询有多少个元素比key小：
整块内的直接进行二分。
非整块的暴力统计。
对于修改元素，只需修改第x个元素所在块的值，并重新排序即可。
AC代码
//5200+ms
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;const int maxn=1e5+7;
int n,m,d[maxn],a[maxn];
int num,block,belong[maxn],l[maxn],r[maxn];void build()
{block=(int)sqrt(n+0.5);num=n/block;if(n%block) num++;for(int i=1;i<=n;i++){belong[i]=(i-1)/block+1;d[i]=a[i];}for(int i=1;i<=num;i++)l[i]=(i-1)*block+1,r[i]=i*block;r[num]=n;for(int i=1;i<=num;i++)sort(d+l[i],d+r[i]+1);
}
void update(int x,int y)//复杂度太高
{a[x]=y;for(int i=l[belong[x]];i<=r[belong[x]];i++)//用冒泡排序d[i]=a[i];sort(d+l[belong[x]],d+r[belong[x]]+1);
}int lb,ub;
int query(int x,int y,int k)
{int ans;int L=lb,R=ub;while(L<R)//二分答案mid{int mid=(L+R)>>1;int cnt=0;if(belong[x]==belong[y]){for(int i=x; i<=y; i++)cnt+=mid>=a[i];}else{for(int i=x; i<=r[belong[x]]; i++)cnt+=mid>=a[i];for(int i=l[belong[y]]; i<=y; i++)cnt+=mid>=a[i];for(int i=belong[x]+1; i<belong[y]; i++)cnt+=upper_bound(d+l[i],d+r[i]+1,mid)-(d+l[i]);}if(cnt>=k)//至少k个数不大于mid{ans=mid;//一开始写成了ans=k，我怎么会写这么蠢的bug（雾)// cout<<"mid="<<mid<<endl;R=mid;}elseL=mid+1;}return ans;
}
int main()
{while(~scanf("%d",&n)){lb=1e9,ub=0;for(int i=1; i<=n; i++)scanf("%d",&a[i]),lb=min(lb,a[i]-1),ub=max(ub,a[i]+1);build();scanf("%d",&m);while(m--){int op;int x,y,k;scanf("%d%d%d",&op,&x,&y);if(op==2)scanf("%d",&k),printf("%d\n",query(x,y,k));elseupdate(x,y);}}return 0;
}