这题好(话说牛客的题目都很好)
我一眼看以为是到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;
}
超级好题,有思维含量。
找到帮派中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;
}
全部评论
(1) 回帖