感觉这题还是不错的……虽然其实算是比较水的题= =
首先分块，令f[i][j]表示第i块到第j块的逆序对数，询问的时候直接计算不完整块与完整块以及不完整块之间的逆序对。
不完整块之间的逆序对直接树状数组暴力求，至于不完整块和完整块的逆序对，我是令s[i]表示前i块的权值前缀和，这样单次查询O(1)，可以减小一点常数，代价是空间稍微费了点……
预处理O(nsqrt(n)logn)，单次查询O(sqrt(n)logn)，空间O(nsqrt(n))，好吧我懒得算如何调节块大小来降低复杂度了，于是就随便找了个233当的块大小= =
细节并不多，然而因为各种脑残错误调了半天才敢交，又因为没看见要离散化和没加强制在线RE两次，真是废了……
/**************************************************************
Problem: 3744
User: hzoier
Language: C++
Result: Accepted
Time:9688 ms
Memory:49700 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,B=,maxb=;
void add(int,int);
int query(int);
int a[maxn],b[maxn],id[maxn],L[maxb]={},R[maxb]={},cntb,f[maxb][maxb]={{}},s[maxb][maxn]={{}},c[maxn]={};
int n,m,l,r,lb,rb,ans=;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
cntb=id[i]=(i-)/B+;
if(!L[id[i]])L[id[i]]=i;
R[id[i]]=i;
}
copy(a+,a+n+,b+);
sort(b+,b+n+);
for(int i=;i<=n;i++)s[id[i]][a[i]=lower_bound(b+,b+n+,a[i])-b]++;
for(int i=;i<=cntb;i++){
for(int j=;j<=n;j++)s[i][j]+=s[i-][j];
for(int j=i;j<=cntb;j++){
for(int k=L[j];k<=R[j];k++){
f[i][j]+=query(a[k]+);
add(a[k],);
}
f[i][j]+=f[i][j-];
}
memset(c,,sizeof(c));
}
for(int i=;i<=cntb;i++)for(int j=;j<=n;j++)s[i][j]+=s[i][j-];
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
l^=ans;r^=ans;
if(id[l]>=id[r]-){
ans=;
for(int i=l;i<=r;i++){
ans+=query(a[i]+);
add(a[i],);
}
for(int i=l;i<=r;i++)add(a[i],-);
}
else{
lb=id[l]+;rb=id[r]-;
ans=f[lb][rb];
for(int i=l;i<L[lb];i++){
ans+=query(a[i]+)+s[rb][a[i]-]-s[lb-][a[i]-];
add(a[i],);
}
for(int i=R[rb]+;i<=r;i++){
ans+=query(a[i]+)+(s[rb][n]-s[rb][a[i]])-(s[lb-][n]-s[lb-][a[i]]);
add(a[i],);
}
for(int i=l;i<L[lb];i++)add(a[i],-);
for(int i=R[rb]+;i<=r;i++)add(a[i],-);
}
printf("%d\n",ans);
}
return ;
}
void add(int x,int d){
while(x){
c[x]+=d;
x&=x-;
}
}
int query(int x){
int ans=;
while(x<=n){
ans+=c[x];
x+=x&-x;
}
return ans;
}