当时做比赛的时候听说过这类用KD_Tree维护的数据结构题
然后知道是KD_Tree,然而并不知道怎么写QAQ
比赛完了之后%了一发代码
其基本思路是这样的：
1、首先我们把询问[L,R]看成二维平面上的点，那么对于任意修改[p,p]
当且仅当p>=L&&p<=R时会对答案有影响
对应到二维平面就是KD_Tree维护矩形区域和的经典操作啦
2、那么我们考虑对历史最小值的询问
先把修改转换为增量修改
我们可以在KD_Tree上维护两个标记
第一个是当前的ADD
第二个是历史所有的Minadd
这样在更改一下push_down函数就可以完成了
QAQ 高仿的代码，真是羞耻 QAQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std; typedef long long LL;
const int maxn=100010;
const int oo=0x7fffffff;
int n,m,D,cnt,rt;
int A[maxn],type[maxn],L[maxn],R[maxn];
LL Bit[maxn],ans[maxn]; void add(int x,int v){for(int i=x;i<=n;i+=(i&(-i)))Bit[i]+=v;}
LL ask(int x){
LL sum=0;
for(int i=x;i>=1;i-=(i&(-i)))sum+=Bit[i];
return sum;
}
int tot=0;
struct Node{
int d[2],mn[2],mx[2];
int L,R,id;
LL sum,add,ans,Minadd;
bool operator <(const Node &A){return d[D]<A.d[D];}
}t[maxn],tmp[maxn];
void up(int o){
for(int i=0;i<2;++i){
t[o].mn[i]=min(t[o].d[i],min(t[t[o].L].mn[i],t[t[o].R].mn[i]));
t[o].mx[i]=max(t[o].d[i],max(t[t[o].L].mx[i],t[t[o].R].mx[i]));
}return;
}
void push_1(int o,LL v){
if(!o)return;
t[o].ans=min(t[o].ans,t[o].sum+v);
t[o].Minadd=min(t[o].Minadd,t[o].add+v);
}
void push_2(int o,LL v){
if(!o)return;
t[o].sum+=v;t[o].add+=v;
t[o].ans=min(t[o].ans,t[o].sum);
t[o].Minadd=min(t[o].Minadd,t[o].add);
}
void push_down(int o){
if(t[o].Minadd){
push_1(t[o].L,t[o].Minadd);
push_1(t[o].R,t[o].Minadd);
t[o].Minadd=0;
}
if(t[o].add){
push_2(t[o].L,t[o].add);
push_2(t[o].R,t[o].add);
t[o].add=0;
}
}
void modify(int o,int p,int val){
if(!o)return;
push_down(o);
if(t[o].mx[0]<=p&&t[o].mn[1]>=p){push_2(o,1LL*val);return;}
if(t[o].d[0]<=p&&t[o].d[1]>=p)t[o].sum+=val,t[o].ans=min(t[o].ans,t[o].sum);
if(t[t[o].L].mn[0]<=p&&t[t[o].L].mx[1]>=p)modify(t[o].L,p,val);
if(t[t[o].R].mn[0]<=p&&t[t[o].R].mx[1]>=p)modify(t[o].R,p,val);
}
void insert(int &o,int x,int y,int id,int c){
if(!o){
o=++tot;t[o].d[0]=x;t[o].d[1]=y;
t[o].id=id;t[o].sum=t[o].ans=ask(y)-ask(x-1);
up(o);
return;
}
push_down(o);
if(c==0){
if(x<=t[o].d[0])insert(t[o].L,x,y,id,c^1);
else insert(t[o].R,x,y,id,c^1);
}else{
if(y<=t[o].d[1])insert(t[o].L,x,y,id,c^1);
else insert(t[o].R,x,y,id,c^1);
}up(o);
}
void DFS(int o){
if(!o)return;
push_down(o);
DFS(t[o].L);
tmp[++cnt]=t[o];
ans[t[o].id]=t[o].ans;
DFS(t[o].R);
}
void build(int &o,int L,int R,int c){
o=0;if(L>R)return;
int mid=(L+R)>>1;D=c;o=mid;
nth_element(tmp+L,tmp+mid,tmp+R+1);
t[o]=tmp[mid];
build(t[o].L,L,mid-1,c^1);
build(t[o].R,mid+1,R,c^1);
up(o);
}
int main(){
rt=0;
t[0].mn[0]=t[0].mn[1]=oo;
t[0].mx[0]=t[0].mx[1]=-oo;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&A[i]),add(i,A[i]);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&type[i],&L[i],&R[i]);
if(type[i]==1){
add(L[i],R[i]-A[L[i]]);
R[i]=R[i]-A[L[i]];
A[L[i]]+=R[i];
}
}
int blo=2000;
for(int i=m;i>=1;--i){
if(type[i]==1)modify(rt,L[i],-R[i]),add(L[i],-R[i]);
else insert(rt,L[i],R[i],i,0);
if(i%blo==0){
cnt=0;DFS(rt);rt=0;
build(rt,1,cnt,0);
}
}
cnt=0;DFS(rt);
for(int i=1;i<=m;++i){
if(type[i]==2)printf("%lld\n",ans[i]);
}return 0; }