【bzoj3744】Gty的妹子序列

【bzoj3744】Gty的妹子序列

题目链接

hhhhhhhhhhhhhhhh

凭借着 O(nn−−√) O ( n n ) $O (n sqrt{n})$的做法，成功卡到了 rank7 r a n k 7 $rank7$（然而小号 rank6 r a n k 6 $rank6$

那我们来讲一讲怎么 n−−√ n $sqrt{n}$吧

首先分块是很明显的

我们先假设询问都是整块整块询问的（即不会有一个块被左端点或右端点分成两半的情况）
那么答案你可以这样去考虑：分成跨越块的和没跨越块的

后者好维护，前者我们可以记一个 ans[i][j] a n s [ i ] [ j ] $ans[i][j]$数组，表示原序列中第 j j $j$个元素到第i" role="presentation" style="position: relative;">ii$i$个块的左端点之前这一段区间的元素与第 i i $i$个块内的元素的逆序对数

然后询问的时候累加就可以了

那如果询问不是整块的情况呢？

我们先加上整块算出来的答案（就是上面的情况），然后再考虑加上一些东西
我们设左边破碎的块为L" role="presentation" style="position: relative;">LL$L$，右边破碎的块为 R R $R$
那我们的答案肯定还要加上L" role="presentation" style="position: relative;">LL$L$与中间的块产生的逆序对数、 R R $R$与中间的块产生的逆序对数以及L" role="presentation" style="position: relative;">LL$L$与 R R $R$产生的逆序对数

前者可以和整块的情况一起算（就是直接∑ans[i][l]" role="presentation" style="position: relative;">∑ans[i][l]∑ans[i][l]$sum{ans[i][l]}$）

中间的答案我们可以考虑每个块的 ans[i][j] a n s [ i ] [ j ] $ans[i][j]$，当 j≥i j ≥ i $j geq i$这个块的右端点时，再多记一下第 j j $j$个元素到第i" role="presentation" style="position: relative;">ii$i$个块的右端点之间这一段区间的元素与第 i i $i$个块内的元素的逆序对数（也就是整块情况的对称问题），然后就可以轻松搞定

最后一部分我们可以先把每一段都给排序好，然后算的时候把L" role="presentation" style="position: relative;">LL$L$和 R R $R$整段给提出来，像归并排序那样做就好了

细节可能有点多，有些处理具体看代码吧

Ps." role="presentation" style="position: relative;">Ps.Ps.$Ps.$这种做法可能会MLE，我块大小开到 250 250 $250$就过了

代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<cstring>
#include<cmath>
using namespace std;typedef long long LL;const int INF = 2147483647;
const int maxn = 50010;
const int maxb = 250;int n,m,now,len,tot,R[maxb],L[maxb];
int A[maxn],B[maxn],cnt[maxn];
int a[maxn],b[maxn],data[maxn],ha[maxn],N;
int Cnt[maxb][maxb],ans[maxb][maxb][maxb],Ans[maxb][maxn];inline LL getint()
{LL ret = 0,f = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') ret = ret * 10 + c - '0',c = getchar();return ret * f;
}inline int cmp(int x,int y)
{return a[x] < a[y];
}inline int Query(int bl,int br,int l,int r)
{int ret = 0;for (int i = bl; i <= br; i++)ret += ans[i][1][R[i] - L[i] + 1] + Ans[i][l] + Ans[i][r] - Ans[i][R[br]];return ret;
}inline int Merge(int bl,int br,int l,int r)
{int p = 0,q = 0;for (int i = L[bl]; i <= R[bl]; i++)if (b[i] >= l) A[++p] = a[b[i]];for (int i = L[br]; i <= R[br]; i++)if (b[i] <= r) B[++q] = a[b[i]];int i = 1,j = 1,ret = 0;while (i <= p && j <= q){if (A[i] > B[j]) j++;else ++i , ret += j - 1;}while (i <= p) ret += q , i++;return ret;
}int main()
{#ifdef AMCfreopen(&#","r",stdin);freopen(&#","w",stdout);#endifn = getint();len = sqrt(n); tot = ceil(n * 1.0 / len);for (int i = 1; i <= n; i++) data[i] = a[i] = getint();sort(data + 1,data + n + 1);for (int i = 1; i <= n; i++)if (i == 1 || data[i] != data[i - 1])ha[++N] = data[i];for (int i = 1; i <= n; i++)a[i] = lower_bound(ha + 1,ha + N + 1,a[i]) - ha;for (int i = 1; i <= tot; i++)L[i] = (i - 1) * len + 1,R[i] = min(n,i * len);for (int i = 1; i <= tot; i++){for (int j = 0; j <= N; j++) cnt[j] = 0;for (int j = L[i]; j <= R[i]; j++) cnt[a[j]]++;for (int j = 1; j <= N; j++) cnt[j] += cnt[j - 1];for (int j = L[i] - 1; j >= 1; j--) Ans[i][j] = Ans[i][j + 1] + cnt[a[j] - 1];for (int j = 0; j <= N; j++) cnt[j] = 0;for (int j = L[i]; j <= R[i]; j++) cnt[a[j]]++;for (int j = N - 1; j >= 0; j--) cnt[j] += cnt[j + 1];for (int j = R[i] + 1; j <= n; j++) Ans[i][j] = Ans[i][j - 1] + cnt[a[j] + 1];for (int i = 1; i <= R[i] - L[i] + 1; i++)for (int j = 1; j <= R[i] - L[i] + 1; j++)Cnt[i][j] = 0;for (int j = L[i]; j <= R[i]; j++)for (int k = j + 1; k <= R[i]; k++)if (a[j] > a[k]){int J = j - L[i] + 1,K = k - L[i] + 1;Cnt[J][K]++; Cnt[K][J]++;}for (int j = 1; j <= R[i] - L[i] + 1; j++)for (int k = 1; k <= R[i] - L[i] + 1; k++)Cnt[j][k] += Cnt[j][k - 1];for (int j = 1; j <= R[i] - L[i] + 1; j++)for (int k = j + 1; k <= R[i] - L[i] + 1; k++)ans[i][j][k] = ans[i][j][k - 1] + Cnt[k][k - 1] - Cnt[k][j - 1];}for (int i = 1; i <= n; i++) b[i] = i;for (int i = 1; i <= tot; i++) sort(b + L[i],b + R[i] + 1,cmp);m = getint();for (int i = 1; i <= m; i++){int l = getint() ^ now,r = getint() ^ now;int bl = ceil(1.0 * l / len),br = ceil(1.0 * r / len);now = 0;if (bl == br) now += ans[bl][l - L[bl] + 1][r - L[bl] + 1];else {now += ans[bl][l - L[bl] + 1][R[bl] - L[bl] + 1] + ans[br][1][r - L[br] + 1];if (bl + 1 <= br - 1) now += Query(bl + 1,br - 1,l,r);now += Merge(bl,br,l,r);}printf("%dn",now);}return 0;
}