CF911D：Inversion Counting（逆序数 & 思维）

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 ai < aj. 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, ..., an (1 ≤ ai ≤ 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 li, ri (1 ≤ li ≤ ri ≤ n) denoting that i-th query is to reverse a segment [li, ri] 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 
        
3
1 2 3
2
1 2
2 3

          output 
        
odd
even

          input 
        
4
1 2 4 3
4
1 1
1 4
1 4
2 3

          output 
        
odd
odd
odd
even

Note

The first example:

after the first query a = [2, 1, 3], inversion: (2, 1);
after the second query a = [2, 3, 1], inversions: (3, 1), (3, 2).

The second example:

a = [1, 2, 4, 3], inversion: (4, 3);
a = [3, 4, 2, 1], inversions: (3, 1), (4, 1), (3, 2), (4, 2), (4, 3);
a = [1, 2, 4, 3], inversion: (4, 3);
a = [1, 4, 2, 3], inversions: (3, 2), (4, 2).

题意：n个数排列，m个询问，每个询问反转一段区间，然后输出整个数组的逆序数的奇偶性。

思路：如果反转的区间有奇数个二元组数对，那么逆序数的奇偶性就改变。因为1=1+0=0+1。然后暴力or树状数组计算原数组的逆序数。

# include <bits/stdc++.h>
using namespace std;
int n, m, l, r, s=0, a[1503], b[1503];
int query(int x)
{
    int res=0;
    for(int i=x; i; i-=i&-i) res += b[i];
    return res;
}
void update(int x) {for(int i=x; i<=n; i+=i&-i) ++b[i]; }
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=n; i>=1; --i)
    {
        s = (s+query(a[i]-1))&1;
        update(a[i]);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&l,&r);
        if(((r-l+1)*(r-l)/2)&1) s^=1,printf(s?"odd":"even");
        else printf(s?"odd":"even");
        puts("");
    }
    return 0;
}

秒客网

CF911D：Inversion Counting（逆序数 & 思维）

相关文章