CodeForces 911D Inversion Counting(思维)

D. Inversion Counting

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Description

A permutation of size n is an array of size n such that each integer from 1 to n occurs exactly once in this array. An inversion in a permutation p is a pair of indices (i, j) such that i > j and a**i < a**j. For example, a permutation [4, 1, 3, 2] contains 4 inversions: (2, 1), (3, 1), (4, 1), (4, 3).

You are given a permutation a of size n and m queries to it. Each query is represented by two indices l and r denoting that you have to reverse the segment [l, r] of the permutation. For example, if a = [1, 2, 3, 4] and a query l = 2, r = 4 is applied, then the resulting permutation is [1, 4, 3, 2].

After each query you have to determine whether the number of inversions is odd or even.

Input

The first line contains one integer n (1 ≤ n ≤ 1500) — the size of the permutation.

The second line contains n integers a1, a2, …, a**n (1 ≤ a**i ≤ n) — the elements of the permutation. These integers are pairwise distinct.

The third line contains one integer m (1 ≤ m ≤ 2·105) — the number of queries to process.

Then m lines follow, i-th line containing two integers l**i, r**i (1 ≤ l**i ≤ r**i ≤ n) denoting that i-th query is to reverse a segment [l**i, r**i] of the permutation. All queries are performed one after another.

Output

Print m lines. i-th of them must be equal to odd if the number of inversions in the permutation after i-th query is odd, and even otherwise.

Examples

input

1
2
3
4
5
3
1 2 3
2
1 2
2 3

output

1
2
odd
even

input

1
2
3
4
5
6
7
4
1 2 4 3
4
1 1
1 4
1 4
2 3

output

1
2
3
4
odd
odd
odd
even

Solution

题意

给你一个数组和若干区间,问你区间翻转后数组中逆序对数为奇数还是偶数。

思路

思维题目:首先求出区间的长度 $len = r-l+1$ ,那么区间内共有 $tot = \frac {len * (len-1)} 2$ 个数对。若 $tot$ 为奇数,则不管该区间有多少个逆序对,翻转区间后逆序对数奇偶性改变; 若为偶数,则不变。

所以我们可以先暴力求出整体逆序对数,再对区间进行以上处理。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 1505
#define INF 0x3f3f3f3f
#define DEBUG
#define DataIn
typedef long long LL;

using namespace std;

int a[MAXN];
int n, m;
int main()
{
int all = 0;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", a+i);
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
if(a[i] > a[j])
all++;
}

bool isodd = false;
if(all & 1)
isodd = true;

int l, r, len;
scanf("%d", &m);
for(int i=0; i<m; i++)
{
scanf("%d%d", &l, &r);
len = r-l+1;
if((len * (len-1) / 2) & 1)
isodd = !isodd;
if(isodd)
puts("odd");
else
puts("even");
}
return 0;
}

mark

# When Who Problem Lang Verdict Time Memory
41129808 2018-08-02 19:31:53 MoonChasing 911D - Inversion Counting GNU C++ Accepted 93 ms 0 KB
❤采之欲遗谁,所思在远道。❤
0%