数组名用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数组标记的是第 i 头奶牛是第几高的。
CE时它说 “对rank有歧义” 是什么意思?求助。