链接：E-速度即转发_牛客挑战赛48 (nowcoder.com)

题意：给定长度为 \(n\) 的序列 \(a\) ，共进行 \(m\) 次操作，有两种操作：

1.给定 \(l,r,k\)，查询区间内满足 \(S(x)>=k\) 的最大 \(x(x \in [0,10^5])\) ，S函数定义为 \(S(x)=\sum_{i=l}^{r} \max(a_{i}-x,0)\)。

2.给定 \(p,k\)，将 \(a_{p}\) 修改为 \(k\)。

前置知识：主席树，树状数组，树套树，动态开点线段树。

题解：首先，观察 \(S\) 函数的定义可以发现 \(S\) 函数的值与区间 \([l,r]\) 的值域有关。我们需要维护的是区间内大于 \(x\)（二分去得到 \(x\) ）的所有数的和 \(sum\) 及个数 \(num\) ，然后结果 \(S(x)=\sum_{i=l}^{r} sum-x*num\)，对比 \(S(x)\) 函数值是否大于 \(k\) 可以继续二分下去。那么维护区间值域主席树显然是一种不错的选择。但此时还有第二种修改操作，那么我们就需要动态修改我们的主席树。

动态修改其实也很容易。我们先考虑一个问题，给定一段序列，多次询问区间 \([l,r]\) 的和。这一看很显然可以直接前缀和去做，但如果此时加入了修改操作，我们就可以用树状数组来维护前缀和。其实树套树也是这个意思。静态主席树维护的是前缀和，那么现在有修改操作了，我们就用树状数组来维护主席树的前缀和，就可以做到动态主席树了。因为在主席树地基础上套了树状数组，那么单次查询修改地复杂度是 \(O(\log^2{n})\)。因此整套流程下来修改的复杂度是 \(O(n \log^2{n})\)，但是查询操作的时候因为在二分 \(x\) ，就会导致查询复杂度带 \(3\) 个 \(\log\)，这显然很难在\(10^5\) 的数据下在 \(3s\) 内跑过去。

仔细观察我们发现，其实我们每次在二分 \(x\) 后查找的是区间 \([l,r]\) 大于等于 \(x\) 的函数值 \(S(x)\) 去判断的，但是既然线段树（主席树其实就是很多棵线段树）本质上也是在二分，那么我们不需要在外层二分 \(x\) ，只需要在查询时先计算右边的最大函数值是否大于k即可直到要往那边跳，最后跳到 \(l==r\) 的位置即是答案。由 \(S(x)=\sum_{i=l}^{r} a_{i}*[a_{i}>mid]-x*\sum_{i=l}^{r}[a_{i}>mid]>=k\) 知 \(x\) 取最小时函数值最大（其中 \(mid\) 是指大于中点的右区间，或者说是右值域），那 \(x\) 取 \(mid+1\) 时去判断是否大于等于 \(k\) 即可。然后查询的复杂度也被压缩到 \(O(n*\log^2{n})\)。于是可以很愉快的通过此题了。

细节：注意查询时得保留跳左子树时得保留右边值域的值和与点数和，因为一跳到左子树下次计算时是不会把此次右值域的值计入的，需要作为参数保留。

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int N=1e5;

ll sum[maxn<<7],a[maxn],n,m,op,u,v,w;
int ls[maxn<<7],rs[maxn<<7],sz[maxn<<7],rt[maxn],now;
int qx[100],tx,qy[100],ty;

template<class T>inline
bool read(T&x)
{
	x=0; char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return ch!=EOF;
}

template<class A,class...B>inline
bool read(A&x,B&...y)
{
	return read(x)&&read(y...); 
}

template<class T>inline
void print(T x)
{
	if(x<0)putchar('-'),x=-x;
	int t[30]={0},pos=0;
	while(x)t[++pos]=x%10,x/=10;
	if(!pos)putchar('0');
	else while(pos)putchar(t[pos--]+'0');
	return;
}

template<class T>inline
void print(T x,char ch)
{
	print(x),putchar(ch);
}

inline int lowbit(int x)
{
	return x&(-x);
}

int update(int&t,int l,int r,ll pos,ll up)
{
	if(!t)t=++now;
	sum[t]+=pos*up,sz[t]+=up;
	if(l==r)return t; 
	int mid=l+r>>1;
	if(pos<=mid)update(ls[t],l,mid,pos,up);
	else update(rs[t],mid+1,r,pos,up);
	return t;
}

ll query(int l,int r,ll as,ll az,ll k)
{
	if(l==r)return l;
	int mid=l+r>>1;
	ll sml=0,nml=0,smr=0,nmr=0,sm,nm;
	for(int i=1;i<=tx;i++)sml+=sum[rs[qx[i]]],nml+=sz[rs[qx[i]]];
	for(int i=1;i<=ty;i++)smr+=sum[rs[qy[i]]],nmr+=sz[rs[qy[i]]];
	sm=smr-sml,nm=nmr-nml;
	if(as+sm-(nm+az)*(mid+1)<k)
	{
		for(int i=1;i<=tx;i++)qx[i]=ls[qx[i]];
		for(int i=1;i<=ty;i++)qy[i]=ls[qy[i]];
		return query(l,mid,as+sm,az+nm,k);
	}
	else
	{
		for(int i=1;i<=tx;i++)qx[i]=rs[qx[i]];
		for(int i=1;i<=ty;i++)qy[i]=rs[qy[i]];
		return query(mid+1,r,as,az,k);
	}
	return -1;
}

void modify(int x,ll pos,ll up)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		rt[i]=update(rt[i],-1,N,pos,up);
	}
	return;
}

int main()
{
//  	freopen("LCA.in","r",stdin);
	read(n,m);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		modify(i,a[i],1);
	}
	for(int i=1;i<=m;i++)
	{
		read(op,u,v);
		if(!op)
		{
			read(w); tx=ty=0; 
			for(int j=u-1;j>=1;j-=lowbit(j))qx[++tx]=rt[j];
			for(int j=v;j>=1;j-=lowbit(j))qy[++ty]=rt[j];
			print(query(-1,N,0,0,w),'\n');
		}
		else
		{
			modify(u,a[u],-1);
			modify(u,v,1);
			a[u]=v;
		}
	}
	return 0;
}