Niuke challenge 48 e speed instant forwarding (tree over tree)

link ：E- Speed Forwarding _ Cattle challenge 48 (nowcoder.com)

The question ： Given length is $n$ Sequence $a$ , Together with $m$ operations , There are two operations ：

1. Given $l,r,k$, The query interval satisfies $S(x)>=k$ Maximum $x(x\in [0,10^5])$ ,S The function is defined as $S(x)={\sum }_{i=l}^r\max (a_i-x,0)$.

2. Given $p,k$, take $a_p$ It is amended as follows $k$.

Pre knowledge ： Chairman tree , Tree array , Tree cover tree , Dynamic open point line segment tree .

Answer key ： First , Observe $S$ The definition of the function can be found $S$ The value and interval of a function $[l,r]$ The value range of . What we need to maintain is that the interval is greater than $x$（ Two points to get $x$ ） The sum of all the Numbers $sum$ And number $num$ , And then the result $S(x)=sum-x\ast num$, contrast $S(x)$ Whether the function value is greater than $k$ Can continue to two points . It is obviously a good choice to maintain the chairman tree of the interval value range . But there is a second modification operation , Then we need to dynamically modify our chairman tree .

Dynamic modification is also easy . Let's start with a question , Given a sequence , Ask the interval several times $[l,r]$ And . Obviously, this can be done directly , However, if the modification operation is added at this time , We can use tree arrays to maintain prefixes and . In fact, it also means "tree over tree" . The static chairman tree maintains prefixes and , Now there is a modification operation , We use the tree array to maintain the prefix and , The dynamic chairman tree can be achieved . Because a tree array is set on the basis of the chairman tree , So the complexity of a single query modification is $O({\log }^{2}n)$. Therefore, the complexity of the whole process is $O(q{\log }^{2}n)$, But the query operation is divided into two parts $x$ , This will result in a query complexity band $3$ individual $\log$, It is obviously difficult to $10^5$ Under the data of $3s$ Run inside .

Observe carefully and we find that , In fact, we are at two points each time $x$ The next search is the interval $[l,r]$ Greater than or equal to $x$ Function value of $S(x)$ To judge , But since the segment tree （ The chairman tree is actually a lot of segment trees ） In essence, it is also in dichotomy , Then we don't need to split in the outer layer $x$ , You only need to calculate whether the maximum function value on the right is greater than k Until you want to jump that way , Finally jump to $l==r$ The position of is the answer . from $S(x)={\sum }_{i=l}^r{a}_i\ast [a_i>mid]-x\ast {\sum }_{i=l}^r[a_i>mid]>=k$ know $x$ Take the minimum function value to the maximum （ among $mid$ Is the right section greater than the midpoint , Or right range ）, that $x$ take $mid+1$ Determine whether it is greater than or equal to $k$ that will do . Then the query complexity is compressed to $O(n\ast {\log }^{2}n)$. So I can pass this question happily .

details ： Note that when jumping the left subtree during query, the sum of values and points in the right value field must be preserved , Because once you jump to the left subtree, the value of the right value field will not be included in the next calculation , It needs to be reserved as a parameter .

#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;
}