讲的都是一些自己不太想得到的题目
1.区间取min，区间查询最大值，区间求和
这个之前做过
记录区间最大值mx1，次大值mx2，最大值个数
插入的时候分情况讨论
if (mx1<x) 不做
if (max1>=x&&max2<x) 赋值max1
不然就递归下去
复杂度势能分析我没仔细学。。。
2.区间取min，区间加，区间求和
和上一题的区别在于有了区间加，延用上一题的处理办法就可以了
3.区间取min，区间取max，区间求和
变成维护6个标记
7.区间修改，区间赋值，查询区间最大值，查询历史区间最大值
如果没有区间赋值，我们可以增加一个历史lazy最大值这么一个标记
有了区间赋值我们发现这个并不能维护
但我们注意到一旦一个区间被区间赋值之后，对它进行区间加等同于区间赋值
于是我们对区间分类
9.
和7有点像
我们注意到把某个地方权值等同于修改[i,j]（其中i<=x,j>=x）
区间赋值操作需要时间先后（就是先打哪个标记是有影响的）
所以这个东西不能用二维线段树来搞。。
但是kd-tree可以解决
（二维的除了线段树（同类的）和kd-tree还有其他东西么。。。）
kd-tree我们可以先把询问点离线弄出来
kd-tree处理高维问题相比线段树代码肯定是简单的
需要注意的就是 kd-tree还需要维护自己节点的信息
所以我们要记录 当前节点自己最小值 当前节点现在自己的值 当前lazy标记的值 lazy标记未下传的最小值
#include <bits/stdc++.h> using namespace std; #define ll long long #define rint register ll #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define mid ((h+t)>>1) const ll N=2e5+10; const ll INF=1e18; ll n,m,cnt,rt,cmp_d; ll a[N],sum[N]; struct re1{ ll a,b,c; }b[N]; struct re{ ll d[2],v; }p[N]; bool cmp(re x,re y) { return(x.d[cmp_d]<y.d[cmp_d]); } #define umax(x,y) if (x<y) x=y #define umin(x,y) if (x>y) x=y struct kd{ ll ls[N],rs[N],Mx[N],Nx[N],My[N],Ny[N],v[N]; ll lazy[N],mlazy[N],nlazy[N],tlazy[N]; IL void updata(ll x) { if (ls[x]) { umax(Mx[x],Mx[ls[x]]); umax(My[x],My[ls[x]]); umin(Nx[x],Nx[ls[x]]); umin(Ny[x],Ny[ls[x]]); } if (rs[x]) { umax(Mx[x],Mx[rs[x]]); umax(My[x],My[rs[x]]); umin(Nx[x],Nx[rs[x]]); umin(Ny[x],Ny[rs[x]]); } } IL void down(ll x) { if (tlazy[x]<0) { umin(tlazy[ls[x]],lazy[ls[x]]+tlazy[x]); umin(tlazy[rs[x]],lazy[rs[x]]+tlazy[x]); umin(mlazy[ls[x]],nlazy[ls[x]]+tlazy[x]); umin(mlazy[rs[x]],nlazy[rs[x]]+tlazy[x]); } nlazy[ls[x]]+=lazy[x]; nlazy[rs[x]]+=lazy[x]; lazy[ls[x]]+=lazy[x]; lazy[rs[x]]+=lazy[x]; lazy[x]=tlazy[x]=0; } ll build(rint h,rint t,rint o) { cmp_d=o; nth_element(p+h,p+mid,p+t+1,cmp); rint x=mid; Mx[x]=Nx[x]=p[x].d[0]; My[x]=Ny[x]=p[x].d[1]; v[x]=p[x].v; if (h!=x) ls[x]=build(h,mid-1,o^1); else ls[x]=0; if (t!=x) rs[x]=build(mid+1,t,o^1); else rs[x]=0; updata(x); return(x); } void change(ll x,ll hx,ll tx,ll hy,ll ty,ll k) { down(x); if (hx>Mx[x]||tx<Nx[x]||hy>My[x]||ty<Ny[x]) return; if (hx<=Nx[x]&&Mx[x]<=tx&&hy<=Ny[x]&&My[x]<=ty) { lazy[x]+=k; nlazy[x]+=k; if (k<0) tlazy[x]+=k; umin(mlazy[x],nlazy[x]); return; } if (hx<=p[x].d[0]&&p[x].d[0]<=tx&&hy<=p[x].d[1]&&p[x].d[1]<=ty) { nlazy[x]+=k; umin(mlazy[x],nlazy[x]); } if (ls[x]) change(ls[x],hx,tx,hy,ty,k); if (rs[x]) change(rs[x],hx,tx,hy,ty,k); } ll find(ll x,ll p1,ll p2) { if (!x) return(INF); down(x); if (p1>Mx[x]||p1<Nx[x]||p2>My[x]||p2<Ny[x]) return(INF); if (p1==p[x].d[0]&&p2==p[x].d[1]) { return mlazy[x]==INF?v[x]:v[x]+mlazy[x]; } return(min(find(ls[x],p1,p2),find(rs[x],p1,p2))); } }K; int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m; rep(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i]; rep(i,1,m) { ll kk,x,y; cin>>kk>>x>>y; b[i].a=x,b[i].b=y,b[i].c=kk; if (kk==2) { p[++cnt].d[0]=x; p[cnt].d[1]=y; p[cnt].v=sum[y]-sum[x-1]; } } if (cnt) rt=K.build(1,cnt,0); rep(i,1,m) { if (b[i].c==1) { K.change(rt,1,b[i].a,b[i].a,n,b[i].b-a[b[i].a]); a[b[i].a]=b[i].b; } else { cout<<K.find(rt,b[i].a,b[i].b)<<endl; } } return 0; }