【牛客挑战赛32E】树上逆序对

数据范围非常奇怪，询问的逆序对个数\(k\leq 30000\)，我们应该可以把所有的情况都求出来

发现对于树上两点\(x,y\)，如果\(x\)是\(y\)的祖先，那么绝对值较大的点的符号决定了能否形成逆序对

如果\(a_x>a_y\)，不取反\(a_x\)，那么无论\(a_y\)取反与否，肯定会形成逆序对，因为\(a_x>a_y>-a_y\)；反之如果取反\(a_x\)，那么无论\(a_y\)取反与否，肯定不对形成逆序对，因为\(a_y>-a_y>-a_x\)

于是我们按照绝对值从小到大排序，之后按照顺序加入树中，一个点对答案的贡献是其子树内部小于它的点的个数加上到根的路径上大于它的点的个数；当我们加入一个点\(x\)时，如果不取反，那么到根的路径上显然不会有点大于它，且子树内部全都小于它，形成的逆序对个数就是其子树内部的点的个数；如果取反，那么到根的路径上的点全都大于它，子树内部不会有点小于它，形成的逆序对个数就是到根的路径上点的个数

所以用树剖+树状数组求一下，之后搞一个背包来转移就好了，背包需要\(\rm bitset\)优化

复杂度\(O(n\log^2n+\frac{nk}{w})\)

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

#define lb(i) (i&-i)

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=1e5+5;

struct E{int v,nxt;}e[maxn<<1];

struct pt{int x,id;}a[maxn];

std::bitset<300001> dp;

int n,num,Q,c[maxn],__;

int sum[maxn],dfn[maxn],top[maxn],fa[maxn],head[maxn],deep[maxn],son[maxn];

inline int cmp(pt A,pt B) {return A.x<B.x;}

inline void add(int x,int y) {

	e[++num].v=y;e[num].nxt=head[x];head[x]=num;

}

inline void ins(int x) {

	for(re int i=x;i<=n;i+=lb(i)) c[i]++;

}

inline int ask(int x) {

	int now=0;

	for(re int i=x;i;i-=lb(i)) now+=c[i];

	return now;

}

inline int calc(int l,int r) {return ask(r)-ask(l-1);}

inline int get(int x) {

	int now=0;

	while(top[x]) now+=calc(dfn[top[x]],dfn[x]),x=fa[top[x]];

	return now;

}

void dfs1(int x) {

	sum[x]=1;

	for(re int i=head[x];i;i=e[i].nxt) {

		if(deep[e[i].v]) continue;

		deep[e[i].v]=deep[x]+1,fa[e[i].v]=x;

		dfs1(e[i].v),sum[x]+=sum[e[i].v];

		if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;

	}

}

void dfs2(int x,int topf) {

	top[x]=topf,dfn[x]=++__;

	if(!son[x]) return;

	dfs2(son[x],topf);

	for(re int i=head[x];i;i=e[i].nxt)

	if(!top[e[i].v]) dfs2(e[i].v,e[i].v);

}

int main() {

	n=read();

	for(re int i=1;i<=n;i++) a[i].x=read(),a[i].id=i;

	for(re int x,y,i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);

	deep[1]=1,dfs1(1),dfs2(1,1);

	std::sort(a+1,a+n+1,cmp);

	dp[0]=1;

	for(re int i=1;i<=n;i++) {

		int x=calc(dfn[a[i].id],dfn[a[i].id]+sum[a[i].id]-1),y=get(a[i].id);

		dp=(dp<<x)|(dp<<y);ins(dfn[a[i].id]);

	}

	Q=read();while(Q--) puts(dp[read()]?"Orz":"QAQ");

	return 0;

}

巴特西

【牛客挑战赛32E】树上逆序对

最新文章

热门文章