给出 $n$ 个数，每次有两种操作：

$1 \ i\ x $ ：把第 $i$ 个数改成 $x$ 。

$2\ sum$ ：求最少的前 $k$ 大数，使之和大于等于 $sum$ 。

1
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, M = 2 * N;
const int inf=1e9+1;

int n,m;
int a[N];

struct Node
{
	int l,r,num;
	LL sum;
}tr[4 * M + M * 19];
int tot;

void update(int &id,int l,int r,int pos,int val)
{
    if(id==0)id=++tot;
    tr[id].num+=val;
    tr[id].sum+=pos*val;

    if(l==r)return ;

    int mid=(l+r)>>1;
    if(pos<=mid)update(tr[id].l,l,mid,pos,val);
    else update(tr[id].r,mid+1,r,pos,val);
}

int query(int id,int l,int r,LL sum)
{
    if(l==r)
    {
        if(sum<=0)return 0;
        return (sum+l-1)/l;//一个节点可能有重复的多个数
    }

    int mid=(l+r)>>1;
    if(tr[tr[id].r].sum>sum)return query(tr[id].r,mid+1,r,sum);
    return query(tr[id].l,l,mid,sum-tr[tr[id].r].sum)+tr[tr[id].r].num;
}

int main()
{
    LL sum=0;
    int cnt=0;
    int rt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>0)
        {
            update(rt,1,inf,a[i],1);
        }
    }
    
    for(int i=1;i<=m;i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int pos,t;
        	cin>>pos>>t;
        	update(rt,1,inf,a[pos],-1),cnt--;
        	update(rt,1,inf,t,1),cnt++;
        }
        
        else
        {
            LL sum;
            cin>>sum;
            cout<<query(rt,1,inf,sum)<<endl;
        }
        
    }
    return 0;
}