【BZOJ3744】Gty的妹子序列
Description
我早已习惯你不在身边，
人间四月天 寂寞断了弦。
回望身后蓝天，
跟再见说再见……
某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现
她们排成了一个序列,每个妹子有一个美丽度。
Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间[l,r]中妹子们美丽度的逆序对数吗?"
蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线。"
请你帮助一下Autumn吧。
给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。
Input
第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
第二行包括n个整数a1...an(ai>0,保证ai在int内)。
接下来一行包括一个整数m(1<=m<=50000),表示询问的个数。
接下来m行,每行包括2个整数l、r(1<=l<=r<=n),表示询问al...ar中的逆序对数(若ai>aj且i<j,则为一个逆序对)。
l,r要分别异或上一次询问的答案(lastans),最开始时lastans=0。
保证涉及的所有数在int内。
Output
对每个询问,单独输出一行,表示al...ar中的逆序对数。
Sample Input
4
1 4 2 3
1
2 4
1 4 2 3
1
2 4
Sample Output
2
题解：网上都说要用可持久化线段树，我偏不用，哼~
我们枚举每个块的左端点i，再枚举i右面的所有j，并用树状数组处理出[i,j]中的逆序对数。这样，对于每个询问[a,b]，我们已经知道了[c*block,b]中的逆序对数。
我们不妨在倒着求一遍，枚举每个块的右端点i，再枚举i左边的所有j，并用树状数组处理出[j,i]中的逆序对数。这样，我们用[c*block,b]+[a,d*block]-[c*block,d*block]，现在[a,b]中的大部分逆序对已经被我们统计完了，就只剩一个在[a,c*block)，一个在(d*block,b]中的逆序对了。直接将一边全都再扔到树状数组里，然后用另一边去查找就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=50010;
int n,m,B,nm,now,ans;
int s[maxn],tim[maxn],s1[240][maxn],s2[240][maxn],v[maxn];
struct node
{
int val,org;
}num[maxn];
bool cmp(node a,node b)
{
return a.val<b.val;
}
void updata(int x)
{
for(int i=x;i<=nm;i+=i&-i)
{
if(tim[i]<now) tim[i]=now,s[i]=0;
s[i]++;
}
}
int query(int x)
{
int i,ret=0;
for(i=x;i;i-=i&-i)
{
if(tim[i]<now) tim[i]=now,s[i]=0;
ret+=s[i];
}
return ret;
}
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,j,a,b,c,d,pre=-1<<30;
for(i=0;i<n;i++) num[i].val=rd(),num[i].org=i;
sort(num,num+n,cmp);
B=int(sqrt(double(n)));
for(i=0;i<n;i++)
{
if(num[i].val>pre) pre=num[i].val,nm++;
v[num[i].org]=nm;
}
for(i=0;i*B<n;i++)
{
now++,a=i*B;
for(j=a;j<n;j++) s1[i][j]=(j?s1[i][j-1]:0)+j-a-query(v[j]),updata(v[j]);
}
for(i=(n-1)/B;i>=1;i--)
{
now++,b=i*B-1;
for(j=b;j>=0;j--) s2[i][j]=s2[i][j+1]+query(v[j]-1),updata(v[j]);
}
m=rd();
for(i=1;i<=m;i++)
{
a=rd()^ans,b=rd()^ans,a--,b--,ans=0;
if(a>b) swap(a,b);
c=a/B,d=b/B;
if(c==d)
{
now++;
for(j=a;j<=b;j++) ans+=j-a-query(v[j]),updata(v[j]);
printf("%d\n",ans);
continue;
}
ans=s1[c+1][b]-s1[c+1][d*B-1]+s2[d][a],now++;
for(j=d*B;j<=b;j++) updata(v[j]);
for(j=a;j<c*B+B;j++) ans+=query(v[j]-1);
printf("%d\n",ans);
}
return 0;
}