题号：NC13947
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。
(x, y), (y, x)算一组。
输入描述:
第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]，分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000
输出描述:
输出一个整数表示满足条件的(x,y)数；64bit请用lld
示例1
输入
复制
4 1 3 1 2 2 4 4 1 2 3 4 3
输出
复制
5
AC Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 400005;
struct sd{
int gra[5];
};
LL res;
int n;
sd q[N], tmp[N];
bool cmp1(sd a, sd b)
{return a.gra[1] < b.gra[1];}
bool cmp2(sd a, sd b)
{return a.gra[2] < b.gra[2];}
void guisort(int l, int r, int p)
{
if (l == r) return ;
int mid = (l + r) >> 1;
guisort(l, mid, p);
guisort(mid + 1, r, p);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r)
{
if(q[i].gra[p] <= q[j].gra[p])
tmp[k ++ ] = q[i ++ ];
else
tmp[k ++ ] = q[j ++], res += mid - i + 1;
}
while(i <= mid)
tmp[k ++ ] = q[i ++ ];
while(j <= r)
tmp[k ++ ] = q[j ++ ];
for (int i = l; i <= r; ++ i)
q[i] = tmp[i];
}
void in()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= 3; ++ j)
scanf("%d", &q[i].gra[j]);
}
void ac()
{
sort(q + 1, q + 1 + n, cmp1);
guisort(1, n, 2);
guisort(1, n, 3);
guisort(1, n, 1);
printf("%lld", res / 2);
}
int main()
{
// freopen("test.in", "r", stdin);
in(); ac();
return 0;
}链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题号：NC20861
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
兔子最近喜欢上了逆序对。
一个逆序对(i,j) 需要满足 i < j 且 ai > aj
兔子觉得只是求一个序列的逆序对个数太没有意思了。
于是兔子想到了一个更有趣的问题！
兔子可以把区间[L,R] 反转，例如序列{1,2,3,4} 反转区间[1,3] 后是{3,2,1,4}。
兔子有m次反转操作，现在兔子想知道每次反转后逆序对个数是奇数还是偶数，兔子喜欢偶数，而讨厌奇数。
请注意，每一次反转操作都会对原序列进行改变。例如序列{1,2,3,4} 第一次操作区间[1,2] 后变成{2,1,3,4} 第二次反转区间[3,4] 后变成 {2,1,4,3}
输入描述:
第一行一个整数 n，表示序列的大小。 第二行 n 个整数ai 表示序列的各个元素。 第三行一个整数m，表示操作个数。 接下来 m 行，每行两个整数 l，r，表示反转的区间。
输出描述:
输出共m行每行一个字符串，表示反转后序列逆序对个数的奇偶性，如果是逆序对个数奇数，输出"dislike"(不含引号)，如果是偶数，输出"like"。
示例1
输入
复制4 1 2 3 4 4 1 2 3 4 1 4 2 3
4 1 2 3 4 4 1 2 3 4 1 4 2 3
输出
复制dislike like like dislike
dislike like like dislike
说明
注意：以下的(i,j)指的是位置 i 和位置 j
a={2,1,3,4} 的逆序对是 (1,2) 共1个，1是奇数，所以是dislike
a={2,1,4,3} 的逆序对是 (1,2) (3,4)共2个,2是偶数，所以是like
a={3,4,1,2} 的逆序对是 (1,3) (1,4) (2,3) (2,4)共4个,4是偶数，所以是like
a={3,1,4,2} 的逆序对是 (1,2) (1,4) (3,4) 共3个,3是奇数，所以是dislike
备注:
对于20%的数据 1 ≤ n ≤ 100 1 ≤ m ≤ 10 对于40%的数据 1 ≤ n ≤ 2000 1 ≤ m ≤ 50 对于60%的数据 1 ≤ n ≤ 2000 1 ≤ m ≤ 104 对于100%的数据 1 ≤ n ≤ 105 1 ≤ m ≤ 2*106
对于所有数据 l ≤ r且 ai 是n的一个排列，即ai互不相同且ai ≤ n
由于读入数据较大，建议使用快速读入。
AC Code:
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int q[N], tmp[N];
LL res;
inline int read()
{
int x = 0, t = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') t *= -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x *= 10;
x += c - 48;
c = getchar();
}
return t * x;
}
void merge_sort(int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else
{
tmp[k ++ ] = q[j ++ ];
res += mid - i + 1;
}
while(i <= mid) tmp[k ++ ] = q[i ++ ];
while(j <= r) tmp[k ++ ] = q[j ++ ];
for(int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
int l, r;
n = read();
for (int i = 1; i <= n; i ++ ) q[i] = read();
merge_sort(1, n);
cin >> m;
for (int i = 1; i <= m; i ++ )
{
l = read();
r = read();
res += (r - l + 1) * (r - l) / 2;
if(res % 2) printf("dislike\n");
else printf("like\n");
}
return 0;
}