网站的推广运营,东莞市城乡和住房建设局,网站注册短信验证怎么做,wordpress美化文章目录问题解析单点修改询问完整代码标记永久化代码所谓二维线段树#xff0c;就是有两个维度的线段树 (逃)
问题
给出一个矩形 要求支持以下操作#xff1a; 1.询问一个子矩形的最值 2.修改某一个单点的值 解析
使用线段树套线段树#xff0c;来解决二维动态问题 注意…
文章目录问题解析单点修改询问完整代码标记永久化代码所谓二维线段树就是有两个维度的线段树 (逃)
问题
给出一个矩形 要求支持以下操作 1.询问一个子矩形的最值 2.修改某一个单点的值 解析
使用线段树套线段树来解决二维动态问题 注意这个东西只能支持单点修改区间查询 区间改直接死翘翘
对于x轴开一个线段树 每个结点对应一个y方向[1,n]的长条 时空复杂度qlogn2qlogn^2qlogn2
在求和问题时不妨用map套树状树组 就可以支持区间修改了 而且代码号写许多 但缺陷是时间复杂度由于套map变成了3log 跑得飞慢qwq
单点修改
由于这个矩形可能很大比如长宽1e5级别 我们可能无法把整棵线段树存下来 所以使用x方向直接开y方向动态开点 为什么x方向不动态开点因为那实在是太不好写了… 那如果长宽1e9级别怎么办你去死吧
注意x方向修改完往上递归的时候要递归到对应的y方向的叶子更新信息 具体实现的时候我开了一个mapmpi,jmp_{i,j}mpi,j记录x方向编号为i的树的y方向上j号叶子结点的编号如果没看明白看代码就清楚了 这样时空复杂度还是对的 注意map赋值的位置不然可能使你凭空变成三个log
mapint,intmp[N2];
void change(int line,int k,int l,int r,int p,int v,int flag0){if(!k){kNew();if(lr) mp[line][p]k;}if(lr){if(flag0) tr[k].mxtr[k].mnv;else{int Lmp[line1][p],Rmp[line1|1][p];tr[k].mxmax(tr[L].mx,tr[R].mx);tr[k].mnmin(tr[L].mn,tr[R].mn);}return;}if(pmid) change(line,tr[k].ls,l,mid,p,v,flag);else change(line,tr[k].rs,mid1,r,p,v,flag);pushup(k);return;
}
void Add(int k,int l,int r,int x,int y,int v){if(lr){change(k,rt[k],1,n,y,v,0);return;}if(xmid) Add(k1,l,mid,x,y,v);else Add(k1|1,mid1,r,x,y,v);change(k,rt[k],1,n,y,v,1);return;
}询问
二维线段树主要难写的地方其实就是修改 询问相比之下就比较常规了 直接递归到对应的树上取答案即可 这里贴一个取max的
int askmx(int k,int l,int r,int x,int y){if(!k) return -2e9;if(xlry){return tr[k].mx;}int res-2e9;if(xmid) Max(res,askmx(tr[k].ls,l,mid,x,y));if(ymid) Max(res,askmx(tr[k].rs,mid1,r,x,y));return res;
}
int Querymx(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1lrx2){return askmx(rt[k],1,n,y1,y2);}int res-2e9;if(x1mid) Max(res,Querymx(k1,l,mid,x1,y1,x2,y2));if(x2mid) Max(res,Querymx(k1|1,mid1,r,x1,y1,x2,y2));return res;
}完整代码
板子题
#includebits/stdc.h
using namespace std;
#define ll long long
#define il inline
const int N850;
const int M3e6100;
const int mod998244353;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;inline void Max(int x,int y){xmax(x,y);}
inline void Min(int x,int y){xmin(x,y);}
int rt[N2];
struct tree{int mx,mn,ls,rs;
}tr[M];
int tot;
#define mid ((lr)1)
inline int New(){tot;tr[tot].mx-2e9;tr[tot].mn2e9;tr[tot].lstr[tot].rs0;return tot;
}
inline void pushup(int x){tr[x].mxmax(tr[tr[x].ls].mx,tr[tr[x].rs].mx);tr[x].mnmin(tr[tr[x].ls].mn,tr[tr[x].rs].mn);return;
}
mapint,intmp[N2];
void change(int line,int k,int l,int r,int p,int v,int flag0){if(!k){kNew();if(lr) mp[line][p]k;}if(lr){if(flag0) tr[k].mxtr[k].mnv;else{int Lmp[line1][p],Rmp[line1|1][p];tr[k].mxmax(tr[L].mx,tr[R].mx);tr[k].mnmin(tr[L].mn,tr[R].mn);}return;}if(pmid) change(line,tr[k].ls,l,mid,p,v,flag);else change(line,tr[k].rs,mid1,r,p,v,flag);pushup(k);return;
}
void Add(int k,int l,int r,int x,int y,int v){if(lr){change(k,rt[k],1,n,y,v,0);return;}if(xmid) Add(k1,l,mid,x,y,v);else Add(k1|1,mid1,r,x,y,v);change(k,rt[k],1,n,y,v,1);return;
}
int askmn(int k,int l,int r,int x,int y){if(!k) return 2e9;if(xlry){return tr[k].mn;}int res2e9;if(xmid) Min(res,askmn(tr[k].ls,l,mid,x,y));if(ymid) Min(res,askmn(tr[k].rs,mid1,r,x,y));return res;
}
int askmx(int k,int l,int r,int x,int y){if(!k) return -2e9;if(xlry){return tr[k].mx;}int res-2e9;if(xmid) Max(res,askmx(tr[k].ls,l,mid,x,y));if(ymid) Max(res,askmx(tr[k].rs,mid1,r,x,y));return res;
}
int Querymx(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1lrx2){return askmx(rt[k],1,n,y1,y2);}int res-2e9;if(x1mid) Max(res,Querymx(k1,l,mid,x1,y1,x2,y2));if(x2mid) Max(res,Querymx(k1|1,mid1,r,x1,y1,x2,y2));return res;
}
int Querymn(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1lrx2){return askmn(rt[k],1,n,y1,y2);}int res2e9;if(x1mid) Min(res,Querymn(k1,l,mid,x1,y1,x2,y2));if(x2mid) Min(res,Querymn(k1|1,mid1,r,x1,y1,x2,y2));return res;
}
int main(){tr[0].mx-2e9;tr[0].mn2e9;scanf(%d,n);//if(o3) break;memset(rt,0,sizeof(rt));tot0;for(int i1;in;i){for(int j1;jn;j){int xread();Add(1,1,n,i,j,x);}}mread();for(int i1;im;i){char c;scanf( %c,c);if(cc){int xread(),yread(),vread();Add(1,1,n,x,y,v);}else{int x1read(),y1read(),x2read(),y2read();int mxQuerymx(1,1,n,x1,y1,x2,y2),mnQuerymn(1,1,n,x1,y1,x2,y2);printf(%d %d\n,mx,mn);}}return 0;
}
/*
3 1
3 1 33 2
1 1 2
3 1 3
*/
标记永久化
尽管二维线段树无法实现区间赋值 但是在一些特殊的情况下可以通过骚操作使其具有区间赋值的功能 那就是这个标记永久化 大概的思路就是x和y方向上都建两棵树一棵是区间的最大值mx一棵存该区间整体赋过的最大值tag 修改的时候沿途对所有的mx更新并对最终子区间的tag更新 询问的时候如果是子区间直接返回mx否则先把res赋值成tag再递归尝试更新这个res 确实是挺妙的 但这个东西是有局限性的 就像它的名字一样这个标记无法撤销 比如维护最大值的时候如果可以把值改小就炸了 更具体的细节看代码吧
代码
板子
#includebits/stdc.h
using namespace std;
#define ll long long
#define debug(a,b) fprintf(stderr,a,b)
const int N1030;
const int mod1e97;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n,m,k;
struct node{int mx,tag,ls,rs;
}tr[N*N*15];
int mx[N2],tag[N2],tot;
#define mid ((lr)1)
int ask(int k,int l,int r,int x,int y){if(!k) return 0;if(xlry){//printf(ask:k%d (%d %d) (%d %d) mx%d\n,k,l,r,x,y,tr[k].mx);return tr[k].mx;}int restr[k].tag;//printf(ask:k%d (%d %d) (%d %d) tag%d\n,k,l,r,x,y,tr[k].tag);if(xmid) resmax(res,ask(tr[k].ls,l,mid,x,y));if(ymid) resmax(res,ask(tr[k].rs,mid1,r,x,y));return res;
}
int Query(int k,int l,int r,int x1,int y1,int x2,int y2){if(x1lrx2){int oask(mx[k],1,m,y1,y2);//printf(Query:k%d (%d %d) [(%d %d),(%d %d)] mx%d\n,k,l,r,x1,y1,x2,y2,o);return o;}int resask(tag[k],1,m,y1,y2);//printf(Query:k%d (%d %d) [(%d %d),(%d %d)] tag%d\n,k,l,r,x1,y1,x2,y2,res);if(x1mid) resmax(res,Query(k1,l,mid,x1,y1,x2,y2));if(x2mid) resmax(res,Query(k1|1,mid1,r,x1,y1,x2,y2));return res;
}
void change(int k,int l,int r,int x,int y,int v){if(!k) ktot;tr[k].mxmax(tr[k].mx,v);if(xlry){//printf(change:k%d (%d %d) (%d %d) tag:v%d\n,k,l,r,x,y,v);tr[k].tagmax(tr[k].tag,v);return;}if(xmid) change(tr[k].ls,l,mid,x,y,v);if(ymid) change(tr[k].rs,mid1,r,x,y,v);return;
}
void Add(int k,int l,int r,int x1,int y1,int x2,int y2,int v){change(mx[k],1,m,y1,y2,v);if(x1lrx2){change(tag[k],1,m,y1,y2,v);return;}if(x1mid) Add(k1,l,mid,x1,y1,x2,y2,v);if(x2mid) Add(k1|1,mid1,r,x1,y1,x2,y2,v);return;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endif//printf(%d\n,sizeof(tr)/1024/1024);nread();mread();kread();n;m;for(int i1;ik;i){int lread(),wread(),hread(),xread(),yread();x;y;int x1x,y1y,x2xl-1,y2yw-1;int mxQuery(1,1,n,x1,y1,x2,y2);Add(1,1,n,x1,y1,x2,y2,mxh);//printf((%d %d) (%d %d) mx%d - %d\n,x1,y1,x2,y2,mx,mxh);}printf(%d\n,Query(1,1,n,1,1,n,m));return 0;
}
