AcWing241. 楼兰图腾
在完成了分配任务之后，西部314来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。
西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。
西部314想知道，这n个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出V的个数和∧的个数。
输入格式
第一行一个数n。
第二行是n个数，分别代表y 1 ， y 2 , … , y n
输出格式
两个数，中间用空格隔开，依次为V的个数和∧的个数。
数据范围
对于所有数据，n≤200000,且输出答案不会超过int64。y 1 ∼ y n是 1 到 n 的一个排列。
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 200010; int n, a[N], tr[N]; int greate[N], lower[N]; void add(int x, int c) { //树状数组的插入操作 for (int i = x;i <= n;i += lowbit(i))tr[i] += c; } int sum(int x) { //树状数组的查询操作 int res = 0; for (int i = x;i;i -= lowbit(i))res += tr[i]; return res; } int main() { cin >> n; for (int i = 1;i <= n;++i)scanf("%d", &a[i]); //初始化原数组 for (int i = 1;i <= n;++i) { //从左到右 int y = a[i]; greate[i] = sum(n) - sum(y); //y左边比y大的数 lower[i] = sum(y - 1); //y左边比y小的数 add(y, 1); //在当前位置插入1 } memset(tr, 0, sizeof tr); LL res1 = 0, res2 = 0; for (int i = n;i;--i) { //从右到左 int y = a[i]; res1 += greate[i] * (LL)(sum(n) - sum(y)); // y右边比y大的数 res2 += lower[i] * (LL)(sum(y - 1)); // y右边比y小的数 add(y, 1); //当前位置插入1 } cout << res1 << " " << res2 << endl; //输出答案 return 0; }
