CodeForces 911D Inversion Counting (思维)

发表于 更新于 分类于 ， 本文字数： 2.5k 阅读时长 ≈ 5 分钟

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
8
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