链接

　　http://www.lydsy.com/JudgeOnline/problem.php?id=3626

填坑

　　今日七道题(3/7)。

题解

　　没有取模导致WA系列。
　　又是一道神题，什么时候能自己想出这种神题啊..
　　离线做，询问[l,r]看做询问[1,r]-[1,l-1]。
　　那问题就是怎么求询问[1,r]，问题变成了：1到r这些节点里，到z的lca深度之和？
　　可以把根到z上的每个点的点权设为1，其余0，然后把[1,r]里每个点到根路径上的权值和加起来就是答案。显然需要转化一下，现在从1到r一次加入每个点，查询z到根路径上的权值和，是不是一样？
　　是的。
　　所以LCT。

代码

//LCT
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 100000
#define mod 201314
using namespace std;
int N, ans[maxn], z[maxn], Q;
vector<int> l[maxn], r[maxn];
struct node
{
int rev, sum, add, size, w;
node *f, *ch[2];
}nd[maxn], *s[maxn];
inline int getwh(node *x)
{if(!x->f)return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;}
inline bool isroot(node *x){return getwh(x)==-1;}
inline void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;}
inline void rev(node *x){if(x)x->rev^=1;}
inline void add(node *x, int d){if(x)x->add+=d;}
inline void pushdown(node *x)
{
if(!x)return;
if(x->rev)
{
swap(x->ch[0],x->ch[1]);
rev(x->ch[0]),rev(x->ch[1]);
x->rev=0;
}
if(x->add)
{
x->sum+=x->size*x->add;
x->w+=x->add;
add(x->ch[0],x->add),add(x->ch[1],x->add);
x->add=0;
}
}
inline void pushup(node *x)
{
pushdown(x->ch[0]),pushdown(x->ch[1]);
x->size=1;x->sum=x->w;
if(x->ch[0])x->size+=x->ch[0]->size,x->sum+=x->ch[0]->sum;
if(x->ch[1])x->size+=x->ch[1]->size,x->sum+=x->ch[1]->sum;
}
inline void rotate(node *x)
{
node *y=x->f, *z=y->f; int c=getwh(x);
if(isroot(y))x->f=z;else join(x,z,getwh(y));
join(x->ch[!c],y,c),join(y,x,!c);
pushup(y),pushup(x);
}
inline void splay(node *x)
{
node *y; int top=0;
for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y;
for(;top;top--)pushdown(s[top]);
while(!isroot(x))
{
y=x->f;
if(isroot(y)){rotate(x);return;}
if(getwh(x)^getwh(y))rotate(x);else rotate(y);
rotate(x);
}
}
inline void access(node *x)
{
node *t=0;
while(x)
{
splay(x);
x->ch[1]=t;
pushup(x);
t=x,x=x->f;
}
}
inline void makeroot(node *x){access(x);splay(x);rev(x);}
inline void link(node *x, node *y){makeroot(x);x->f=y;}
int read(int x=0)
{
char c=getchar();
while(c<48 or c>57)c=getchar();
while(c>=48 and c<=57)x=(x<<1)+(x<<3)+c-48,c=getchar();
return x;
}
void init()
{
int i, x, y;
N=read(), Q=read();
for(i=2;i<=N;i++)link(nd+i,nd+read()+1);
for(i=1;i<=Q;i++)
{
x=read()+1, y=read()+1, z[i]=read()+1;
l[x-1].push_back(i);
r[y].push_back(i);
}
}
void work()
{
int i, q; vector<int>::iterator it;
node *root=nd+1;
for(i=1;i<=N;i++)
{
access(nd+i);splay(root);root->add++;
for(it=l[i].begin();it!=l[i].end();it++)
{
q=*it;
access(nd+z[q]);splay(root);
ans[q]-=root->sum;
}
for(it=r[i].begin();it!=r[i].end();it++)
{
q=*it;
access(nd+z[q]);splay(root);
ans[q]+=root->sum;
}
}
}
int main()
{
int i;
init();
work();
for(i=1;i<=Q;i++)printf("%dn",ans[i]%mod);
return 0;
}

最后

以上就是洁净萝莉为你收集整理的bzoj3626: [LNOI2014]LCA链接填坑题解代码的全部内容，希望文章能够帮你解决bzoj3626: [LNOI2014]LCA链接填坑题解代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。