bzoj3626 [ LNOI2014 ] -- 树链剖分
2018-06-17 22:36:05来源:未知 阅读 ()
直接复制gconeice的题解吧
显然,暴力求解的复杂度是无法承受的。
考虑这样的一种暴力,我们把 z 到根上的点全部打标记,对于 l 到 r 之间的点,向上搜索到第一个有标记的点求出它的深度统计答案。观察到,深度其实就是上面有几个已标记了的点(包括自身)。所以,我们不妨把 z 到根的路径上的点全部 +1,对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现,实际上这个操作具有叠加性,且可逆。也就是说我们可以对于 l 到 r 之间的点 i,将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点(包括自身)的权值和就是这个询问的答案。把询问差分下,也就是用 [1, r] ? [1, l ? 1] 来计算答案,那么现在我们就有一个明显的解法。从 0 到 n ? 1 依次插入点 i,即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和,显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n),LCT的复杂度为 O((n + q)· log n),均可以完成任务。至此,题目已经被我们完美解决。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 #define N 50010 8 #define M 201314 9 #define ll long long 10 vector<int>g[N]; 11 struct Node{ 12 int f,z,d; 13 Node(){} 14 Node(int f,int z,int d):f(f),z(z),d(d){} 15 }; 16 vector<Node>G[N]; 17 int i,j,k,n,m,Top[N],Num,s[N],Son[N],w[N],c[N<<2],x,y,z,Ans[N],p[N<<2],f[N]; 18 inline void Dfs1(int x){ 19 s[x]=1; 20 for(int i=0;i<g[x].size();i++){ 21 Dfs1(g[x][i]); 22 s[x]+=s[g[x][i]]; 23 if(s[g[x][i]]>s[Son[x]])Son[x]=g[x][i]; 24 } 25 } 26 inline void Dfs2(int x,int Tmp){ 27 Top[x]=Tmp;w[x]=++Num; 28 if(Son[x])Dfs2(Son[x],Tmp); 29 for(int i=0;i<g[x].size();i++) 30 if(g[x][i]!=Son[x])Dfs2(g[x][i],g[x][i]); 31 } 32 inline void Down(int x,int y){ 33 p[x<<1]+=p[x];p[x<<1|1]+=p[x]; 34 c[x<<1]+=p[x]*(y+1>>1);c[x<<1|1]+=p[x]*(y>>1); 35 p[x]=0; 36 } 37 inline void Up(int x){c[x]=c[x<<1]+c[x<<1|1];} 38 inline void Update(int Node,int l,int r,int L,int R){ 39 if(l>R||r<L)return; 40 if(l>=L&&r<=R){ 41 c[Node]+=r-l+1; 42 p[Node]++; 43 return; 44 } 45 if(p[Node])Down(Node,r-l+1); 46 int Mid=l+r>>1; 47 Update(Node<<1,l,Mid,L,R); 48 Update(Node<<1|1,Mid+1,r,L,R); 49 Up(Node); 50 } 51 inline int Query(int Node,int l,int r,int L,int R){ 52 if(l>R||r<L)return 0; 53 if(l>=L&&r<=R)return c[Node]; 54 if(p[Node])Down(Node,r-l+1); 55 int Mid=l+r>>1; 56 return (Query(Node<<1,l,Mid,L,R)+Query(Node<<1|1,Mid+1,r,L,R))%M; 57 } 58 inline void Update_tree(int x){ 59 while(x){ 60 Update(1,1,n,w[Top[x]],w[x]); 61 x=f[Top[x]]; 62 } 63 } 64 inline int Query_tree(int x){ 65 int Ans=0; 66 while(x){ 67 Ans=(Ans+Query(1,1,n,w[Top[x]],w[x]))%M; 68 x=f[Top[x]]; 69 } 70 return Ans; 71 } 72 int main(){ 73 scanf("%d%d",&n,&m); 74 for(i=2;i<=n;i++)scanf("%d",&f[i]),g[++f[i]].push_back(i); 75 Dfs1(1);Dfs2(1,1); 76 for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),G[x].push_back(Node(i,++z,-1)),G[y+1].push_back(Node(i,z,1)); 77 for(i=1;i<=n;i++){ 78 Update_tree(i); 79 for(j=0;j<G[i].size();j++){ 80 Ans[G[i][j].f]+=Query_tree(G[i][j].z)*G[i][j].d; 81 } 82 } 83 for(i=1;i<=m;i++)printf("%d\n",(Ans[i]+M)%M); 84 return 0; 85 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P2142 高精度减法
下一篇:P1603 斯诺登的密码
- BZOJ3083: 遥远的国度(树链剖分) 2018-07-25
- BZOJ4196: [Noi2015]软件包管理器(树链剖分 线段树) 2018-07-09
- bzoj1146整体二分+树链剖分+树状数组 2018-06-17
- bzoj4712 -- 树链剖分 2018-06-17
- bzoj2588 -- 树链剖分+主席树 2018-06-17
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