目前可以卡进 800ms

求卡常/dk

#include <bits/stdc++.h>
#define siz 633
typedef long long ll;
#define EOL putchar('\n')
#define getchar() (bp1==bp2&&(bp2=(bp1=buf)+fread(buf,1,fast_io,stdin),bp1==bp2)?EOF:*bp1++)
#define putchar(x) (bp3-obuf<fast_io?0:(fwrite(obuf,1,fast_io,stdout),bp3=obuf),*bp3++=(x))
#define END (fwrite(obuf,1,bp3-obuf,stdout),exit(0))
const int fast_io = 15000003;
char buf[fast_io], obuf[fast_io], *bp1 = buf, *bp2 = buf, *bp3 = obuf;
void rd(ll &x)
{
    int ch; x = 0;
    while(isspace(ch=getchar()));
    if(ch == EOF) return;
    do x = ch-'0'+x*10; while(isdigit(ch=getchar()));
}
void rd(int &x)
{
    int ch; x = 0;
    while(isspace(ch=getchar()));
    if(ch == EOF) return;
    do x = ch-'0'+x*10; while(isdigit(ch=getchar()));
}
void pt(ll x)
{
    if(x>9)pt(x/10);
    putchar(x%10+'0');
}
struct Node {
   int val, pos;
   bool operator < (const Node &rhs) const { return val < rhs.val; }
} b2[100011];
int p[100011], n, B, N, L[333], R[333], bel[100011], bi[100011], i, j, len, k, pos;
int pre[100011], suf[100011], b21[100011], b22[100011];
ll f[333][100011], d[333][333];
inline void add(int k, int d)
{//cout<<k<<endl;
   for(; k <= n; k += k&-k) bi[k] += d;
}
inline int ask(int k)
{//cout<<k<<endl;
   int ans = 0; for(; k; k &= k-1) ans += bi[k];
   return ans;
}
void init()
{
   B = std::min(siz, n);
   L[1] = N = 1; R[1] = B;
   while(R[N] < n) { L[N+1] = R[N]+1; R[N+1] = std::min(n, R[N]+B); ++N; }
   for(i = 1; i <= n; i += 8)
   {
      b2[i] = (Node) { p[i], i };
      b2[i+1] = (Node) { p[i+1], i+1 };
      b2[i+2] = (Node) { p[i+2], i+2 };
      b2[i+3] = (Node) { p[i+3], i+3 };
      b2[i+4] = (Node) { p[i+4], i+4 };
      b2[i+5] = (Node) { p[i+5], i+5 };
      b2[i+6] = (Node) { p[i+6], i+6 };
      b2[i+7] = (Node) { p[i+7], i+7 };
   }
   for(i = 1; i <= N; ++i)
   {
      std::sort(b2+L[i], b2+R[i]+1);
      for(j = L[i]; j <= R[i]; ++j) bel[j] = i, b21[j] = b2[j].val, b22[j] = b2[j].pos;
      int x = 0;
      for(j = L[i]; j <= R[i]; ++j) { add(p[j], 1); pre[j] = x += ask(n)-ask(p[j]); }
      d[i][i] = x;
      for(j = L[i]; j <= R[i]; ++j) { add(p[j], -1); suf[j] = x; x -= ask(p[j]); }
   }
   std::sort(b2+1, b2+n+1);
   for(i = 1; i <= N; ++i)
   {
      for(j = 1, pos = L[i]; j <= n; ++j)
      {
         while(pos <= R[i] && b21[pos] < j) ++pos;
         const int id = b2[j].pos;
         if(id < L[i]) f[i][id] += pos-L[i];
         else if(id > R[i]) f[i][id] += R[i]+1-pos-(pos<=R[i]&&b21[pos]==j);
      }
   }
   for(i = 1; i <= N; ++i)
      for(j = 2; j <= n; j += 8)
      {
         f[i][j] += f[i][j-1];
         f[i][j+1] += f[i][j];
         f[i][j+2] += f[i][j+1];
         f[i][j+3] += f[i][j+2];
         f[i][j+4] += f[i][j+3];
         f[i][j+5] += f[i][j+4];
         f[i][j+6] += f[i][j+5];
         f[i][j+7] += f[i][j+6];
      }
   for(int len = 1; len < N; ++len)
      for(i = 1; i+len <= N; i += 8)
      {
         j = i+len; d[i][j] = d[i][j-1]+d[i+1][j]-d[i+1][j-1]+f[j][R[i]]-f[j][L[i]-1];
         d[i+1][j+1] = d[i+1][j  ]+d[i+2][j+1]-d[i+2][j  ]+f[j+1][R[i+1]]-f[j+1][L[i+1]-1];
         d[i+2][j+2] = d[i+2][j+1]+d[i+3][j+2]-d[i+3][j+1]+f[j+2][R[i+2]]-f[j+2][L[i+2]-1];
         d[i+3][j+3] = d[i+3][j+2]+d[i+4][j+3]-d[i+4][j+2]+f[j+3][R[i+3]]-f[j+3][L[i+3]-1];
         d[i+4][j+4] = d[i+4][j+3]+d[i+5][j+4]-d[i+5][j+3]+f[j+4][R[i+4]]-f[j+4][L[i+4]-1];
         d[i+5][j+5] = d[i+5][j+4]+d[i+6][j+5]-d[i+6][j+4]+f[j+5][R[i+5]]-f[j+5][L[i+5]-1];
         d[i+6][j+6] = d[i+6][j+5]+d[i+7][j+6]-d[i+7][j+5]+f[j+6][R[i+6]]-f[j+6][L[i+6]-1];
         d[i+7][j+7] = d[i+7][j+6]+d[i+8][j+7]-d[i+8][j+6]+f[j+7][R[i+7]]-f[j+7][L[i+7]-1];
      }
}
int t1[100011], t2[100011], cnt1, cnt2;
inline int merg(int *a, int n, int *b, int m)
{
   int p = 0, q = 0, ans = 0;
   while(q < m)
   {
      while(p < n && a[p] < b[q]) ++p;
      ans += n-p;
      ++q;
      if(p == n) break;
   }
   return ans;
}
ll query(const int l, const int r)
{
   const int x = bel[l], y = bel[r];
   if(x == y)
   {
      cnt1 = cnt2 = 0;
      for(i = L[x]; i <= R[x]; i += 8)
      {
         b22[i]<l&&(t1[++cnt1]=b21[i])||(b22[i]<=r&&(t2[++cnt2]=b21[i]));
         i+1<=R[x]&&(b22[i+1]<l&&(t1[++cnt1]=b21[i+1])||(b22[i+1]<=r&&(t2[++cnt2]=b21[i+1])));
         i+2<=R[x]&&(b22[i+2]<l&&(t1[++cnt1]=b21[i+2])||(b22[i+2]<=r&&(t2[++cnt2]=b21[i+2])));
         i+3<=R[x]&&(b22[i+3]<l&&(t1[++cnt1]=b21[i+3])||(b22[i+3]<=r&&(t2[++cnt2]=b21[i+3])));
         i+4<=R[x]&&(b22[i+4]<l&&(t1[++cnt1]=b21[i+4])||(b22[i+4]<=r&&(t2[++cnt2]=b21[i+4])));
         i+5<=R[x]&&(b22[i+5]<l&&(t1[++cnt1]=b21[i+5])||(b22[i+5]<=r&&(t2[++cnt2]=b21[i+5])));
         i+6<=R[x]&&(b22[i+6]<l&&(t1[++cnt1]=b21[i+6])||(b22[i+6]<=r&&(t2[++cnt2]=b21[i+6])));
         i+7<=R[x]&&(b22[i+7]<l&&(t1[++cnt1]=b21[i+7])||(b22[i+7]<=r&&(t2[++cnt2]=b21[i+7])));
      }
      return pre[r]-(l==L[x]?0:pre[l-1])-merg(t1+1, cnt1, t2+1, cnt2);
   }
   long long ans = suf[l]+pre[r]+d[x+1][y-1];
   for(i = x+1; i < y; i += 8)
   {
      i < y && (ans += f[i][r]-f[i][L[y]-1]+f[i][R[x]]-f[i][l-1]);
      i+1 < y && (ans += f[i+1][r]-f[i+1][L[y]-1]+f[i+1][R[x]]-f[i+1][l-1]);
      i+2 < y && (ans += f[i+2][r]-f[i+2][L[y]-1]+f[i+2][R[x]]-f[i+2][l-1]);
      i+3 < y && (ans += f[i+3][r]-f[i+3][L[y]-1]+f[i+3][R[x]]-f[i+3][l-1]);
      i+4 < y && (ans += f[i+4][r]-f[i+4][L[y]-1]+f[i+4][R[x]]-f[i+4][l-1]);
      i+5 < y && (ans += f[i+5][r]-f[i+5][L[y]-1]+f[i+5][R[x]]-f[i+5][l-1]);
      i+6 < y && (ans += f[i+6][r]-f[i+6][L[y]-1]+f[i+6][R[x]]-f[i+6][l-1]);
      i+7 < y && (ans += f[i+7][r]-f[i+7][L[y]-1]+f[i+7][R[x]]-f[i+7][l-1]);
   }
   cnt1 = cnt2 = 0;
   for(i = L[x]; i <= R[x]; i += 8)
   {
      b22[i] >= l && (t1[++cnt1] = b21[i]);
      i+1 <= R[x] && b22[i+1] >= l && (t1[++cnt1] = b21[i+1]);
      i+2 <= R[x] && b22[i+2] >= l && (t1[++cnt1] = b21[i+2]);
      i+3 <= R[x] && b22[i+3] >= l && (t1[++cnt1] = b21[i+3]);
      i+4 <= R[x] && b22[i+4] >= l && (t1[++cnt1] = b21[i+4]);
      i+5 <= R[x] && b22[i+5] >= l && (t1[++cnt1] = b21[i+5]);
      i+6 <= R[x] && b22[i+6] >= l && (t1[++cnt1] = b21[i+6]);
      i+7 <= R[x] && b22[i+7] >= l && (t1[++cnt1] = b21[i+7]);
   }
   for(i = L[y]; i <= R[y]; i += 8)
   {
      b22[i] <= r && (t2[++cnt2] = b21[i]);
      i+1 <= R[y] && b22[i+1] <= r && (t2[++cnt2] = b21[i+1]);
      i+2 <= R[y] && b22[i+2] <= r && (t2[++cnt2] = b21[i+2]);
      i+3 <= R[y] && b22[i+3] <= r && (t2[++cnt2] = b21[i+3]);
      i+4 <= R[y] && b22[i+4] <= r && (t2[++cnt2] = b21[i+4]);
      i+5 <= R[y] && b22[i+5] <= r && (t2[++cnt2] = b21[i+5]);
      i+6 <= R[y] && b22[i+6] <= r && (t2[++cnt2] = b21[i+6]);
      i+7 <= R[y] && b22[i+7] <= r && (t2[++cnt2] = b21[i+7]);
   }
   return ans+merg(t1+1, cnt1, t2+1, cnt2);
}
signed main()
{
   int m; ll lastans = 0; rd(n); rd(m);
   for(int i = 1; i <= n; ++i)
      rd(p[i]);
   init();
   while(m--)
   {
      ll l, r; rd(l); rd(r);
      l ^= lastans; r ^= lastans;
      pt(lastans = query(l, r)); EOL;
   }
   END;
}