C++14(g++5.4) 解法, 执行用时: 320ms, 内存消耗: 8804K, 提交时间: 2019-09-26 23:05:10

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;

bitset<30001> mask;

int n;

struct BIT {
	int tree[N];
	inline int lowbit(int x) {
		return x & -x;
	}
	void add(int x, int v) {
		if (!x) return;
		for (int i = x; i <= n; i += lowbit(i))
			tree[i] += v;
	}
	int query(int x) {
		int ans = 0;
		for (int i = x; i; i -= lowbit(i)) 
			ans += tree[i];
		return ans;
	}
} bit[2];

int a[N], in[N], out[N], tol, o[N];
vector<int> G[N];

void dfs(int u, int fa) {
	in[u] = ++tol;
	for (auto v: G[u])
		if (v != fa) dfs(v, u);
	out[u] = tol;
}

bool cmp(const int &x, const int &y) {
	return a[x] < a[y];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		o[i] = i;
	}
	sort(o + 1, o + n + 1, cmp);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, -1);
	mask.set(0);
	for (int i = 1; i <= n; i++) {
		int u = o[i];
		int k1 = bit[0].query(in[u]), k2 = bit[1].query(out[u]) - bit[1].query(in[u] - 1);
		mask = mask << k1 | mask << k2;
		bit[0].add(in[u] + 1, 1); bit[0].add(out[u] + 1, -1);
		bit[1].add(in[u], 1);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int k;
		scanf("%d", &k);
		puts(mask.test(k) ? "Orz" : "QAQ");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 341ms, 内存消耗: 14232K, 提交时间: 2019-09-20 21:14:01

#include<cstdio>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;

const int N=1e5+5;

int q,n,a[N],o[N],id[N],tim,foo[N],bar[N],bit[N];
vector<int>E[N],Q[N];
bitset<30001>dp;

void modify(int x,int v){
	while(x<=n)bit[x]+=v,x+=x&-x;
}

int query(int x){
	int res=0;
	while(x)res+=bit[x],x^=x&-x;
	return res;
}

void dfs(int u,int f){
	id[++tim]=a[u];
	Q[tim].push_back(-u);
	foo[u]=query(a[u]);modify(a[u],1);
	for(int v:E[u])if(v!=f)dfs(v,u);
	modify(a[u],-1);
	Q[tim].push_back(u);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),o[i]=a[i];
	sort(o+1,o+n+1);
	for(int i=1;i<=n;++i)a[i]=lower_bound(o+1,o+n+1,a[i])-o;
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		E[x].push_back(y);E[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=n;++i){
		modify(id[i],1);
		for(int j:Q[i])
			if(j>0)bar[j]+=query(a[j]);
			else bar[-j]-=query(a[-j]);
	}
	dp[0]=1;
	for(int i=1;i<=n;++i)dp=(dp<<foo[i])|(dp<<bar[i]);
	scanf("%d",&q);
	for(int i=1,k;i<=q;++i){
		scanf("%d",&k);
		puts(dp[k]?"Orz":"QAQ");
	}
	return 0;
}