牛客练习赛2

A.Contest

这题好（话说牛客的题目都很好）

我一眼看以为是到tarjan，后来发现可以转化为cdq分治求三维偏序问题

我们把三场比赛的名次设为a[i],b[i],c[i].

答案可以转化为求多少对是a[i]>a[j],b[i]>b[j],c[i]>c[j]

可以发现这不就是cdq分治求三维偏序吗

cdq分治就是第一维排序，第二维归并排序，第三维树状数组

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int n,tot,ans,c[N];
struct node{
    int x,y,z;
}a[N],y[N];
char buf[1<<21],*p1=buf,*p2=buf;
/*inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int res=0,f=0;
    char c;
    c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        res=res*10+c-48;
        c=gc();
    }
    if(f)return -res;
    return res;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    while(x<N)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)/2;
    cdq(l,mid);cdq(mid+1,r);
    int L=l,R=mid+1,tot=l;
    while(L<=mid&&R<=r)
    {
        if(a[L].y<=a[R].y)add(a[L].z,1),y[tot++]=a[L++];
        else ans-=sum(a[R].z),y[tot++]=a[R++];
    }
    while(L<=mid)
    {
        add(a[L].z,1);
        y[tot++]=a[L++];
    }
    while(R<=r)
    {
        ans-=sum(a[R].z);
        y[tot++]=a[R++];
    }
    for(int i=l;i<=mid;i++)add(a[i].z,-1);
    for(int i=l;i<=r;i++)a[i]=y[i];
}
bool cmp(node a,node b)
{
    return a.x<b.x;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].x=read();
        a[i].y=read();
        a[i].z=read();
    }
    sort(a+1,a+n+1,cmp);
    ans=n*(n-1)/2;
    cdq(1,n);
    cout<<ans;
    return 0;
}

C. Alliances

超级好题，有思维含量。

找到帮派中dfs序在首都附近的两个点。

    一个比它小，一个比它大，分别求lca.

答案就是lca与首都的距离取min 

有公式:$dep[u]-dep[v]+max(dep[Top]-dep[v],0)$ $v=lca(u,x)$    x为dfs序最接近u的点

lower_bound(dfs序)找到最接近的比他大的点

#include
using namespace std;
const int N=500005;
int n,m,x,y,u,q,ans,Top,num,t,deep,a[N],dep[N],ru[N],chu[N],top[N],dfn[N],id[N],f[N][25];
vectorg[N],v[N];
vector::iterator it;
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p1&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int res=0,f=0;
    char c;
    c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        res=res*10+c-48;
        c=gc();
    }
    if(f)return -res;
    return res;
}
void dfs(int u,int fa)
{
    ru[u]=++t;dfn[u]=++deep;id[deep]=u;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i]==fa)continue;
        f[g[u][i]][0]=u;
        dep[g[u][i]]=dep[u]+1;
        dfs(g[u][i],u);
    }
    chu[u]=++t;
}
bool pd(int x,int y)
{
    if(ru[x]=chu[y])return true;
    return false;
}
int lca(int x,int y)
{
    if(pd(x,y))return x;
    if(pd(y,x))return y;
    for(int i=20;i>=0;i--)
    {
        if(!pd(f[x][i],y))x=f[x][i];
    }
    return f[x][0];
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        x=read();y=read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    f[1][0]=1;
    dfs(1,0);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];
    m=read();
    for(int i=1;i<=m;i++)
    {
        num=read();
        for(int j=1;j<=num;j++)
        {
            u=read();
            v[i].push_back(dfn[u]);
            if(j==1)top[i]=u;
            else top[i]=lca(top[i],u);
        }
        sort(v[i].begin(),v[i].end());
    }
    q=read();
    while(q--)
    {
        ans=n;
        u=read();num=read();
        for(int i=1;i<=num;i++)
        {
            a[i]=read();
            if(i==1)Top=top[a[i]];
            else Top=lca(Top,top[a[i]]);
        }
        for(int i=1;i<=num;i++)
        {
            it=lower_bound(v[a[i]].begin(),v[a[i]].end(),dfn[u]);
            if(it!=v[a[i]].end())
            {
                int v=lca(u,id[*it]);
                ans=min(ans,dep[u]-dep[v]+max(dep[Top]-dep[v],0));
            }
            if(it!=v[a[i]].begin())
            {
                --it;
                int v=lca(u,id[*it]);
                ans=min(ans,dep[u]-dep[v]+max(dep[Top]-dep[v],0));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}