bzoj 2588: Spoj 10628. Count on a tree 주석 트 리 + dfs 순서

2575 단어 데이터 구조
hzhwcmhf 가 말 했 습 니 다. 이 문 제 는 주석 나무 입 니 다. 그리고 저 는 그때 나무 사슬 로 나 누 어 그렇게 하 라 고 했 습 니 다. 떨 어 졌 는 지 안 떨 어 졌 는 지 나중에 알 게 되 었 습 니 다. dfs 순서 입 니 다. 큰 차이 가 없 지만 곰 곰 이 생각해 보면 나무 가 그렇게 하 는 것 은 완전히 불필요 합 니 다.예전 의 나 는 너무 약 했다.
#include
#include
#include
#include
#include
#define inf 0x7fffffff
#define ll long long
#define N 100005
#define M 2000005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,tot,siz,cnt,ind,last;
int num[N],pos[N];
int v[N],tmp[N],hash[N],root[N];
int ls[M],rs[M],sum[M];
int deep[N],fa[N][17];
struct data{int to,next;}e[200005];int head[N];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
int find(int x)
{
    int l=1,r=tot;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(hash[mid]=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
void update(int l,int r,int x,int &y,int val)
{
    siz++;
    y=siz;
    sum[y]=sum[x]+1;
    if(l==r) return;
    ls[y]=ls[x];rs[y]=rs[x];
    int mid=(l+r)>>1;
    if(val<=mid)update(l,mid,ls[x],ls[y],val);
    else update(mid+1,r,rs[x],rs[y],val);
}
int que(int x,int y,int k)
{
    int a=x,b=y,c=lca(x,y),d=fa[c][0];
    a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
    int l=1,r=tot;
    while(l>1;
        int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
        if(tmp>=k)
        {
            r=mid;
            a=ls[a];b=ls[b];c=ls[c];d=ls[d];
        }
        else
        {
            k-=tmp;
            l=mid+1;
            a=rs[a];b=rs[b];c=rs[c];d=rs[d];
        }
    }
    return hash[l];
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        v[i]=read(),tmp[i]=v[i];
    sort(tmp+1,tmp+n+1);
    hash[++tot]=tmp[1];
    for(int i=2;i<=n;i++)
        if(tmp[i]!=tmp[i-1])hash[++tot]=tmp[i];
    for(int i=1;i<=n;i++)v[i]=find(v[i]);
    for(int i=1;i

좋은 웹페이지 즐겨찾기