题目链接
E 树上逆序对 (树链剖分+主席树)
题意:
给定一颗树,每一个点有一个权值为 v i v_i vi或者 − v i -v_i −vi,多次询问能否存在 k k k 个树上逆序对。树上逆序对的定义为:若有一对节点 ( x , y ) (x,y) (x,y) ,满足 x x x 是 y y y 的祖先,且 x x x 点权值大于 y y y 点的权值,则 ( x , y ) (x,y) (x,y) 为一个树上逆序对。
思路:
由于是多次询问,考虑预处理出所以能得到的逆序对数,对于一队顶点 ( i , j ) (i,j) (i,j) 考虑绝对值大的点产生的贡献,当它取正数是它的贡献是对于其子树权值绝对值比它小的个数,当它取负数时,它的贡献是它的所有祖先权值绝对值比它小的个数。那么我们只要处理出每一个点 i i i 的祖先和子树中比 ∣ v i ∣ |v_i| ∣vi∣ 小的个数即可,方法很多,这里用树剖和主席树解。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//初始化
int n,q,m;
int c[N],C[N];
vector<int>e[N];
vector<int>v;
int getid(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]),v.push_back(c[i]);
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++)C[i]=getid(c[i]);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
e[u].push_back(v);e[v].push_back(u);
}
}
//主席树
int rt[N*50];
struct zx_tree{
int ls[N*50],rs[N*50],tot,sum[N*50];
inline void update(int &root,int pre,int l,int r,int pos){
root=++tot;ls[root]=ls[pre],rs[root]=rs[pre],sum[root]=sum[pre]+1;
if(l==r)return ;
int mid=(l+r)/2;
if(pos<=mid)update(ls[root],ls[pre],l,mid,pos);
else update(rs[root],rs[pre],mid+1,r,pos);
}
inline int query(int root,int pre,int l,int r,int k){//区间小于k的个数
if(r<k)return sum[root]-sum[pre];//root>pre
if(l==r)return 0;
int mid=(l+r)/2;
if(k<=mid)return query(ls[root],ls[pre],l,mid,k);
else return query(rs[root],rs[pre],mid+1,r,k)+sum[ls[root]]-sum[ls[pre]];
}
}T;
//树剖
int tot[N],son[N],deep[N],fa[N];
int dfs1(int u,int f,int dep){
tot[u]=1;fa[u]=f;deep[u]=dep;
int pd=-1;
for(int v:e[u]){
if(v==f)continue;
tot[u]+=dfs1(v,u,dep+1);
if(tot[v]>pd)pd=tot[v],son[u]=v;
}
return tot[u];
}
int idx[N],top[N],id[N],cnt;
void dfs2(int u,int f){
idx[u]=++cnt,id[cnt]=u;
top[u]=f;
if(!son[u])return ;
dfs2(son[u],f);
for(int v:e[u]){
if(!idx[v])dfs2(v,v);
}
}
int ljquery(int x,int y,int k){
int ans=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
ans+=T.query(rt[idx[x]],rt[idx[top[x]]-1],1,m,k);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
ans+=T.query(rt[idx[y]],rt[idx[x]-1],1,m,k);
return ans;
}
int x[N],y[N];
bitset<30005>jl;
void cl(){
dfs1(1,0,1);dfs2(1,0);m=v.size();
for(int i=1;i<=n;i++)T.update(rt[i],rt[i-1],1,m,C[id[i]]);
for(int i=1;i<=n;i++){
if(i!=1)x[i]=ljquery(fa[i],1,C[i]);
if(son[i])y[i]=T.query(rt[idx[i]+tot[i]-1],rt[idx[i]],1,m,C[i]);
}
jl[0]=1;
for(int i=1;i<=n;i++){
jl=(jl<<x[i])|(jl<<y[i]);
}
scanf("%d",&q);
int t;
while(q--){
scanf("%d",&t);
if(jl[t])puts("Orz");
else puts("QAQ");
}
}
int main()
{
init();
cl();
}