当前位置: 首页 > news >正文

江苏网站制作企业百度seo排名优化如何

江苏网站制作企业,百度seo排名优化如何,google网站怎么做流量,网站推广信息怎么做(零基础者出门左拐) 最近又双叒学了主席树,打了几道模板题。感觉还行 主席树,在我看来就是线段树的可持化 (一开始以为主席树只是可持久化权值线段树)。在题目中需要建多颗线段树或权值线段树且相邻的线段树…

(零基础者出门左拐)
最近又双叒学了主席树,打了几道模板题。
感觉还行
主席树,在我看来就是线段树的可持化 (一开始以为主席树只是可持久化权值线段树)。在题目中需要建多颗线段树或权值线段树且相邻的线段树差别不大(一般就一个点不一样)时就可以用主席树。运用可持久化的思想,我们并不需要重新构建一颗线段树,因为只需要改一个点,所以线段树只需要新多出\(logn\)个节点,其他的节点继承前面的线段树就行了(所以一般都要开始建一颗空树)。这样一来,我们建树的时间复杂度和、这一堆线段树的空间复杂度变成了\(nlogn\),真是佩服人类的智慧。

【模板】可持久化线段树 1(主席树)

嗯,模板题,求区间第k大,我们找到对应的两颗线段树\(root[r]\)\(root[l-1]\)然后在这两颗线段数上同时二分就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e5+100;
int num,n,m,a[N],b[N],tot,root[N],w[N*20],ch[N*20][2];
void build(int l,int r,int &now){now=++num;if(l==r)return;int mid=(l+r)>>1;build(l,mid,ch[now][0]);build(mid+1,r,ch[now][1]);
}
void ins(int l,int r,int x,int pre,int &now){now=++num;w[now]=w[pre]+1;if(l==r)return;ch[now][0]=ch[pre][0];ch[now][1]=ch[pre][1];int mid=(l+r)>>1;if(x>mid)ins(mid+1,r,x,ch[pre][1],ch[now][1]);else ins(l,mid,x,ch[pre][0],ch[now][0]);
}
int check(int l,int r,int k,int pre,int now){if(l==r)return l;int tmp=w[ch[now][0]]-w[ch[pre][0]];int mid=(l+r)>>1;if(tmp>=k)return check(l,mid,k,ch[pre][0],ch[now][0]);else return check(mid+1,r,k-tmp,ch[pre][1],ch[now][1]);
}
int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;
}
int main(){n=read();m=read();for(int i=1;i<=n;i++)a[i]=read(),b[++tot]=a[i];sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;build(1,tot,root[0]);for(int i=1;i<=n;i++)ins(1,tot,a[i],root[i-1],root[i]);while(m--){int l=read(),r=read(),k=read();printf("%d\n",b[check(1,tot,k,root[l-1],root[r])]);}return 0;
}

非常短以下的主席树不加说明就是模板的这种主席树。


[SDOI2010]粟粟的书架

天啊,这题强行二合一。
就说说\(n=1\)的情况。一开始想的是树状数组套平衡树,或套权值线段树的。\(m=500000\)。。。再见。
考虑用主席树,我们在主席树上维护两个东西\(sum[i]\)代表权值和,\(num[i]\)代表数量和。然后在主席树上二分,先考虑右子树,如果\(sum[ch[now][1]]-sum[ch[pre][1]]<k,k\)就减去\(sum[ch[now][1]]-sum[ch[pre][1]]\)然后答案加上\(num[ch[now][1]]-num[ch[pre][1]]\),然后递归左子树,否则递归右子树。最后\(l=r\)时答案再加上当前\(xl>=k\)的最小正整数解。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=205;
const int MAXN=1050;
const int NN=500100;
int n,m,q,w[N][N][MAXN],num[N][N][MAXN],root[NN],sum[NN*41],Num[NN*41],cnt,ch[NN*41][2];
inline int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;
}
int getw(int x1,int y1,int x2,int y2,int k){return w[x2][y2][k]-w[x2][y1-1][k]-w[x1-1][y2][k]+w[x1-1][y1-1][k];
}
int getnum(int x1,int y1,int x2,int y2,int k){return num[x2][y2][k]-num[x2][y1-1][k]-num[x1-1][y2][k]+num[x1-1][y1-1][k];
}
void work1(){int a[N][N];int mx=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read(),mx=max(mx,a[i][j]);for(int k=1;k<=mx+1;k++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){w[i][j][k]=w[i-1][j][k]+w[i][j-1][k]-w[i-1][j-1][k]+(a[i][j]>=k?a[i][j]:0);num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+(a[i][j]>=k?1:0);}while(q--){int x=read(),y=read(),xx=read(),yy=read(),h=read();if(getw(x,y,xx,yy,1)<h){printf("Poor QLW\n");continue;}int l=1,r=mx;int ans=mx+1;;while(l<=r){int mid=(l+r)>>1;if(getw(x,y,xx,yy,mid)<h){ans=mid;r=mid-1;}else l=mid+1;}printf("%d\n",getnum(x,y,xx,yy,ans)+(h-getw(x,y,xx,yy,ans)-1)/(ans-1)+1);}
} 
void build(int l,int r,int &now){now=++cnt;if(l==r)return;int mid=(l+r)>>1;build(l,mid,ch[now][0]);build(mid+1,r,ch[now][1]);
}
void add(int l,int r,int x,int pre,int &now){now=++cnt;Num[now]=Num[pre]+1;sum[now]=sum[pre]+x;if(l==r)return;ch[now][1]=ch[pre][1];ch[now][0]=ch[pre][0];int mid=(l+r)>>1;if(x>mid)add(mid+1,r,x,ch[pre][1],ch[now][1]);else add(l,mid,x,ch[pre][0],ch[now][0]);
}
int check(int l,int r,int A,int B,int k){int ans=0;while(l<r){int mid=l+r>>1;int lch=sum[ch[B][1]]-sum[ch[A][1]];if(lch<k) ans+=Num[ch[B][1]]-Num[ch[A][1]],k-=lch,r=mid,B=ch[B][0],A=ch[A][0];else l=mid+1,B=ch[B][1],A=ch[A][1];}ans+=(k+l-1)/l;return ans;
}
void work2(){int a[NN];for(int i=1;i<=m;i++)a[i]=read();build(1,1000,root[0]); for(int i=1;i<=m;i++)add(1,1000,a[i],root[i-1],root[i]);while(q--){int x=read(),y=read(),xx=read(),yy=read(),h=read();if(sum[root[yy]]-sum[root[y-1]]<h){printf("Poor QLW\n");continue;}printf("%d\n",check(1,1000,root[y-1],root[yy],h));}
}
int main(){n=read();m=read();q=read();if(n!=1)work1();else work2();return 0;
}

[SDOI2013]森林

询问一个森林中两点间路径经过点的第k小,动态连边。保证是一个森林。强制在线。

首先我们可以在树上建主席树,每一个点建一颗权值线段树,继承他父亲线段树的信息。
然后处理询问时,我们可以用\(sum[x]+sum[y]-sum[lca]-sum[fa[lca]]\)来表示\(x,y\)路径上的权值线段树。然后我们在这4个权值线段树树上二分就行了。
然后我们如何处理,动态连边呢。我们用启发式合并的思想,把小的树接在大的树上面,然后在小树里\(dfs\)重构就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=101000;
int cnt,head[N],f[N],fa[N][23],dep[N],root[N],a[N],size[N],b[N],tot;
int sum[N*600],ch[N*600][2],num,n,m,q,ans;
struct edge{int to,nxt;
}e[N*2];
void add_edge(int u,int v){cnt++;e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;cnt++;e[cnt].nxt=head[v];e[cnt].to=u;head[v]=cnt;
}
int find(int x){if(f[x]==x)return x;else return f[x]=find(f[x]);
}
void merge(int x,int y){int fx=find(x),fy=find(y);f[fy]=fx;size[fx]+=size[fy];
}
int getlca(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}
void build(int l,int r,int &now){now=++num;if(l==r)return;int mid=(l+r)>>1;build(l,mid,ch[now][0]);build(mid+1,r,ch[now][1]);
}
void add(int l,int r,int x,int pre,int &now){now=++num;sum[now]=sum[pre]+1;if(l==r)return;ch[now][0]=ch[pre][0];ch[now][1]=ch[pre][1];int mid=(l+r)>>1;if(x>mid)add(mid+1,r,x,ch[pre][1],ch[now][1]);else add(l,mid,x,ch[pre][0],ch[now][0]);
}
void dfs(int u,int f){fa[u][0]=f;for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];dep[u]=dep[f]+1;add(1,tot,a[u],root[f],root[u]);for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(v==f)continue;dfs(v,u);}
}
int check(int x,int y,int lca,int flca,int l,int r,int k){while(l<r){int mid=(l+r)>>1;int tmp=sum[ch[x][0]]+sum[ch[y][0]]-sum[ch[lca][0]]-sum[ch[flca][0]];if(tmp>=k)x=ch[x][0],y=ch[y][0],lca=ch[lca][0],flca=ch[flca][0],r=mid;else k-=tmp,x=ch[x][1],y=ch[y][1],lca=ch[lca][1],flca=ch[flca][1],l=mid+1;}return b[l];
}
int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;
}
int main(){int hhh=read();n=read(),m=read(),q=read();for(int i=1;i<=n;i++)f[i]=i,size[i]=1,a[i]=read(),b[i]=a[i];sort(b+1,b+1+n);tot=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;build(1,tot,root[0]);for(int i=1;i<=m;i++){int u=read(),v=read();add_edge(u,v);merge(u,v);}for(int i=1;i<=n;i++)if(f[i]==i)dfs(i,0);char s[3];while(q--){scanf("%s",s);if(s[0]=='Q'){int x=read(),y=read(),k=read();x^=ans;y^=ans;k^=ans;int lca=getlca(x,y);ans=check(root[x],root[y],root[lca],root[fa[lca][0]],1,tot,k);printf("%d\n",ans);}else{int x=read()^ans,y=read()^ans;if(size[x]>size[y])swap(x,y);add_edge(x,y);merge(x,y);dfs(y,x);}}return 0;
}

[CQOI2015]任务查询系统

一开始受到HNOI2015摘果子的启发写了一发树套树,然后就T了

这题要求求覆盖一个点的前k小区间和。强制在线。

但主席树的解法其实差不多,因为主席树有前缀和的思想,我们把每一个区间拆开,在\(l\)处加区间的权值,在\(r+1\)处减区间的权值,然后用主席树维护一个前缀和。
我们就可以单点查询了。在主席树上二分就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;
}
int n,m,num,tot;
int a[N],b[N],root[N<<6];
long long ans=1;
struct tree {long long sum; int cnt,l,r;
}t[N<<6];
vector<int>be[N],ed[N];
void update(int &u,int l,int r,int pre,int pos,int v){u=++tot; t[u]=t[pre];t[u].cnt+=v, t[u].sum+=1ll*v*b[pos];if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) update(t[u].l,l,mid,t[pre].l,pos,v);else update(t[u].r,mid+1,r,t[pre].r,pos,v);
}
long long query(int u,int l,int r,int k){int num=t[t[u].l].cnt;if(l==r) return t[u].sum/(1ll*t[u].cnt)*1ll*k;int mid=(l+r)>>1;if(k<=num) return query(t[u].l,l,mid,k);else return query(t[u].r,mid+1,r,k-num)+t[t[u].l].sum;
}
int main(){m=read(),n=read();for(int i=1;i<=m;i++) {int x=read(),y=read();a[i]=read(),b[i]=a[i];be[x].push_back(i), ed[y+1].push_back(i);}sort(b+1,b+1+m); int num=unique(b+1,b+1+m)-b-1;for(int i=1;i<=n;i++) {root[i]=root[i-1];for(int j=0;j<be[i].size();j++) {int p=lower_bound(b+1,b+1+num,a[be[i][j]])-b;update(root[i],1,num,root[i],p,1);}for(int j=0;j<ed[i].size();j++) {int p=lower_bound(b+1,b+1+num,a[ed[i][j]])-b;update(root[i],1,num,root[i],p,-1);}}for(int i=1;i<=n;i++) {int x=read(),a=read(),b=read(),c=read(),k=(1ll*a*ans+b)%c+1;if(k>t[root[x]].cnt) ans=t[root[x]].sum;else ans=query(root[x],1,num,k);printf("%lld\n",ans);}return 0;
}

[国家集训队]middle

二分答案想到了,然后小于的为-1,大于等于的为1,中间一块加上,一个最大前缀,一个最大后缀的套路也知道,然后就不会了。
听说是陈立杰出的题
然后该怎么办?上主席树,我们一个初步的想法是每一个权值,都建一颗1和-1的普通线段树上面维护区间和,区间最大前缀,最大后缀。然后我们发现,相邻两个权值的线段树,很相近,只有一个权值的点不一样,只需要改\(logn\)个节点,然后就是主席树了。那么假如一个权值有很多点该怎么办。只需要一个一个插入,然后以最后一次插入完成后的根作为这个权值的根就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=20100;
vector<int> vec[N];
int n,m,a[N],b[N],ans,root[N],num,q[6];
int sum[N*20],ml[N*20],mr[N*20],tot,ch[N*20][2];
int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;
}
void update(int now){sum[now]=sum[ch[now][0]]+sum[ch[now][1]];ml[now]=max(ml[ch[now][0]]+sum[ch[now][1]],ml[ch[now][1]]);mr[now]=max(mr[ch[now][1]]+sum[ch[now][0]],mr[ch[now][0]]);
}
void build(int l,int r,int &now){if(now==0)now=++tot;if(l==r){sum[now]=ml[now]=mr[now]=1;return ;}int mid=(l+r)>>1;build(l,mid,ch[now][0]);build(mid+1,r,ch[now][1]);update(now);
}
void add(int l,int r,int x,int pre,int &now){now=++tot;if(l==r){sum[now]=ml[now]=mr[now]=-1;return;}ch[now][0]=ch[pre][0];ch[now][1]=ch[pre][1];int mid=(l+r)>>1;if(x>mid)add(mid+1,r,x,ch[pre][1],ch[now][1]);else add(l,mid,x,ch[pre][0],ch[now][0]);update(now);
}
int check(int l,int r,int L,int R,int now){if(L>R)return 0;if(l==L&&r==R){return sum[now];}int mid=(l+r)>>1;if(L>mid)return check(mid+1,r,L,R,ch[now][1]);else if(R<=mid)return check(l,mid,L,R,ch[now][0]);else return check(l,mid,L,mid,ch[now][0])+check(mid+1,r,mid+1,R,ch[now][1]); 
}
int check_L(int l,int r,int L,int R,int now){if(l==L&&r==R)return ml[now];int mid=(l+r)>>1;if(L>mid)return check_L(mid+1,r,L,R,ch[now][1]);else if(R<=mid)return check_L(l,mid,L,R,ch[now][0]);else{int tmp1=check_L(mid+1,r,mid+1,R,ch[now][1]);int tmp2=check(mid+1,r,mid+1,R,ch[now][1])+check_L(l,mid,L,mid,ch[now][0]);return max(tmp1,tmp2);}
}
int check_R(int l,int r,int L,int R,int now){if(l==L&&r==R)return mr[now];int mid=(l+r)>>1;if(L>mid)return check_R(mid+1,r,L,R,ch[now][1]);else if(R<=mid)return check_R(l,mid,L,R,ch[now][0]);else{int tmp1=check_R(l,mid,L,mid,ch[now][0]);int tmp2=check(l,mid,L,mid,ch[now][0])+check_R(mid+1,r,mid+1,R,ch[now][1]);return max(tmp1,tmp2);}
}
bool judge(int x){int tmp1=check(1,n,q[2]+1,q[3]-1,root[x]);int tmp2=check_L(1,n,q[1],q[2],root[x]);int tmp3=check_R(1,n,q[3],q[4],root[x]);if(tmp1+tmp2+tmp3>=0)return true;else return false; 
}
int work(){int l=1,r=num,tmp;while(l<=r){int mid=(l+r)>>1;if(judge(mid)){tmp=mid;l=mid+1;}else r=mid-1;}return tmp;
}
int main(){n=read();for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];sort(b+1,b+1+n);num=unique(b+1,b+1+n)-b-1;build(1,n,root[0]);for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+num,a[i])-b;vec[a[i]].push_back(i);}for(int i=1;i<=num;i++){root[i]=root[i-1];if(vec[i-1].size())for(int j=0;j<vec[i-1].size();j++)add(1,n,vec[i-1][j],root[i],root[i]);}m=read();while(m--){q[1]=(read()+ans)%n+1,q[2]=(read()+ans)%n+1,q[3]=(read()+ans)%n+1,q[4]=(read()+ans)%n+1;//  q[1]=read(),q[2]=read(),q[3]=read(),q[4]=read();sort(q+1,q+1+4);ans=work();printf("%d\n",b[ans]);ans=b[ans];}return 0;
}

总结一下。主席树一般可以干什么?区间第k大,区间大于x的数的个数(和)。一般都需要在主席树上二分。然后主席树有前缀和的思想。可以很好的应用在树上用差分拼出一个路径。也可以求出差分再用主席树求前缀,支持单点查询,对于包含一个点的区间的信息,我们这一用到这个技巧。然后就是对于建很多颗线段树,但相邻的线段树比较相近时,也可以可持久化。

转载于:https://www.cnblogs.com/Xu-daxia/p/10111996.html

http://www.lbrq.cn/news/2397187.html

相关文章:

  • 直播软件推荐重庆好的seo平台
  • 20个优秀微信小程序seo常见的优化技术
  • 建设通是正规网站吗百度搜索下载
  • 建设一个网站的规划网站在线优化检测
  • 03340 网站建设与管理长沙h5网站建设
  • 做网站用什么配置的vps福州百度快照优化
  • 网上发帖推广seo平台是什么
  • cn体育门户网站源码(asp网络营销课程个人感悟
  • 电子商务网站开发目的和意义产品推广介绍怎么写
  • ps做素材下载网站好消息tvapp电视版
  • 如何做网站权重微信营销推广方案
  • 武汉去施工网今日招工seo千享科技
  • 家居在线设计平台广州网站优化多少钱
  • 深圳做营销网站设计广告商对接平台
  • 开个网站做英语培训百度网站收录
  • 高端大气网站欣赏竞价推广和信息流推广
  • 厦门市网站建设局设计网站
  • 和田知名网站建设企业怎么优化关键词
  • 江阴做网站公司怎么提高百度关键词排名
  • 什么网站做简历模板seo研究中心道一老师
  • 有哪些网站做的比较好看的长春网站seo
  • 服装官网网站建设百度竞价托管哪家好
  • 营销网站建设规划概念提供搜索引擎优化公司
  • wordpress转bitcronseowhy教研室
  • 深圳建站公司的小技巧市场营销案例100例
  • 如何在局域网内做网站网站功能优化
  • web网站开发分享网站武汉百度推广优化
  • 东莞做网站公司有哪些收录批量查询工具
  • 做网站都注意哪些东西百度营销登录入口
  • 微信看视频打赏网站建设头条新闻最新消息
  • Ubuntu20.04 samba配置
  • web前端渡一大师课 02 浏览器渲染原理
  • 用户中心项目实战(springboot+vue快速开发管理系统)
  • 智能体之变:深度解析OpenAI ChatGPT Agent如何重塑人机协作的未来
  • Django3 - Web前端开发基础 HTML、CSS和JavaScript
  • SpringBoot项目部署至云服务器