这是一道看似复杂其实也不简单的思维题。
其实思路很明显。
因为这道题的数据范围比较大，有1e5的询问，如果暴力（像我考场上那样打平衡树）的话可以做到$mnlogn$。
但那样也是稳T。
经过思考之后我们可以发现，这道题必定要使用m的解法，也就是对于每一个询问$O1$求解。（总不可能$mlogn$求解）
那么怎么$O1$呢？
众所周知，$O1$算法自古以来就和数学脱不开关系。
而本题中有哪些量可以扯上来搞一搞呢？
具体的值？肯定不现实。
那也就只剩下区间长度了。
针对区间长度进行考察之后，我们可以发现这样的一件事：
如果区间中数对个数为偶数，那么翻转之后答案不变。
否则变化。
这是为什么呢？
很显然，翻转操作是具有封闭性的。换言之，不会影响到外面的元素。
而根据我们的手动模拟，翻转后逆序对个数=数对数-翻转前逆序对个数。
于是乎正解就出来了。
我们先用树状数组搞一搞原数组的逆序对。
然后对于每一组询问，异或一下判奇偶即可。
AC代码如下：
797ms 24kb
1 // By Ilverene 2 3 #include4 5 using namespace std; 6 7 namespace StandardIO{ 8 9 template inline void read(T &x){10 x=0;T f=1;char c=getchar();11 for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;12 for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';13 x*=f;14 }15 16 template inline void write(T x){17 if(x<0)putchar('-'),x*=-1;18 if(x>=10)write(x/10);19 putchar(x%10+'0');20 }21 22 }23 24 using namespace StandardIO;25 26 namespace Solve{27 28 // Define your constants here.29 const int N=1515;30 31 // Define your global variables here.32 int n,m,s=0,a[N],b[N];33 // Define your main functions here.34 template inline _Tp query(_Tp x){35 int res=0;36 for(int i=x;i;i-=i&-i)res+=b[i];37 return res;38 }39 void update(int x){40 for(int i=x;i<=n;i+=i&-i)++b[i];41 }42 43 inline void solve(){44 // Write your main logic here.45 read(n);46 for(int i=1;i<=n;++i)read(a[i]);47 for(int i=n;i>=1;--i){48 s=(s+query(a[i]-1))&1;49 update(a[i]);50 }51 read(m);52 while(m--){53 int l,r;54 read(l),read(r);55 if(((r-l+1)*(r-l)/2)&1)s^=1,printf(s?"odd":"even");56 else printf(s?"odd":"even");57 putchar('\n');58 } 59 }60 }61 62 using namespace Solve;63 64 int main(){65 // freopen(".in","r",stdin);66 // freopen(".out","w",stdout);67 solve();68 }