关键词：
题意：给你一个矩阵，q次操作，每次查询长宽l的矩阵最大值a和最小值b，然后把中间点换成floor((a+b)/2)，
解法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过来，因为此时的外层树维护的是x轴区间最大和区间最小，需要从x轴两个更小的区间树合并起来更新
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-8; const int N=800+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; int c[N][N],n; struct segtreeinsegtree int ma[N<<2][N<<2],mi[N<<2][N<<2]; bool leaf; void pushupx(int id,int rt) ma[id][rt]=max(ma[id<<1][rt],ma[id<<1|1][rt]); mi[id][rt]=min(mi[id<<1][rt],mi[id<<1|1][rt]); void pushupy(int id,int rt) ma[id][rt]=max(ma[id][rt<<1],ma[id][rt<<1|1]); mi[id][rt]=min(mi[id][rt<<1],mi[id][rt<<1|1]); void buildy(int id,int x,int l,int r,int rt) if(l==r) if(leaf)ma[id][rt]=mi[id][rt]=c[x][l]; else pushupx(id,rt);//,printf("%d %d %d %d\n",id,x,ma[id][rt]); return ; int m=(l+r)>>1; buildy(id,x,ls);buildy(id,x,rs); pushupy(id,rt); void buildx(int xl,int xr,int rt,int yl,int yr) if(xl==xr)leaf=1;buildy(rt,xl,yl,yr,1);return ; int m=(xl+xr)>>1; buildx(xl,m,rt<<1,yl,yr); buildx(m+1,xr,rt<<1|1,yl,yr); leaf=0,buildy(rt,xl,yl,yr,1); void updatey(int id,int posx,int posy,int c,int l,int r,int rt) if(l==r) if(leaf)ma[id][rt]=mi[id][rt]=c; else pushupx(id,rt); return ; int m=(l+r)>>1; if(posy<=m)updatey(id,posx,posy,c,ls); else updatey(id,posx,posy,c,rs); pushupy(id,rt); void updatex(int posx,int posy,int c,int l,int r,int rt) if(l==r)leaf=1;updatey(rt,posx,posy,c,1,n,1);return ; int m=(l+r)>>1; if(posx<=m)updatex(posx,posy,c,ls); else updatex(posx,posy,c,rs); leaf=0,updatey(rt,posx,posy,c,1,n,1); int querymay(int id,int L,int R,int l,int r,int rt) if(L<=l&&r<=R)return ma[id][rt]; int m=(l+r)>>1,ans=0; if(L<=m)ans=max(ans,querymay(id,L,R,ls)); if(m<R)ans=max(ans,querymay(id,L,R,rs)); return ans; int querymax(int xl,int xr,int yl,int yr,int l,int r,int rt) if(xl<=l&&r<=xr)return querymay(rt,yl,yr,1,n,1); int m=(l+r)>>1,ans=0; if(xl<=m)ans=max(ans,querymax(xl,xr,yl,yr,ls)); if(m<xr)ans=max(ans,querymax(xl,xr,yl,yr,rs)); return ans; int querymiy(int id,int L,int R,int l,int r,int rt) if(L<=l&&r<=R)return mi[id][rt]; int m=(l+r)>>1,ans=1e9+10; if(L<=m)ans=min(ans,querymiy(id,L,R,ls)); if(m<R)ans=min(ans,querymiy(id,L,R,rs)); return ans; int querymix(int xl,int xr,int yl,int yr,int l,int r,int rt) if(xl<=l&&r<=xr)return querymiy(rt,yl,yr,1,n,1); int m=(l+r)>>1,ans=1e9+10; if(xl<=m)ans=min(ans,querymix(xl,xr,yl,yr,ls)); if(m<xr)ans=min(ans,querymix(xl,xr,yl,yr,rs)); return ans; int query(int x,int y,int l) int xl=max(1,x-l/2),xr=min(n,x+l/2); int yl=max(1,y-l/2),yr=min(n,y+l/2); int ma=querymax(xl,xr,yl,yr,1,n,1); int mi=querymix(xl,xr,yl,yr,1,n,1); // printf("%d %d\n",ma,mi); int ans=floor(1.0*(ma+mi)/2); updatex(x,y,ans,1,n,1); return ans; void debug(int id,int l,int r,int rt) printf("%d %d %d %d\n",l,r,ma[id][rt],mi[id][rt]); if(l==r)return ; int m=(l+r)>>1; debug(id,ls);debug(id,rs); s; int main() int T,cnt=0;scanf("%d",&T); while(T--) scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&c[i][j]); s.buildx(1,n,1,1,n); // s.debug(5,1,n,1); int q;scanf("%d",&q); printf("Case #%d:\n",++cnt); while(q--) int x,y,l; scanf("%d%d%d",&x,&y,&l); printf("%d\n",s.query(x,y,l)); return 0; /*********************** 1 3 1 2 3 4 5 6 7 8 9 5 2 2 1 ***********************/
树套树(代码片段)
树套树一种思想，就是一棵树的节点是另一颗树。在外面的叫外层树，在里面的叫内层树。外层树一般是，树状数组，线段树内层树一般是平衡树，STL,线段树线段树套STL/**@Author:zhl*@Date:2020-11-1612:50:32*/#include<bits/stdc++.h>#define... 查看详情
树套树初探(代码片段)
最近学了学树套树，做了几道模板题。发现好像有点水咳咳咳。树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点... 查看详情
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
hdu4819mosaic树套树(代码片段)
...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情
「题解」树套树tree(代码片段)
本文将同步发布于：洛谷博客；csdn；博客园；简书。题目题目描述给你一个\\(n\\)个点的小树（正常的树），给你一个\\(m\\)个点的大树，大树的节点是一棵小树，大树的边是跨越了两棵小树之间的边，\\(q\\)次询问，求树上距离... 查看详情
hdu6096树套树(代码片段)
思路：网上的题解有AC自动机的，有trie树的，还有（乱搞？）的 首先把输入的那n个串按照字典序排序，把n个串翻转以后再按照字典序排序这样我们发现，查的前缀在字典序排序后是一段区间，查的后缀翻转一下在翻转后的... 查看详情
「luogu3380」模板二逼平衡树（树套树）(代码片段)
「luogu3380」【模板】二逼平衡树（树套树）传送门我写的树套树——线段树套平衡树。线段树上的每一个节点都是一棵( extFHQTreap)，然后我们就可以根据平衡树的基本操作以及线段树上区间信息可合并的性质来实现了，具体细节... 查看详情
4889:[tjoi2017]不勤劳的图书管理员树套树(代码片段)
...惯例的题面(Bzoj没有，洛谷找的):动态加权逆序对，一眼树套树。256MB内存，5e4范围，不虚不虚。首先把交换改成两个插入和两个删除。考虑插入和删除的贡献，就是统计前面比这个值大的数的数值和，数量和，后面比这个值小的... 查看详情
97:cf983e倍增+树套树(代码片段)
$des$一棵$n$个点的树，树上有$m$条双向的公交线路，每条公交线路都在两个节点之间沿最短路径往返。$q$次询问从一个点要到达另一个点，在只坐公交的情况下，至少需要坐几辆公交车；或者判断无法只坐公交到达。$n,m,q<=2 ime... 查看详情
树套树(代码片段)
历时三天终于打过了树套树 激动激动激动写个博客纪念一下 二逼平衡树~//luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<stack>#include<queue>usingna... 查看详情
线段树树套树杭电ojluckandlove(代码片段)
博客主页:https://blog.csdn.net/qq_50285142欢迎点赞👍收藏✨关注❤留言📝如有错误，敬请指正🎈虽然生活很难，但我们也要一直走下去🎈题目链接思路：问题是要询问满足两个区间的最大缘分值，因为... 查看详情
二逼平衡树（树套树）(代码片段)
第一次写树套树，在一定帮助下学习，调码3h。用线段树套平衡树，对于区间内排名的查询可以解决了；//$O(log^2n)$对于查询区间排名为k的数，二分答案再判断；//$O(log^3n)$修改数值直接修改；//$O(log^2n)$前驱后继，线段树递归区间... 查看详情
二维线段树之树套树(代码片段)
1//poj1195二维线段树之树套树2//先确定横坐标所在的区间并记录该结点的编号p，然后再确定纵坐标所在的区间并记录该结点的编号cur，则tree[cur][p]为目标区间。3#include<cstdio>4#include<cstdlib>5#include<cstring>6#include<cmath&g... 查看详情
「模板」树套树
「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过，但我删除SBT点的时候没回收内存！写了就RE！先放上来吧，回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情
洛谷p3380模板二逼平衡树（树套树，树状数组，线段树）(代码片段)
洛谷题目传送门emm。。。题目名写了个平衡树，但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧。就像dynamicranking那样（蒟蒻的Sol,放一个link骗访问量233）所有的值（包括初始a数组，操作1、3、4、5的k）全部先... 查看详情
模板二逼平衡树（树套树）(代码片段)
...但是码量绝对是很大的一种方法居然控制在了6KB以内线段树套红黑树（逃这是一次前所未有的尝试因为线段树套平衡树求区间第(k)小复杂度是(mathrmO(log^3n))的所以速度比不上树状数组套线段树但是应该在线段树套平衡树的代码中... 查看详情
p3759[tjoi2017]不勤劳的图书管理员[树套树](代码片段)
树套树是什么啊我不知道/dk我只知道卡常数w//byIsaunoya#pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize("Ofast")#pragmaGCCoptimize("inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falig... 查看详情