首页 > 代码库 > BZOJ 2588 Count on a tree 主席树+倍增LCA
BZOJ 2588 Count on a tree 主席树+倍增LCA
题目大意：给定一棵树，每个节点有权值，询问两个节点路径上的权值第k小
这题很卡时间。。。
树链剖分+二分+树套树的O(nlog^4n)做法可以去死了
没有修改操作，树链剖分+二分+划分树O(nlog^3n)，还是死了
我怒了，裸学了一发可持久化线段树(不看任何代码OTZ，我是怎么做到的0.0)，二分+主席树，O(nlog^2n)，居然还是死了！
最后发现我SB了，完全没有必要二分，直接把4个参全传下去就行了，O(nlogn)
首先我们对于每个节点维护这个节点到根的权值线段树 然后对于每个询问(x,y)，这条路径上的线段树就是tree[x]+tree[y]-tree[lca(x,y)]-tree[fa[lca(x,y)]]
把四个节点全都传参，然后当作普通权值线段树做正常求第k小就行了
时间复杂度O(nlogn)
最后一个回车不能输出，否则会PE。。。坑爹啊，难怪这题PE的数量占了AC的2/3。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
struct Tree{
Tree *ls,*rs;
int num;
Tree(Tree*_,Tree*__,int ___):ls(_),rs(__),num(___){}
}*tree[M];
Tree* Build_Tree(Tree *p,int x,int y,int z)
{
int mid=x+y>>1;
if(x==y)
return new Tree(tree[0],tree[0],p->num+1);
if(z<=mid)
return new Tree(Build_Tree(p->ls,x,mid,z),p->rs,p->num+1);
else
return new Tree(p->ls,Build_Tree(p->rs,mid+1,y,z),p->num+1);
}
int Get_Ans(Tree *p1,Tree *p2,Tree *p3,Tree *p4,int x,int y,int k)
{
int mid=x+y>>1;
if(x==y)
return mid;
int temp = p1->ls->num + p2->ls->num - p3->ls->num - p4->ls->num ;
if(k<=temp) return Get_Ans( p1->ls , p2->ls , p3->ls , p4->ls , x , mid , k );
else return Get_Ans( p1->rs , p2->rs , p3->rs , p4->rs , mid+1 , y , k-temp );
}
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot;
int n,m,ans;
int a[M],fa[M][20],dpt[M];
pair<int,int>b[M];
void Add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x)
{
int i;
dpt[x]=dpt[fa[x][0]]+1;
tree[x]=Build_Tree(tree[fa[x][0]],1,n,a[x]);
for(i=head[x];i;i=table[i].next)
{
if(table[i].to==fa[x][0])
continue;
fa[table[i].to][0]=x;
DFS(table[i].to);
}
}
int LCA(int x,int y)
{
int j;
if(dpt[x]<dpt[y])
swap(x,y);
for(j=19;~j;j--)
if(dpt[fa[x][j]]>=dpt[y])
x=fa[x][j];
if(x==y)
return x;
for(j=19;~j;j--)
if(fa[x][j]!=fa[y][j])
x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
int Query(int x,int y,int k)
{
int lca=LCA(x,y);
return Get_Ans( tree[x] , tree[y] , tree[lca] , tree[fa[lca][0]] , 1 , n , k );
}
int main()
{
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
int i,j,x,y,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
scanf("%d",&b[i].first);
b[i].second=i;
}
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
a[b[i].second]=i;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
Add(x,y);
Add(y,x);
}
tree[0]=new Tree(0x0,0x0,0);
tree[0]->ls=tree[0]->rs=tree[0];
DFS(1);
for(j=1;j<=19;j++)
for(i=1;i<=n;i++)
fa[i][j]=fa[ fa[i][j-1] ][j-1];
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&k);
printf("%d",ans=b[Query(x^ans,y,k)].first);
if(i!=m)
puts("");
}
}
附送我TLE了的树链剖分+划分树。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
inline int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
inline int getint() {
int c;
while(!isdigit(c = getc()) && c != '-');
bool sign = c == '-';
int tmp = sign ? 0 : c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return sign ? -tmp : tmp;
}
inline void output(int x)
{
static int a[20];
if (x == 0)
putchar('0');
else {
int top = 0;
if (x < 0)
putchar('-'), x=-x;
while(x) {
a[++top] = x % 10;
x /= 10;
}
for(int i = top; i >= 1; --i)
putchar('0' + a[i]);
}
}
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot;
int n,m,ans,maxnum;
int f[M],fa[M],son[M],dpt[M],siz[M],top[M],pos[M],a[M],b[M],c[M],s[20][M],cnt;
inline void add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void bfs()
{
static int q[M],r=0,h=0;
int i,x;
q[++r]=1;
while(r!=h)
{
x=q[++h];
dpt[x]=dpt[fa[x]]+1;
siz[x]=1;
for(i=head[x];i;i=table[i].next)
{
if(table[i].to==fa[x])
continue;
fa[table[i].to]=x;
q[++r]=table[i].to;
}
}
for(i=n;i;i--)
{
x=q[i];
siz[fa[x]]+=siz[x];
if(siz[x]>siz[son[fa[x]]])
son[fa[x]]=x;
}
for(i=1;i<=n;i++)
{
x=q[i];
if(son[fa[x]]==x)
top[x]=top[fa[x]];
else
{
top[x]=x;
for(;x;x=son[x])
pos[x]=++cnt,a[pos[x]]=f[x];
}
}
}
void Build_Tree(int l,int r,int dpt)
{
if(l==r)
return ;
int i,mid=l+r>>1;
int l1=l,l2=mid+1;
int left=mid-l+1;
for(i=l;i<=r;i++)
left-=(a[i]<c[mid]);
for(i=l;i<=r;i++)
{
if(a[i]<c[mid]||a[i]==c[mid]&&left)
b[l1++]=a[i],s[dpt][i]=(i==l?1:s[dpt][i-1]+1),left-=(a[i]==c[mid]);
else
b[l2++]=a[i],s[dpt][i]=(i==l?0:s[dpt][i-1]);
}
memcpy( a+l , b+l , sizeof(a[0])*(r-l+1) );
Build_Tree(l,mid,dpt+1);
Build_Tree(mid+1,r,dpt+1);
}
int Get_Ans(int l,int r,int dpt,int x,int y,int val)
{
int mid=l+r>>1;
int l1=(x==l?0:s[dpt][x-1]),l2=s[dpt][y];
if(x>y)
return 0;
if(l==r)
return c[mid]<=val;
if(val<c[mid])
return Get_Ans(l,mid,dpt+1,l+l1,l+l2-1,val);
else
return l2-l1+Get_Ans(mid+1,r,dpt+1,(mid+1)+(x-l-l1),(mid+1)+(y-l+1-l2)-1,val);
}
bool Query(int x,int y,int val,int k)
{
int re=0,fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dpt[fx]<dpt[fy])
swap(x,y),swap(fx,fy);
re+=Get_Ans(1,n,0,pos[fx],pos[x],val);
if(re>=k)
return true;
x=fa[fx];fx=top[x];
}
if(dpt[x]<dpt[y])
swap(x,y);
re+=Get_Ans(1,n,0,pos[y],pos[x],val);
if(re>=k)
return true;
return false;
}
inline int Divide(int x,int y,int k)
{
int l=0,r=maxnum;
while(l+1!=r)
{
int mid=l+r>>1;
if( Query(x,y,mid,k) )
r=mid;
else
l=mid;
}
if( Query(x,y,l,k) )
return l;
return r;
}
int main()
{
//freopen("count.in","r",stdin);
//freopen("bf.out","w",stdout);
int i,x,y,k;
cin>>n>>m;
for(i=1;i<=n;i++)
f[i]=getint(),maxnum=max(maxnum,f[i]);
for(i=1;i<n;i++)
x=getint(),y=getint(),add(x,y),add(y,x);
bfs();
memcpy(c+1,a+1,n<<2);
sort(c+1,c+n+1);
Build_Tree(1,n,0);
for(i=1;i<=m;i++)
{
x=getint();y=getint();k=getint();
x^=ans;
ans=Divide(x,y,k);
output(ans);
if(i!=m)
puts("");
}
return 0;
}
BZOJ 2588 Count on a tree 主席树+倍增LCA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。