力竭了，求卡常，代码最高92分T#1，或者说是否时间复杂度有问题

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
struct IO {
#define MAXSIZE (1 << 17)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
 inline  char gc() {
#if DEBUG  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  inline void read(unsigned long long &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }
    
  inline  void read(unsigned int &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }

  inline  void read(char *s) {
    char ch = gc();
    for (; isspace(ch); ch = gc());
    for (; !isspace(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  inline void read(char &c) { for (c = gc(); isspace(c); c = gc()); }

  inline void push(const char &c) {
#if DEBUG
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  inline void write(unsigned long long x) {
    bool neg = false;
    if (x < 0) {
      neg = true;
      push('-');
    }
    static int sta[40];
    int top = 0;
    do {
      sta[top++] = x % 10;
      x /= 10;
    } while (x);
    if (neg)
      while (top) push('0' - sta[--top]);
    else
      while (top) push('0' + sta[--top]);
    push('\n');
  }



  inline void write(unsigned int x, char lastChar) { write(x), push(lastChar); }
} io;
unsigned int n,m; 
unsigned long long p[634][634],last;
unsigned long long l,r;
unsigned int sum[634][100001],lk[634],rk[634],idk[100001],kuainum[634][161][161],a[100001];
struct node{
	unsigned int id,x;
}b[100001];
static inline bool cmp(node s1,node s2){
	if(s1.x<s2.x) return 1;
    else return 0;
}
signed main(){
	io.read(n),io.read(m);
	for(int i=1;i<=n;i++){
		io.read(a[i]);
		b[i]=(node){i,a[i]};
	}
	unsigned int len=sqrt(n)/2,kuai=(n+len-1)/len;
//	if(kuai*kuai!=n) kuai++,len++;
	for(int i=1;i<=kuai;i++){
		lk[i]=rk[i-1]+1,rk[i]=min(n,lk[i]+len-1);
		sort(b+lk[i],b+rk[i]+1,cmp);
		for(int j=lk[i];j<=rk[i];j++){
			idk[j]=i;
			sum[i][a[j]]++;
		}
		for(int j=1;j<=n;j++){
			sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
		}
		int B=rk[i]-lk[i]+1;
		for(int r=2;r<=B;r++){
			int cnt=0;
			for(int l=r-1;l>=1;l--){
				if(a[lk[i]+l-1]>a[lk[i]+r-1]) cnt++;
				kuainum[i][l][r]=kuainum[i][l][r-1]+cnt;
			}
		}
	}
	for(int i=1;i<=kuai;i++){
		for(int j=i;j<=kuai;j++){
			p[i][j]=p[i][j-1]+kuainum[j][1][rk[j]-lk[j]+1];
			for(int k=lk[j];k<=rk[j];k++){
				p[i][j]+=sum[j-1][n]-sum[j-1][a[k]]-(sum[i-1][n]-sum[i-1][a[k]]);
			}
		}
	}
	while(m--){
		io.read(l),io.read(r);
		l^=last,r^=last;
		int idl=idk[l],idr=idk[r];
		if(idl==idr){
			last=kuainum[idl][l-lk[idl]+1][r-lk[idr]+1];
			io.write(last);
			continue;
		}
		last=0;
		if(idl+1<=idr-1){
			last=p[idl+1][idr-1];
		}
		last+=kuainum[idl][l-lk[idl]+1][rk[idl]-lk[idl]+1]+kuainum[idr][1][r-lk[idr]+1];
		if(idl+1<=idr-1){
			for(int i=lk[idr];i<=r;i++){
				last+=sum[idr-1][n]-sum[idr-1][a[i]]-(sum[idl][n]-sum[idl][a[i]]);
			}
			for(int i=l;i<=rk[idl];i++){
				last+=sum[idr-1][a[i]-1]-sum[idl][a[i]-1];
			}
		}
		int lt=lk[idr]-1,cnt=0;
		for(int i=lk[idl];i<=rk[idl];i++){
			if(b[i].id<l||b[i].id>r) continue;
			while(lt+1<=rk[idr]){
				if(b[lt+1].id<l||b[lt+1].id>r) lt++;
				else if(b[lt+1].x<b[i].x){
					cnt++,lt++;
				}
				else{
					break;
				} 
			}
			last+=cnt;
		}
        io.write(last);
	}
	return 0;
}