为什么数组名用Rank能AC,用rank就CE?
查看原帖
为什么数组名用Rank能AC,用rank就CE?
958675
Linzijian2012楼主2023/11/4 10:24

数组名用rank:CE

CE代码:

//P3608
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
struct segment{
	int l, r, num;
}tree[N * 4];
struct cow{
	long long high;
	int pos;
}c[N];
int n, rank[N], ans, l[N], r[N];
bool cmp(cow x, cow y){
	return (x.high > y.high);
}
bool leaf(int u){
	return (tree[u].l == tree[u].r);
}
int lc(int u){
	return (2 * u);
}
int rc(int u){
	return (2 * u + 1);
}
void pushup(int u){
	tree[u].num = tree[lc(u)].num + tree[rc(u)].num;
	return;
}
void clear(int u){
	if (leaf(u)){
		tree[u].l = 0;
		tree[u].r = 0;
		tree[u].num = 0;
		return;
	}
	clear(lc(u));
	clear(rc(u));
	tree[u].l = 0;
	tree[u].r = 0;
	tree[u].num = 0;
	return;
}
void build(int u, int L, int R){
	tree[u].l = L;
	tree[u].r = R;
	if (leaf(u)){
		tree[u].num = 0;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	build(lc(u), tree[u].l, mid);
	build(rc(u), mid + 1, tree[u].r);
	pushup(u);
	return;
}
void posadd(int u, int p, int k){
	if (tree[u].l == p && tree[u].r == p){
		tree[u].num += k;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	if (p <= mid){
		posadd(lc(u), p, k);
	}
	if (mid < p){
		posadd(rc(u), p, k);
	}
	pushup(u);
	return;
}
int segsum(int u, int L, int R){
	if (L <= tree[u].l && tree[u].r <= R){
		return tree[u].num;
	}
	int res = 0, mid = (tree[u].l + tree[u].r) >> 1;
	if (L <= mid){
		res += segsum(lc(u), L, R);
	}
	if (mid < R){
		res += segsum(rc(u), L, R);
	}
	return res;
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lld", &c[i].high);
		c[i].pos = i;
	}
	sort(c + 1, c + n + 1, cmp);
	for (int i = 1; i <= n; i++){
		rank[c[i].pos] = i;
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++){
		int C = rank[i];
		l[i] = segsum(1, 1, C - 1);
		posadd(1, C, 1);
	}
	clear(1);
	build(1, 1, n);
	for (int i = n; i >= 1; i--){
		int C = rank[i];
		r[i] = segsum(1, 1, C - 1);
		posadd(1, C, 1);
	}
	for (int i = 1; i <= n; i++){
		int maxx = (l[i] > r[i] ? l[i] : r[i]);
		int minn = (l[i] < r[i] ? l[i] : r[i]);
		if (maxx > minn * 2){
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

数组名用Rank:AC

AC代码:

//P3608
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
struct segment{
	int l, r, num;
}tree[N * 4];
struct cow{
	long long high;
	int pos;
}c[N];
int n, Rank[N], ans, l[N], r[N];
bool cmp(cow x, cow y){
	return (x.high > y.high);
}
bool leaf(int u){
	return (tree[u].l == tree[u].r);
}
int lc(int u){
	return (2 * u);
}
int rc(int u){
	return (2 * u + 1);
}
void pushup(int u){
	tree[u].num = tree[lc(u)].num + tree[rc(u)].num;
	return;
}
void clear(int u){
	if (leaf(u)){
		tree[u].l = 0;
		tree[u].r = 0;
		tree[u].num = 0;
		return;
	}
	clear(lc(u));
	clear(rc(u));
	tree[u].l = 0;
	tree[u].r = 0;
	tree[u].num = 0;
	return;
}
void build(int u, int L, int R){
	tree[u].l = L;
	tree[u].r = R;
	if (leaf(u)){
		tree[u].num = 0;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	build(lc(u), tree[u].l, mid);
	build(rc(u), mid + 1, tree[u].r);
	pushup(u);
	return;
}
void posadd(int u, int p, int k){
	if (tree[u].l == p && tree[u].r == p){
		tree[u].num += k;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	if (p <= mid){
		posadd(lc(u), p, k);
	}
	if (mid < p){
		posadd(rc(u), p, k);
	}
	pushup(u);
	return;
}
int segsum(int u, int L, int R){
	if (L <= tree[u].l && tree[u].r <= R){
		return tree[u].num;
	}
	int res = 0, mid = (tree[u].l + tree[u].r) >> 1;
	if (L <= mid){
		res += segsum(lc(u), L, R);
	}
	if (mid < R){
		res += segsum(rc(u), L, R);
	}
	return res;
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lld", &c[i].high);
		c[i].pos = i;
	}
	sort(c + 1, c + n + 1, cmp);
	for (int i = 1; i <= n; i++){
		Rank[c[i].pos] = i;
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++){
		int C = Rank[i];
		l[i] = segsum(1, 1, C - 1);
		posadd(1, C, 1);
	}
	clear(1);
	build(1, 1, n);
	for (int i = n; i >= 1; i--){
		int C = Rank[i];
		r[i] = segsum(1, 1, C - 1);
		posadd(1, C, 1);
	}
	for (int i = 1; i <= n; i++){
		int maxx = (l[i] > r[i] ? l[i] : r[i]);
		int minn = (l[i] < r[i] ? l[i] : r[i]);
		if (maxx > minn * 2){
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

蒟蒻的rank数组标记的是第 ii 头奶牛是第几高的。

CE时它说 “对rank有歧义” 是什么意思?求助。

2023/11/4 10:24
加载中...