Description
Autumn终于会求区间逆序对了!Bakser神犇决定再考验一下他，他说道：
“在Gty的妹子序列里，某个妹子的美丽度可也是会变化的呢。你还能求出某个区间中妹子们美丽度的逆序对数吗？当然，为了方便，这次我们规定妹子们的美丽度在[1,n]中。仍然强制在线。”
Autumn需要你的帮助。
给定一个正整数序列a(1<=ai<=n)，支持单点修改，对于每次询问，输出al...ar中的逆序对数，强制在线。
Input
第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
第二行包括n个整数a1...an(1<=ai<=n)。
接下来一行包括一个整数m(1<=m<=50000),表示操作的个数。
接下来m行,每行包括3个整数。
0 L R (1<=L<=R<=n) 询问[L,R]中的逆序对数。
1 p v (1<=p<=n,1<=v<=n) 将p位置的数修改为v。
L,R,p,v 都需要异或上一次的答案，保证异或之后的值是合法的。
保证涉及的所有数在int内。
Output
对每个询问，单独输出一行，表示al...ar中的逆序对数。对每个询问，单独输出一行，表示al...ar中的逆序对数。
Sample Input
10
1 7 5 6 9 4 9 4 4 7
10
0 4 6
0 5 8
0 1 10
1 25 19
0 19 25
1 14 4
0 12 12
0 2 5
1 8 7
1 1 10
1 7 5 6 9 4 9 4 4 7
10
0 4 6
0 5 8
0 1 10
1 25 19
0 19 25
1 14 4
0 12 12
0 2 5
1 8 7
1 1 10
Sample Output
2
3
16
13
0
2
Solution
分块，同时维护几个数组：
$f[i]$表示第$i$块内部的逆序对个数。
$g[i][j]$表示第$i$块和第$j$块能形成的逆序对个数，第二维用树状数组维护。
$s[i][j]$表示前$i$块里$j$数出现的次数，第二维同样用树状数组维护。
查询就利用这三个数组查一下，利用好树状数组前缀和的性质。乱七八糟加加减减。
修改就维护好这三个数组就好了……
速度倒数第二$46s$低空飞过……心情简单……
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (50009)
#define S (259)
using namespace std; int n,m,opt,l,r,ans,num,f[S],a[N];
int ID[N],L[S],R[S]; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} struct BIT
{
int c[N];
void Update(int x,int v)
{
for (; x<=n; c[x]+=v,x+=(x&-x));
}
int Query(int x)
{
int ans=;
for (; x; ans+=c[x],x-=(x&-x));
return ans;
}
}B,g[S],s[S]; void Build()
{
int unit=sqrt(n);
num=n/unit+(n%unit!=);
for (int i=; i<=num; ++i)
L[i]=(i-)*unit+, R[i]=i*unit;
R[num]=n;
for (int i=; i<=num; ++i)
for (int j=L[i]; j<=R[i]; ++j) ID[j]=i;
} void Preprocess()
{
for (int i=; i<=num; ++i)
{
for (int j=L[i]; j<=R[i]; ++j)
{
f[i]+=B.Query(n)-B.Query(a[j]);
B.Update(a[j],);
}
for (int j=L[i]; j<=R[i]; ++j) B.Update(a[j],-);
}
for (int i=; i<=num; ++i)
for (int j=; j<=i-; ++j)
{
for (int k=L[j]; k<=R[j]; ++k) B.Update(a[k],);
for (int k=L[i]; k<=R[i]; ++k) g[i].Update(j,B.Query(n)-B.Query(a[k]));
for (int k=L[j]; k<=R[j]; ++k) B.Update(a[k],-);
}
for (int i=; i<=num; ++i)
for (int j=L[i]; j<=R[i]; ++j) s[i].Update(a[j],);
for (int i=; i<=num; ++i)
for (int j=; j<=n; ++j) s[i].Update(j,s[i-].Query(j)-s[i-].Query(j-));
} int Calc(int l,int r)
{
int ans=;
if (ID[l]==ID[r])
{
for (int i=l; i<=r; ++i)
{
ans+=B.Query(n)-B.Query(a[i]);
B.Update(a[i],);
}
for (int i=l; i<=r; ++i) B.Update(a[i],-);
return ans;
}
for (int i=l; i<=R[ID[l]]; ++i)
{
ans+=s[ID[r]-].Query(a[i]-)-s[ID[l]].Query(a[i]-);
ans+=B.Query(n)-B.Query(a[i]);
B.Update(a[i],);
}
for (int i=l; i<=R[ID[l]]; ++i) B.Update(a[i],-); for (int i=L[ID[r]]; i<=r; ++i)
{
ans+=(s[ID[r]-].Query(n)-s[ID[r]-].Query(a[i]))-(s[ID[l]].Query(n)-s[ID[l]].Query(a[i]));
ans+=B.Query(n)-B.Query(a[i]);
B.Update(a[i],);
}
for (int i=L[ID[r]]; i<=r; ++i) B.Update(a[i],-); for (int i=ID[l]+; i<=ID[r]-; ++i) ans+=f[i];
for (int i=ID[l]+; i<=ID[r]-; ++i)
ans+=g[i].Query(i-)-g[i].Query(ID[l]);
for (int i=l; i<=R[ID[l]]; ++i) B.Update(a[i],);
for (int i=L[ID[r]]; i<=r; ++i) ans+=B.Query(n)-B.Query(a[i]);
for (int i=l; i<=R[ID[l]]; ++i) B.Update(a[i],-);
return ans;
} void Change(int x,int k)
{
int id=ID[x];
for (int i=id; i<=num; ++i) s[i].Update(a[x],-);
for (int i=id; i<=num; ++i) s[i].Update(k,); for (int i=; i<=id-; ++i)
{
g[id].Update(i,-s[i].Query(n)+s[i].Query(a[x])+s[i-].Query(n)-s[i-].Query(a[x]));
g[id].Update(i,s[i].Query(n)-s[i].Query(k)-s[i-].Query(n)+s[i-].Query(k));
}
for (int i=id+; i<=num; ++i)
{
g[i].Update(id,-s[i].Query(a[x]-)+s[i-].Query(a[x]-));
g[i].Update(id,s[i].Query(k-)-s[i-].Query(k-));
} f[id]=; a[x]=k;
for (int i=L[id]; i<=R[id]; ++i)
{
f[id]+=B.Query(n)-B.Query(a[i]);
B.Update(a[i],);
}
for (int i=L[id]; i<=R[id]; ++i) B.Update(a[i],-);
} int main()
{
n=read();
Build();
for (int i=; i<=n; ++i) a[i]=read();
Preprocess();
m=read();
while (m--)
{
opt=read(); l=read(); r=read();
l^=ans; r^=ans;
if (opt==) printf("%d\n",ans=Calc(l,r));
else Change(l,r);
}
}