bzoj 3744 Gty的妹子序列 区间逆序对数(在线) 分块

题意

给定(n)个数，(q)个询问，每次询问([l,r])区间内的逆序对数。

强制在线。

离线的话就如上一题bzoj 3289 Mato的文件管理，可以直接用 莫队 搞，在线的话怎么办呢？

分块大法好。

1

预处理出两个信息：

1. (f[i][j])：从 第(i)块开始位置 到 位置(j) 这段区间的逆序对数
2. (s[i][j])：前(i)块中(\leq j)的数字总数

2

有了这两个信息之后怎么用呢？

考虑一个询问([l,r])，

首先，如果左右端点在同一段内，直接暴力即可，

否则，将其拆成三段看待：

————————————————-

| ① |	    	②		         	|	③		|

l	l所在块的右端点              	r所在块的左端点   r

如上图，

逆序对数=

①中的逆序对数+②中的逆序对数+③中的逆序对数+

①与②间的逆序对数+①与③间的逆序对数+②与③间的逆序对数

根据上面预处理出的信息(f)，

即能直接得到（②+③）一整段的逆序对数，

即②中的逆序对数+③中的逆序对数+②与③间的逆序对数，

复杂度(O(1))

因此，另外要求的就是，

①中的逆序对数+①与②间的逆序对数+①与③间的逆序对数

其中，

①中的逆序对数 及 ①与③间的逆序对数 可以直接树状数组暴力算，

(\sqrt n)次插入，(2*\sqrt n)次查询，复杂度(O(\sqrt n*logn))

①与②间的逆序对数 则需枚举①中的每个数，然后用预处理出的另一个信息(s)，

复杂度(O(\sqrt n1))

(f[i][j])：从 第(i)块开始位置 到 位置(j) 这段区间的逆序对数

对每一块做一次树状数组，复杂度：(2(\sqrt n+2\sqrt n+\cdots+n)*logn=O(n\sqrt nlogn))

(s[i][j])：前(i)块中(\leq j)的数字总数

算每一块时，充分利用前缀和思想，先算第(i)块中(= j)的数字总数，再算第(i)块中(\leq j)的数字总数，最后算前(i)块中(\leq j)的数字总数，复杂度：(O(n\sqrt n))

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); –i)

#define dF2(i, a, b) for (int i = (a); i >= (b); –i)

#define maxn 50010

#define maxb 310

using namespace std;

typedef long long LL;

int a[maxn], mp[maxn], c[maxn], cnt[maxb][maxn], bl[maxn];

int n, m, nn, num, blo;

struct node { int l, r; }b[maxb];

int f[maxb][maxn];

inline int read(){


char c=getchar();int x=0,f=1;<br/>
while(c&lt;&#39;0&#39;||c&gt;&#39;9&#39;){if(c==&#39;-&#39;)f=-1; c=getchar();}<br/>
while(c&gt;=&#39;0&#39;&amp;&amp;c&lt;=&#39;9&#39;){x=x*10+c-&#39;0&#39;; c=getchar();}<br/>
return x*f;<br/>


}

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

inline int query(int x) { int ret=0; while (x) ret += c[x], x-=lowbit(x); return ret; }

inline void add(int x, int v) { while (x&lt;=nn) c[x] += v, x+=lowbit(x); }

void init(int s) {


b[s].l=s*blo, b[s].r=(s==num-1?n:b[s].l+blo);<br/>
memset(c, 0, sizeof c);<br/>
F(i, b[s].l, n) {<br/>
    f[s][i] = f[s][i-1] + i-b[s].l-query(a[i]);<br/>
    add(a[i], 1);<br/>
}<br/>
F(i, b[s].l, b[s].r) ++cnt[s][a[i]];<br/>
F2(i, 1, nn) cnt[s][i] += cnt[s][i-1];<br/>
F2(i, 1, nn) cnt[s][i] += cnt[s-1][i];<br/>


}

int ask(int l, int r) {


int ret=0;<br/>
if (bl[l]==bl[r]) {<br/>
    memset(c, 0, sizeof c);<br/>
    F2(i, l, r) {<br/>
        ret += i-l-query(a[i]);<br/>
        add(a[i], 1);<br/>
    }<br/>
}<br/>
else {<br/>
    ret += f[bl[l]+1][r];<br/>
    memset(c, 0, sizeof c);<br/>
    F(i, l, b[bl[l]].r) {<br/>
        ret += i-l-query(a[i]);<br/>
        add(a[i], 1);<br/>
        ret += cnt[bl[r]-1][a[i]-1]-cnt[bl[l]][a[i]-1];<br/>
    }<br/>
    int ex=b[bl[l]].r-l;<br/>
    F2(i, b[bl[r]].l, r) ret += ex-query(a[i]);<br/>
}<br/>
return ret;<br/>


}

int main() {


scanf(&#34;%d&#34;, &amp;n); blo = sqrt(n);<br/>
F(i, 0, n) a[i]=mp[i]=read(), bl[i]=i/blo;<br/>
sort(mp, mp+n);<br/>
nn = unique(mp, mp+n)-mp;<br/>
F(i, 0, n) a[i] = lower_bound(mp, mp+nn, a[i])-mp+1;<br/>
num = bl[n-1]+1;<br/>
F(i, 0, num) init(i);<br/>
int lastans=0;<br/>
scanf(&#34;%d&#34;, &amp;m);<br/>
F(i, 0, m) {<br/>
    int l=read(),r=read();<br/>
    l^=lastans, r^=lastans;<br/>
    --l, --r; if (l&gt;r) swap(l, r);<br/>
    if (l&lt;0||r&gt;=n) continue;<br/>
    printf(&#34;%d\n&#34;, lastans=ask(l,r));<br/>
}<br/>
return 0;<br/>


}