bzoj2588 -- 树链剖分+主席树
2018-06-17 22:40:57来源:未知 阅读 ()
先将权值离散。
显然可以对于每个结点建一棵权值线段树存这个点到根结点的路径上的点权,询问时在线段树上二分,但这样时间是O(n2log2n)的。
然后想到用主席树优化,时间复杂度O(n*log2n)。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 #define ll long long 8 inline char nc(){ 9 static char buf[100000],*p1=buf,*p2=buf; 10 if(p1==p2){ 11 p2=(p1=buf)+fread(buf,1,100000,stdin); 12 if(p1==p2)return EOF; 13 } 14 return *p1++; 15 } 16 inline void Read(int& x){ 17 char c=nc(),b=1; 18 for(;c<'0'||c>'9';c=nc())if(c=='-')b=-1; 19 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());x*=b; 20 } 21 char S[30]; 22 int Len; 23 inline void Print(int x){ 24 for(Len=0;x;x/=10)S[++Len]=x%10; 25 while(Len)putchar(S[Len--]+48); 26 } 27 #define N 100010 28 vector<int>g[N]; 29 struct Ls{ 30 int w,f; 31 }l[N]; 32 struct Node{ 33 int l,r,s; 34 }c[N*80]; 35 int Ans,i,j,k,n,m,x,y,a[N],Top[N],Rt[N],f[N],d[N],s[N],Son[N],w[N],Num,Cnt,L; 36 inline void Dfs1(int x,int F){ 37 f[x]=F;d[x]=d[F]+1;s[x]=1; 38 for(int i=0;i<g[x].size();i++) 39 if(g[x][i]!=F){ 40 Dfs1(g[x][i],x); 41 if(s[g[x][i]]>s[Son[x]])Son[x]=g[x][i]; 42 s[x]+=s[g[x][i]]; 43 } 44 } 45 inline void Insert(int Last,int& x,int l,int r,int y){ 46 c[++Cnt]=c[Last]; 47 x=Cnt;c[x].s++; 48 if(l==r)return; 49 int Mid=l+r>>1; 50 if(Mid>=y)Insert(c[Last].l,c[x].l,l,Mid,y);else Insert(c[Last].r,c[x].r,Mid+1,r,y); 51 } 52 inline void Dfs2(int x,int Tmp){ 53 Top[x]=Tmp;Insert(Rt[f[x]],Rt[x],1,Num,a[x]); 54 if(Son[x])Dfs2(Son[x],Tmp); 55 for(int i=0;i<g[x].size();i++) 56 if(g[x][i]!=f[x]&&g[x][i]!=Son[x])Dfs2(g[x][i],g[x][i]); 57 } 58 inline bool Cmp(Ls a,Ls b){return a.w<b.w;} 59 inline int Lca(int x,int y){ 60 while(Top[x]!=Top[y]) 61 if(d[Top[x]]>d[Top[y]])x=f[Top[x]];else y=f[Top[y]]; 62 return d[x]>d[y]?y:x; 63 } 64 inline int Query(int x,int y,int z,int p,int l,int r,int k){ 65 if(l==r)return l; 66 int Mid=l+r>>1; 67 int S=k-c[c[x].l].s-c[c[y].l].s+c[c[z].l].s+c[c[p].l].s; 68 if(S<=0)return Query(c[x].l,c[y].l,c[z].l,c[p].l,l,Mid,k); 69 return Query(c[x].r,c[y].r,c[z].r,c[p].r,Mid+1,r,S); 70 } 71 int main(){ 72 Read(n);Read(m); 73 for(i=1;i<=n;i++)Read(l[i].w),l[i].f=i; 74 sort(l+1,l+n+1,Cmp); 75 a[l[1].f]=Num=1;w[1]=l[1].w; 76 for(i=2;i<=n;i++) 77 if(l[i].w==l[i-1].w)a[l[i].f]=Num;else a[l[i].f]=++Num,w[Num]=l[i].w; 78 for(i=1;i<n;i++)Read(x),Read(y),g[x].push_back(y),g[y].push_back(x); 79 Dfs1(1,0);Dfs2(1,1); 80 while(m--){ 81 Read(x);Read(y);Read(k); 82 x^=Ans; 83 L=Lca(x,y); 84 Ans=w[Query(Rt[x],Rt[y],Rt[L],Rt[f[L]],1,Num,k)]; 85 Print(Ans); 86 if(m)putchar('\n'); 87 } 88 return 0; 89 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:2924 数独挑战
下一篇:网络编程:connect函数
- 树状结构之主席树 2019-01-03
- 洛谷P4197 Peaks(Kruskal重构树 主席树) 2018-09-18
- BZOJ4299: Codechef FRBSUM(主席树) 2018-09-18
- 洛谷P2468 [SDOI2010]粟粟的书架(二分答案 前缀和 主席树) 2018-09-18
- 牛客NOIP提高组R1 C保护(主席树) 2018-09-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash