题目链接
http://noi-test.zzstep.com/contest/0x40「数据结构进阶」例题/4201 楼兰图腾
分析
给出的纵坐标是按照横坐标升序给出的，对于所有纵坐标，在其左侧较小的数的个数乘上在其右侧较小的数的个数就是^的个数；v同理。
AC代码
#include <cstdio>
#include <cstring>
inline int read() {
int num
= 0;
char c
= getchar();
while (c
< '0' || c
> '9') c
= getchar();
while (c
>= '0' && c
<= '9')
num
= num
* 10 + c
- '0', c
= getchar();
return num
;
}
const int maxn
= 2e5 + 5;
int n
, a
[maxn
], b
[maxn
], c
[maxn
], bit
[maxn
];
inline int ask(int x
) {
int ret
= 0;
while (x
) ret
+= bit
[x
], x
-= x
& (-x
);
return ret
;
}
inline void add(int x
, int d
) {
while (x
<= n
) bit
[x
] += d
, x
+= x
& (-x
);
}
int main() {
n
= read();
for (int i
= 1; i
<= n
; ++i
)
a
[i
] = read(), b
[i
] = ask(a
[i
] - 1), add(a
[i
], 1);
memset(bit
, 0, sizeof(bit
));
for (int i
= n
; i
; --i
) c
[i
] = ask(a
[i
] - 1), add(a
[i
], 1);
long long cnt1
= 0, cnt2
= 0;
for (int i
= 1; i
<= n
; ++i
)
cnt1
+= (i
- 1ll - b
[i
]) * (n
- i
- c
[i
]), cnt2
+= 1ll * b
[i
] * c
[i
];
printf("%lld %lld", cnt1
, cnt2
);
return 0;
}
