【洛谷P3899】谈笑风生

题目大意:给定一棵 N 个节点的有根树,1 号节点为根节点,现给出 Q 个询问,每次询问距离 u 号节点不超过 K 的节点 b,c 为 a 与 b 的后代,求这样的三元组有多少个。

题解:学会了线段树合并。

由于之前对线段树合并理解的不深刻,导致狂 WA 不止QAQ。

需要统计

\[\sum_{d e p t h(a)+k \geq d e p t h(b)} \operatorname({size}(b)-1)
\]

这是一个二维数点问题,可以在一个维度上建立权值线段树,在另一个维度上统计权值和即可。

需要将询问离线处理,因为当 N 棵线段树合并完毕时,对于子节点的线段树来说,里面不仅有自己子树的权值,也有其他子树的权值(合并导致)。因此,需要在递归遍历每个节点时,在递归结束时进行对每个节点统计询问,最后统一输出即可。

时间复杂度和空间复杂度均为 \(O(nlogn)\)。

代码如下

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1e5+10;
typedef long long ll; int n,a[maxn],d[maxn],cnt,ans[maxn];
vector<int> G[maxn];
struct node{
#define ls(o) t[o].lc
#define rs(o) t[o].rc
int lc,rc,sz;
}t[maxn*20];
int tot,root[maxn];
inline void pushup(int o){t[o].sz=t[ls(o)].sz+t[rs(o)].sz;}
void insert(int &o,int l,int r,int pos){
if(!o)o=++tot;
if(l==r){++t[o].sz;return;}
int mid=l+r>>1;
if(pos<=mid)insert(ls(o),l,mid,pos);
else insert(rs(o),mid+1,r,pos);
pushup(o);
}
int query(int o,int l,int r,int x,int y){
if(!o)return 0;
if(l==x&&r==y)return t[o].sz;
int mid=l+r>>1;
if(y<=mid)return query(ls(o),l,mid,x,y);
else if(x>mid)return query(rs(o),mid+1,r,x,y);
else return query(ls(o),l,mid,x,mid)+query(rs(o),mid+1,r,mid+1,y);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r){t[x].sz+=t[y].sz;return x;}
int mid=l+r>>1;
ls(x)=merge(ls(x),ls(y),l,mid);
rs(x)=merge(rs(x),rs(y),mid+1,r);
return pushup(x),x;
} void read_and_parse(){// 1 - n
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),d[i]=a[i];
sort(d+1,d+n+1);
cnt=unique(d+1,d+n+1)-d-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(d+1,d+cnt+1,a[i])-d;
for(int i=2,fa;i<=n;i++)scanf("%d",&fa),G[fa].pb(i);
} void dfs(int u){
for(auto v:G[u]){
dfs(v);
root[u]=merge(root[u],root[v],1,n);
}
ans[u]=t[root[u]].sz-query(root[u],1,n,1,a[u]-1);
insert(root[u],1,n,a[u]);
} void solve(){
dfs(1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
} int main(){
read_and_parse();
solve();
return 0;
}
上一篇:MySQL中GRANT和IDENTIFIED同时使用时出现near 'IDENTIFIED BY...” at line 1错误


下一篇:MySQL授权命令grant注意事项