Description

我早已习惯你不在身边，

人间四月天 寂寞断了弦。

回望身后蓝天，

跟再见说再见……

某天,蒟蒻Autumn发现了从 Gty的妹子树上掉落下来了许多妹子,他发现

她们排成了一个序列,每个妹子有一个美丽度。

Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间\([l,r]\)中妹子们美丽度的逆序对数吗?"

蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线。"

请你帮助一下Autumn吧。

给定一个正整数序列\(a\),对于每次询问,输出\(a_{l}...a_{r}\)中的逆序对数,强制在线。

Input

第一行包括一个整数\(n(1 \le n \le 50000)\),表示数列\(a\)中的元素数。

第二行包括\(n\)个整数\(a_{1}...a_{n}\)(\(a_{i}>0\),保证\(a_{i}\)在\(int\)内)。

接下来一行包括一个整数\(m(1 \le m \le 50000)\),表示询问的个数。

接下来m行,每行包括\(2\)个整数\(l,r(1 \le l \le r \le n)\),表示询问\(a_{l}...a_{r}\)中的逆序

对数(若\(a_{i}>a_{j}\)且\(a_{i}<a_{j}\),则为一个逆序对)。

\(l,r\)要分别异或上一次询问的答案\((lastans)\),最开始时\(lastans=0\)。

保证涉及的所有数在\(int\)内。

Output

对每个询问,单独输出一行,表示\(a_{l}...a_{r}\)中的逆序对数。

Sample Input

4

1 4 2 3

1

2 4

Sample Output

2

一道很典型的分块题目。

首先将序列离散化，之后分块记录这些值：\(have[i][j]\)表示第\(i\)个块中小于等于\(j\)的元素个数；\(rev[i]\)表示第\(i\)个块的逆序对个数；\(ref2[i][j]\)表示\(i\)块与下标小于等于\(j\)的序列元素构成的逆序对数(\(A_{j}\)不在第\(i\)块内)；\(ref3[i][j]\)第\(i\)块与前\(j\)块所构成逆序对数目。（预处理在\(O(n\sqrt{n})\)的时间内完成）

询问的话，块与块之间的我们可以用\(ref3\)在\(O(\sqrt{n})\)的时间内算出，块与散部可以用\(ref2\)在\(O(\sqrt{n})\)的时间内算出。散与散的只能用树状数组暴力求解，在\(O(\sqrt{n}logn)\)的时间内算出结果。

综上，本题时间复杂度\(O(n\sqrt{n}+m\sqrt{n}logn)\)，空间复杂度\(O(n\sqrt{n})\)。有不理解的参考代码。

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

using namespace std;

#define maxn 50010

const int len = 230;

int n,m,ans,A[maxn],bac[maxn],have[len][maxn];

int rev[maxn],tree[maxn],ref2[len][maxn],ref3[len][len],tot;

inline int begin(int ord) { return (ord-1)*len+1; }

inline int end(int ord) { return min(ord*len,n); }

inline int belong(int ord) { return (ord+len-1)/len; }

inline int size(int ord) { return end(ord)-begin(ord)+1; }

inline int lowbit(int x) { return x & -x; }

inline void ins(int x,int y) { for (;x <= n;x += lowbit(x)) tree[x] += y; }

inline int calc(int x) { int ret = 0; for (;x;x -= lowbit(x)) ret += tree[x]; return ret; }

inline void ready()

{

	for (int i = 1;i <= n;++i) bac[i] = A[i];

	sort(bac+1,bac+n+1); tot = unique(bac+1,bac+n+1)-bac-1;

	for (int i = 1;i <= n;++i) A[i] = lower_bound(bac+1,bac+tot+1,A[i])-bac;

	tot = (n + len-1)/len;

	for (int i = 1;i <= tot;++i)

	{

		int l = begin(i),r = end(i);

		for (int j = l;j <= r;++j) have[i][A[j]]++;

		for (int j = 1;j <= n;++j) have[i][j] += have[i][j-1];

		for (int j = l;j <= r;++j) for (int k = j+1;k <= r;++k) rev[i] += A[j] > A[k];

	}

	for (int i = 1;i <= tot;++i)

	{

		int l = begin(i),r = end(i);

		for (int j = 1;j < l;++j)

			ref2[i][j] += ref2[i][j-1],ref2[i][j] += have[i][A[j]-1];

		for (int j = r+1;j <= n;++j)

			ref2[i][j] += ref2[i][j-1],ref2[i][j] += size(i)-have[i][A[j]];

	}

	for (int i = 1;i <= n;++i)

	{

		int now = belong(i);

		for (int j = 1;j < now;++j)

			ref3[now][j] += size(j)-have[j][A[i]];

	}

	for (int i = 1;i <= tot;++i)

		for (int j = 2;j < i;++j)

			ref3[i][j] += ref3[i][j-1];

}

inline int work(int l,int r)

{

	int tot = 0,L = belong(l),R = belong(r),p = end(L),q = begin(R);

	for (int i = L+1;i < R;++i)

	{

		tot += rev[i];

		tot += ref3[i][i-1] - ref3[i][L];

		tot += ref2[i][p]-ref2[i][l-1];

		tot += ref2[i][r]-ref2[i][q-1];

	}

	if (L != R)

	{

		for (int i = r;i >= q;--i) tot += calc(A[i]-1),ins(A[i],1);

		for (int i = p;i >= l;--i) tot += calc(A[i]-1),ins(A[i],1);

		for (int i = r;i >= q;--i) ins(A[i],-1);

		for (int i = p;i >= l;--i) ins(A[i],-1);

	}

	else

	{

		for (int i = r;i >= l;--i) tot += calc(A[i]-1),ins(A[i],1);

		for (int i = r;i >= l;--i) ins(A[i],-1);

	}

	return tot;

}

int main()

{

	freopen("3744.in","r",stdin);

	freopen("3744.out","w",stdout);

	scanf("%d",&n);

	for (int i = 1;i <= n;++i) scanf("%d",A+i);

	ready();

	scanf("%d",&m);

	for (int i = 1;i <= m;++i)

	{

		int l,r; scanf("%d %d",&l,&r);

		l ^= ans; r ^= ans;

		printf("%d\n",ans = work(l,r));

	}

	fclose(stdin); fclose(stdout);

	return 0;

}