这是一道看似复杂其实也不简单的思维题。
其实思路很明显。
因为这道题的数据范围比较大，有1e5的询问，如果暴力（像我考场上那样打平衡树）的话可以做到$mnlogn$。
但那样也是稳T。
经过思考之后我们可以发现，这道题必定要使用m的解法，也就是对于每一个询问$O1$求解。（总不可能$mlogn$求解）
那么怎么$O1$呢？
众所周知，$O1$算法自古以来就和数学脱不开关系。
而本题中有哪些量可以扯上来搞一搞呢？
具体的值？肯定不现实。
那也就只剩下区间长度了。
针对区间长度进行考察之后，我们可以发现这样的一件事：
如果区间中数对个数为偶数，那么翻转之后答案不变。
否则变化。
这是为什么呢？
很显然，翻转操作是具有封闭性的。换言之，不会影响到外面的元素。
而根据我们的手动模拟，翻转后逆序对个数=数对数-翻转前逆序对个数。
于是乎正解就出来了。
我们先用树状数组搞一搞原数组的逆序对。
然后对于每一组询问，异或一下判奇偶即可。
AC代码如下：
797ms 24kb
// By Ilverene
#include<bits/stdc++.h>
using namespace std;
namespace StandardIO{
template<typename T>inline void read(T &x){
x=;T f=;char c=getchar();
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(;c>=''&&c<='';c=getchar())x=x*+c-'';
x*=f;
}
template<typename T>inline void write(T x){
if(x<)putchar('-'),x*=-;
if(x>=)write(x/);
putchar(x%+'');
}
}
using namespace StandardIO;
namespace Solve{
// Define your constants here.
const int N=;
// Define your global variables here.
int n,m,s=,a[N],b[N];
// Define your main functions here.
template<typename _Tp>inline _Tp query(_Tp x){
int res=;
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];
}
inline void solve(){
// Write your main logic here.
read(n);
for(int i=;i<=n;++i)read(a[i]);
for(int i=n;i>=;--i){
s=(s+query(a[i]-))&;
update(a[i]);
}
read(m);
while(m--){
int l,r;
read(l),read(r);
if(((r-l+)*(r-l)/)&)s^=,printf(s?"odd":"even");
else printf(s?"odd":"even");
putchar('\n');
}
}
}
using namespace Solve;
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
solve();
}