网站建设需要到哪些知识,代运营,那块做微信平台网站,西安注册公司网上申请入口分块点分治Treap byWYCby\ WYCby WYC Part1 分块 概念
就是将nnn个数分成若干个块#xff0c;然后要处理的时候整块一起的加上局部的直接暴力。
如果将块的大小分配好一般每次都是O(n)O(\sqrt n)O(n)的。
而且因为十分暴力#xff0c;所以有很多优秀的性质。 实现方法
…分块点分治Treap
byWYCby\ WYCby WYC Part1 分块 概念
就是将nnn个数分成若干个块然后要处理的时候整块一起的加上局部的直接暴力。
如果将块的大小分配好一般每次都是O(n)O(\sqrt n)O(n)的。
而且因为十分暴力所以有很多优秀的性质。 实现方法
怎么暴力的还用讲实现方法好吧讲一些基础的
要求区间求和区间修改
对于每个块维护一个所以值的和和一个懒惰
区间求和时将整块的直接加上去局部的暴力加上去
区间修改时将整块的懒惰标记局部的暴力加上去
对于局部修改时如果有懒惰就直接暴力将整个块都修改然后去掉懒惰。
时间复杂度每个都是O(n)O(\sqrt n)O(n)
是不是十分优秀 例题
在例题中体现优秀的性质 P4168-[Violet]蒲公英
题目大意
询问区间众数
解题思路
将数字离散化然后分块。对于数组vi,j,kv_{i,j,k}vi,j,k表示i∼ji\sim ji∼j个块kkk的个数。对于询问(l,r)(l,r)(l,r)将整块的直接累计然后局部的直接暴力。
时间复杂度:O(NT2MNT)O(NT^2\frac{MN}{T})O(NT2TMN)根据LYD的说法让T≈n3T\approx \sqrt[3]nT≈3n的话时间复杂度就可以在O(N53)O(N^{\frac{5}{3}})O(N35)级别。
代码写优美些或者加点优化就可以过。
code
#includecstdio
#includecmath
#includealgorithm
#includecstring
#define Tn 40
#define N 40010
using namespace std;
int n,m,L[Tn],R[Tn],v[Tn][Tn][N],l,r,num[N];
int z[N],w[N],a[N],cnt,k[N],t,T,pos[N],x;
bool cmp(int x,int y)//排序
{return z[x]z[y];}
void begins()//预处理
{for(int i1;it;i){L[i](i-1)*T1;R[i]i*T;}if(R[t]n) t,L[t]R[t-1]1,R[t]n;//计算边界for(int i1;it;i)for(int ji;jt;j)for(int kL[i];kR[j];k)v[i][j][a[k]];//计算v数组
}
int ask(int l,int r)
{int ppos[l],qpos[r];if(p-q2){memset(k,0,sizeof(k));for(int il;ir;i)k[a[i]];}else{p;q--;for(int i1;icnt;i)k[i]v[p][q][i];//直接累计for(int il;iL[p];i)//暴力统计k[a[i]];for(int iR[q]1;ir;i)//暴力统计*2k[a[i]];}int mark1;for(int i2;icnt;i)//找众数if(k[i]k[mark]) marki;return w[mark];
}
int main()
{scanf(%d%d,n,m);t(int)pow(double(n),1.0/3);Tn/t;for(int i1;in;i){scanf(%d,z[i]);num[i]i;}sort(num1,num1n,cmp);z[0]-1;for(int i1;in;i)//离散化{if(z[num[i]]!z[num[i-1]]) cnt,w[cnt]z[num[i]];;a[num[i]]cnt;}Tn/t;begins();for(int i1;im;i){scanf(%d%d,l,r);l(lx-1)%n1;r(rx-1)%n1;if(lr) swap(l,r);printf(%d\n,xask(l,r));}
}优秀性质1
对于块你可以构建二维的就十分优秀。
如这道题中vi,j,kv_{i,j,k}vi,j,k对于块进行了二维 P4879-ycz的妹子
题目大意
有若干种操作
Cxy:ax−yC\ x\ y:a_x-yC x y:ax−yIxy:I\ x\ y:I x y:加一个(原本有的话就改变)axya_xyaxyQ:Q:Q:询问所以数的和Dx:D\ x:D x:删除第xxx个(有的才算)数。
解题思路
我们发现只有单点修改和全部求和。所以ansansans表示全部的和然后前三个操作就搞定了。 第四个操作维护一个分块记录每块有的数的个数然后找到目标在那个块之后这个块里暴力寻找这个操作时间负责度O(n)O(\sqrt n)O(n)
总体时间复杂度:O(nn)O(n\sqrt n)O(nn)
codecodecode
#includecstdio
#includecmath
#includeiostream
#define ll long long
#define N 500000
#define T 1000
using namespace std;
ll n,m,a[N10],ans,no[N10],x,y,t;
ll L[T],R[T],num[T],pos[N10];
char c;
int main()
{scanf(%lld%lld,n,m);tsqrt(N);for(ll i1;iN;i){pos[i](i-1)/t1;if(in)no[i]1;}for(ll i1;in;i){scanf(%lld,a[i]);num[pos[i]];ansa[i];}for(ll i1;im;i){cinc;if(cQ)printf(%lld\n,ans);else if(cI){scanf(%lld%lld,x,y);ans-a[x];a[x]y;ansy;nmax(n,x);if(no[x]){no[x]0;num[pos[x]];}}else if(cC){scanf(%lld%lld,x,y);if(no[x]) continue;ans-y;a[x]-y;}else if(cD){scanf(%lld,x);ll k1;while(x-num[k]0)x-num[k],k;for(int i(k-1)*t1;imin(k*t,n);i){if(!no[i]) --x;if(!x){num[k]--;no[i]1;ans-a[i];a[i]0;break;}}}}
}优秀性质2
一个块一个块的跑利用储存块的信息快速锁定目标 P3203-[HNOI2010]弹飞绵羊
这个就强大了
题目大意
nnn个装置。到第iii个装置会被往前弹aia_iai个。 两种操作 修改aia_iai和询问从iii出发要多少次弹射可以弹出去。
解题思路
first本题正解LCT。然而分块可以轻松过掉
分块。对于每个点维护要多少步弹出该块和弹出去后弹到哪里。 询问就直接根据两个数据修改就直接重构整个块。
时间复杂度:O(nn)O(n\sqrt n)O(nn)
code
#includecstdio
#includecmath
#define N 200010
#define T 500
using namespace std;
int n,m,x,t,a[N],L[T],R[T],step[N],to[N],pos[N];
void pre_work()//预处理
{for(int i1;it;i)//块边界{L[i](i-1)*t1;R[i]i*t;}if(R[t]!n) t,L[t]R[t-1]1,R[t]n;for(int i1;it;i)for(int jR[i];jL[i];j--){if(ja[j]R[i]) step[j]step[ja[j]]1,to[j]to[ja[j]];else step[j]1,to[j]ja[j];pos[j]i;}//初始数据
}
int ask(int x)//询问
{int ans0;while(xn)ansstep[x],xto[x];return ans;
}
void change(int i)//重构块
{for(int jR[i];jL[i];j--)if(ja[j]R[i]) step[j]step[ja[j]]1,to[j]to[ja[j]];else step[j]1,to[j]ja[j];
}
int main()
{scanf(%d,n);tsqrt(n);for(int i1;in;i)scanf(%d,a[i]);pre_work();scanf(%d,m);for(int i1;im;i){scanf(%d,x);if(x1){scanf(%d,x);x;printf(%d\n,ask(x));}else{scanf(%d,x);x;scanf(%d,a[x]);change(pos[x]);}}
}优秀性质3
本题最强大的地方是在于当他修改时直接暴力重构了整个块十分强大 性质总结
对于分块最强大的操作就是暴力。因为无论怎么暴力只要每次保证不用重构太多块基本都是O(n)O(\sqrt n)O(n)的
然后就算根据每个块的信息找一遍也依据是O(n)O(\sqrt n)O(n)的
而且n2n\sqrt n^2nn2n所以我们可以猥琐欲为的将数据当做可以n2n^2n2的来看 分块-终章
“局部暴力大段维护”。当然分块十分简单性质也十分优秀也很好写。
but!but!but!时间复杂度终究是O(nn)O(n\sqrt n)O(nn)的如果出题人让你用O(nlogn)O(n\ log\ n)O(n log n)也没有办法
还是老老实实写别的数据结构对吧 Part2-点分治 概念
首先点分治无论在速度还是处理问题方面都会被树上启发式合并吊打而且我也不知道为什么他会被分进数据结构里但是不重要
点分治在树上进行分治每次将树分治成若干棵不同的子树处理。
实现方法
一般用于处理树上路径长度的问题
这里举LuoguLuoguLuogu的模板P3806P3806P3806
一棵树(无向)mmm个询问求长度为kkk的路径存不存在。
对于以ppp为根的子树
然后考虑路径种类其实只有两种
经过根节点包含在某一棵子树中
对于1我们将路径分成两半.
求出根节点里每个点的距离did_idi和每个节点位于那个子树bib_ibi
要求满足bx≠byb_x\neq b_ybxby和dxdykd_xd_ykdxdyk
这时候定义函数Calc(p)Calc(p)Calc(p)表示以ppp为根的子树上上述路径的条数
而路径二就直接分治让子树再处理一遍就好了。
现在是考虑Calc(p)Calc(p)Calc(p)如何定义的问题。
因为数据很小用lonxlon_xlonx表示是否存在长度为xxx的路径
然后我们对于每颗子树先用之前的lonlonlon计算一下询问
之后在将这棵子树加入lonlonlon数组
然后在子树之中继续处理
时间复杂度:O(TNlogN)O(TN\ log \ N)O(TN log N)TTT为树的层数
可是如果树是一条链那么时间就会退化为O(N2logN)O(N^2\ log\ N)O(N2 log N)
但是如果我们每次以子树的重心作为新分治的根那么最多只会有logNlog\ Nlog N层。
时间就可以稳在O(Nlog2N)O(N\ log^2\ N)O(N log2 N) Part 3:Treap
概念
TreapTreapTreap就是平衡树的一种所谓平衡树就是要求稳定在lognlog\ nlog n层左右的BSTBSTBST为什么要稳定层数我们等会再讲。
实现方法
将TreapTreapTreap的实现方法之前要先将BSTBSTBST
BSTBSTBST
所谓BST就是二叉查找树。
二叉查找树有个优秀的性质那就是对于每个节点左子节点的权值比它小右子节点比它大。
这样我们就可以愉快的干很多事比如查找前驱后继排名啊
明人不说暗话先来将实现方法
开始先构建两个节点−inf-inf−inf和infinfinf以任意一个为根 int New(int new_val){val[tot]new_val;dat[tot]rand();cnt[tot]size[tot]1;return tot;}void Build(){New(-INF);New(INF);root1;r[1]2;Updata(root);}1[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I4PJVqvd-1576912899795)(https://i.loli.net/2019/01/20/5c446542aac73.png)]
插入andandand删除:
插入一个数时先从根开始。对于走到的每一个点如果比它小就往左不然就往右走。知道找到一个空余的位置就插入。 void Insert(int p,int num){if(p0){pNew(num);return;}//如果有空位了if(numval[p]){cnt[p];Updata(p);return;}//已经有这个数了if(numval[p]){Insert(l[p],num);}//小于往左else{Insert(r[p],num);}//大于往右Updata(p);//更新数据}删除也是根据那个走法找到位置然后删除
删除时注意将子节点接上去
void Remove(int val){int proot;while(p){if(vala[p].val) break;pvala[p].val?a[p].l:a[p].r;}if(p0) return;if(a[p].l0){pa[p].r}//没左接右else if(a[p].r0){pa[p].l;}//没右接左else{//求个后继int nexta[p].r;while(a[next].l0) nexta[next].l;//next没有左子树直接删除Romove(a[next].val);//令节点next代替节点p的位置a[next].la[p].r;a[next].ra[p].r;pnext;}
}求前驱/后继
valvalval后继就是比valvalval大的最小的数。
对于求后继我们可以用一步一步往下走的方法并在路上更新答案ansansans直到走到valvalval的位置或结束时。
这时有3种结果
没有valvalval这个节点。那就直接取ansansans有valvalval但没有右子树。也是直接取ansansans找到valvalval且也有右子树。走到右边然后一直往左走就是valvalval的后继
前驱同理 int GetPre(int num){int ans1;int proot;while(p){if(numval[p]){//找到val节点if(l[p]0){pl[p];//往左一步while(r[p]0) pr[p];//一直往右ansp;//统计}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];//走}return val[ans];}int GetNext(int num){int ans2;int proot;while(p){if(numval[p]){if(r[p]0){pr[p];while(l[p]0) pl[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}查询一个数的排名/一个排名的数
一个数的排名就直接走到那个点顺路根据树的大小统计前面有多少个点就好了。
一个排名的数就根据子树大小来走就ok了。 int GetRankByVal(int p,int num){if(p0) return 0;if(numval[p]) return size[l[p]]1;if(numval[p]) return GetRankByVal(l[p],num);return GetRankByVal(r[p],num)size[l[p]]cnt[p];}int GetValByRank(int p,int rank){if (p0) return INF;if(size[l[p]]rank) return GetValByRank(l[p],rank);if(size[l[p]]cnt[p]rank) return val[p];return GetValByRank(r[p],rank-size[l[p]]-cnt[p]);}这就是BSTBSTBST的全部了。我们来考虑它的弊端。
每次时间就会为O(T)O(T)O(T)
如果我以单调的插入数那么每次就会退化为O(N)O(N)O(N)
那么我们就要让这个BSTBSTBST平衡 TreapTreapTreap
TreapTreapTreap是其中一种让BSTBSTBST保持在lognlog\ nlog n层左右的一个数据结构
具体实现方法就是通过旋转对于一个东西 可以旋转为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dTwPYOyz-1576912899796)(https://i.loli.net/2019/01/20/5c446ed9d8f17.png)]
总之就是分为左旋和右旋 void zig(int p){int ql[p];l[p]r[q];r[q]p;pq;Updata(r[p]);Updata(p);}void zag(int p){int qr[p];r[p]l[q];l[q]p;pq;Updata(l[p]);Updata(p);}只会我们对每个点我们定义一个特征值。然后我们通过旋转让特征值满足二叉堆的性质。
只要让特征值时随机的基本都可以维持在lognlog\ nlog n层附近。
好了放codecodecode
#includecstdio
#includealgorithm
#define INF 2147483647/3
#define N 100010
using namespace std;
int n,root;
struct Treap_node{int l[N],r[N];int val[N],dat[N];int cnt[N],size[N];int tot;int New(int new_val){val[tot]new_val;dat[tot]rand();cnt[tot]size[tot]1;return tot;}void Updata(int p){size[p]size[l[p]]size[r[p]]cnt[p];}void Build(){New(-INF);New(INF);root1;r[1]2;Updata(root);}int GetRankByVal(int p,int num){if(p0) return 0;if(numval[p]) return size[l[p]]1;if(numval[p]) return GetRankByVal(l[p],num);return GetRankByVal(r[p],num)size[l[p]]cnt[p];}int GetValByRank(int p,int rank){if (p0) return INF;if(size[l[p]]rank) return GetValByRank(l[p],rank);if(size[l[p]]cnt[p]rank) return val[p];return GetValByRank(r[p],rank-size[l[p]]-cnt[p]);}void zig(int p){int ql[p];l[p]r[q];r[q]p;pq;Updata(r[p]);Updata(p);}void zag(int p){int qr[p];r[p]l[q];l[q]p;pq;Updata(l[p]);Updata(p);}void Insert(int p,int num){if(p0){pNew(num);return;}if(numval[p]){cnt[p];Updata(p);return;}if(numval[p]){Insert(l[p],num);if(dat[p]dat[l[p]]) zig(p);}else{Insert(r[p],num);if(dat[p]dat[r[p]]) zag(p);}Updata(p);}int GetPre(int num){int ans1;int proot;while(p){if(numval[p]){if(l[p]0){pl[p];while(r[p]0) pr[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}int GetNext(int num){int ans2;int proot;while(p){if(numval[p]){if(r[p]0){pr[p];while(l[p]0) pl[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}void Remove(int p,int num){if(p0) return;if(numval[p]){if(cnt[p]1){cnt[p]--;Updata(p);return;}if(l[p]||r[p]){if(r[p]0||dat[l[p]]dat[r[p]])zig(p),Remove(r[p],num);elsezag(p),Remove(l[p],num);Updata(p);}else p0;return;}numval[p]?Remove(l[p],num):Remove(r[p],num);Updata(p);}
}a;
int main()
{a.Build();scanf(%d,n);while(n--){int opt,x;scanf(%d%d,opt,x);switch(opt){case 1:a.Insert(root,x);break;case 2:a.Remove(root,x);break;case 3:printf(%d\n,a.GetRankByVal(root,x)-1);break;case 4:printf(%d\n,a.GetValByRank(root,x1));break;case 5:printf(%d\n,a.GetPre(x));break;case 6:printf(%d\n,a.GetNext(x));break;}}
}虽然基本都可以用setsetset搞定但是还是可以做很多NBNBNB的好东西的。 Part4:树链剖分
概念
将树分割成若干条链来处理将树上的问题转换为线性问题
实现方法
实现概念
学树链剖分之前我们先来getgetget一些前置知识
重儿子:子树最大的一个儿子
轻儿子:其他儿子
重边:连接重儿子的边
轻边:其他边
重路径:重边的路径
还有一个重要性质:从根到任何一个点的轻边数不超过lognlog\ nlog n条 证明: 若走到一条轻边那么子树大小至少缩小一半那么最多走logn\log nlogn条轻边子树大小就会缩小为1 证毕
所以我们对于一条路径的轻边数量也是logloglog级的。
所以我们可以对于重路径将树进行划分。
我们来看例题:
要求支持子树修改子树求和路径修改路径求和。
对于子树操作很简单我们按照dfsdfsdfs序加入线段树然后线段树区间修改就可以做到子树修改可以路径问题如何解决?
这时候我们就可以用树链剖分了。我们考虑将dfsdfsdfs修改一下。
我们可以每次优先走重儿子那么重路径在线段树上的位置就是连续的对于一段重路径我们就可以进行区间修改了而轻边有不会太多所以一次操作时间复杂度是O(log2n)O(log^2\ n)O(log2 n)的
代码实现
我们先跑两次dfsdfsdfs预处理
第一遍:
sonx:xson_x:xsonx:x的重儿子
depx:xdep_x:xdepx:x的深度
sizx:xsiz_x:xsizx:x的子树大小
fx:xf_x:xfx:x的父节点
第二遍:
segx:xseg_x:xsegx:x在线段树上的位置
idz:id_z:idz:线段树zzz位置上的节点
topx:xtop_x:xtopx:x所在重路径最浅的节点
之后我们就预处理完了。
之后我们对于路径操作可以向倍增求LCALCALCA一样将一条路径拆分为两条路径不过变为每次跳到topxtop_xtopx然后跳的过程重进行用线段树进行区间修改。
上
codecodecode
#includecstdio
#includealgorithm
using namespace std;
const int N200000;
int tot,cnt,n,m,s,p,ls[N],pw[N],id[N];
int siz[N],dep[N],f[N],son[N],seg[N],top[N];
struct treenode{int l,r,lazy,val;
};
struct LineTree{treenode t[N*2];void build(int x,int l,int r){t[x].ll;t[x].rr;if(lr){t[x].valpw[id[l]]%p;return;}int mid(lr)1;build(x*2,l,mid);build(x*21,mid1,r);t[x].val(t[x*2].valt[x*21].val)%p;}void downdata(int x){if(t[x].lazy){(t[x*2].lazyt[x].lazy)%p;(t[x*2].valt[x].lazy*(t[x*2].r-t[x*2].l1))%p;(t[x*21].lazyt[x].lazy)%p;(t[x*21].valt[x].lazy*(t[x*21].r-t[x*21].l1))%p;t[x].lazy0;}}void change(int x,int l,int r,int num){if(t[x].llt[x].rr){(t[x].valnum*(t[x].r-t[x].l1))%p;(t[x].lazynum)%p;return;}downdata(x);int mid(t[x].lt[x].r)1;if(rmid) change(x*2,l,r,num);else if(lmid) change(x*21,l,r,num);else change(x*2,l,mid,num),change(x*21,mid1,r,num);t[x].val(t[x*2].valt[x*21].val)%p;}int find(int x,int l,int r){if(t[x].llt[x].rr)return t[x].val;downdata(x);int mid(t[x].lt[x].r)1;if(rmid) return find(x*2,l,r);else if(lmid) return find(x*21,l,r);else return (find(x*2,l,mid)find(x*21,mid1,r))%p; }
}LT;//线段树
struct edge_node{int to,next;
}a[N*2];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs1(int x,int fa)//第一遍预处理
{siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dep[y]dep[x]1;f[y]x;dfs1(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}
}
void dfs2(int x,int fa)//第二遍预处理
{seg[x]cnt;id[cnt]x;if(son[x]){top[son[x]]top[x];dfs2(son[x],x);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x]) continue;top[y]y;dfs2(y,x);}
}
void path_change(int x,int y,int z)//路径修改
{while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);//哪个深度大跳哪个LT.change(1,seg[top[x]],seg[x],z);//路径修改xf[top[x]];//跳}if(dep[x]dep[y]) swap(x,y);LT.change(1,seg[x],seg[y],z);return;
}
int path_ask(int x,int y)//路径查询—同上
{int ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);(ansLT.find(1,seg[top[x]],seg[x]))%p;xf[top[x]];}if(dep[x]dep[y]) swap(x,y);(ansLT.find(1,seg[x],seg[y]))%p;return ans;
}
int main()
{scanf(%d%d%d%d,n,m,s,p);for(int i1;in;i)scanf(%d,pw[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs1(s,0);top[s]s;dfs2(s,0);LT.build(1,1,n);for(int i1;im;i){int t,x,y,z;scanf(%d%d,t,x);if(t1){scanf(%d%d,y,z);path_change(x,y,z);}if(t2){scanf(%d,y);printf(%d\n,path_ask(x,y));}if(t3){scanf(%d,z);LT.change(1,seg[x],seg[x]siz[x]-1,z);}if(t4){printf(%d\n,LT.find(1,seg[x],seg[x]siz[x]-1));}}
} Part 5:练习题
luogu3870−[TJOI2009]luogu3870-[TJOI2009]luogu3870−[TJOI2009]开关【分块】
luogu4008−[NOI2003]luogu4008-[NOI2003]luogu4008−[NOI2003]文本编辑器【分块】
luogu2634−[luogu2634-[luogu2634−[国家集训队]]]聪聪可可【点分治】
luogu4178−Treeluogu4178-Treeluogu4178−Tree【点分治】
luogu3714−[BJOI2017]luogu3714-[BJOI2017]luogu3714−[BJOI2017]树的难题【点分治】
luogu3345−[ZJOI2015]luogu3345-[ZJOI2015]luogu3345−[ZJOI2015]幻想乡战略游戏【点分治】
luogu1503−luogu1503-luogu1503−鬼子进村【TreapTreapTreap】
luogu1533−luogu1533-luogu1533−可怜的狗狗【TreapTreapTreap】
luogu3313−[SDOI2014]luogu3313-[SDOI2014]luogu3313−[SDOI2014]旅行【主席树,,,树链剖分】
luogu2486−[SDOI2011]luogu2486-[SDOI2011]luogu2486−[SDOI2011]染色【树链剖分】
luogu2146−[NOI2015]luogu2146-[NOI2015]luogu2146−[NOI2015]软件包管理器【树链剖分】
