链接:https://ac.nowcoder.com/acm/contest/21763/1008
来源:牛客网
兔子最近喜欢上了逆序对。
一个逆序对(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
输出
复制
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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int a[N],tmp[N],q[N];
ll merge_sort(int l, int r)
{
if(l>=r) return 0;
int mid = l + r;
ll res = 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++] = a[j++];
res += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = a[i++];
while(j <= r ) tmp[k++] = a[j++];
for(int i = l,j = 0;i <= r;j ++,i++) a[i] = tmp[j];
return res;
}
int main()
{
int n,m;
cin>>n;
for(int i =1;i <= n;i ++) cin>>a[i];
cin>>m;
while(m--)
{
int s1,s2;
cin>>s1>>s2;
int temp;
a[temp] = a[s1];
a[s1] = a[s2];
a[s2] = a[temp];
ll k = merge_sort(1,n);
if(k % 2 == 0) cout<<"like"<<endl;
else cout<<"dislike"<<endl;
}
}
这个输入只能输入到第四行,之后为什么就输入不了了