链接:hdu5412
题解
- 注意这题是单点修改，整体二分一下就可以AC，一发过。。。
- 把所有修改操作看成把这个点删了，再加上一个数。
- 每次二分一个mid，对于要修改的数小于（因为求得是第k大）这个值，直接加上然后放到左区间,否则放到右区间，对于查询操作，如果这个区间内大于mid的数x小于k那么显然答案应该比mid大，k-=x后放到右区间，否则放到左区间，注意这里的顺序是不能改变的QAQ
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
const int N=1e6+7;
const int inf=0x3f3f3f3f;
int n,m,ans[N],tr[N],a[N];
struct node{
int x,y,k,cnt,num;
inline void init(int _x,int _y,int _k,int _cnt,int _num){x=_x;y=_y;k=_k;cnt=_cnt;num=_num;}
}q[N],b[N];
inline void update(int x,int y){for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;}
inline int query(int x){ll res=0;for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
void solve(int L,int R,int LL,int RR){
if(LL==RR){rep(i,L,R)if(q[i].k)ans[q[i].num]=LL;return ;}
int mid=LL+RR>>1,l=L,r=R;
rep(i,L,R){
if(q[i].k){
q[i].cnt=query(q[i].y)-query(q[i].x-1);
if(q[i].cnt<q[i].k)q[i].k-=q[i].cnt,b[r--]=q[i];
else b[l++]=q[i];
}
else {
if(q[i].y<=mid)b[l++]=q[i],update(q[i].x,q[i].cnt);
else b[r--]=q[i];
}
}
rep(i,L,R)if(!q[i].k&&q[i].y<=mid)update(q[i].x,-q[i].cnt);
rep(i,L,l-1)q[i]=b[i];
for(int i=l,j=R;i<=R;--j,++i)q[i]=b[j];
if(l!=L)solve(L,l-1,LL,mid);
if(r!=R)solve(r+1,R,mid+1,RR);
}
int main(){
while(~scanf("%d",&n)){
int len=0;
rep(i,1,n){scanf("%d",&a[i]);q[++len].init(i,a[i],0,1,0);}
scanf("%d",&m);
rep(i,1,m){
int op;scanf("%d",&op);
if(op&1){
int x,y;
scanf("%d%d",&x,&y);
q[++len].init(x,a[x],0,-1,0);
q[++len].init(x,y,0,1,0);
a[x]=y;
ans[i]=0;
}
else {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
q[++len].init(x,y,z,0,i);
}
}
solve(1,len,1,inf);
rep(i,1,m)if(ans[i])printf("%d\n",ans[i]);
}
return 0;
}