树状数组打错了还有救吗？

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct BIT
{
	int c[N],n;
	void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
	int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
}tr;
int a[N],b[N],blen,ans[N],n,m,B,sum,len;
struct node{int l,r,id;}q[N];
bool cmp(node n1,node n2){return n1.l/B!=n2.l/B?n1.l<n2.l:(n1.l/B)&1?n1.r<n2.r:n1.r>n2.r;}
void add(int x,int op)
{
	int s=op?tr.get(x-1):len-tr.get(x);
	len++,sum+=s;tr.add(x,1);
}
void del(int x,int op)
{
	int s=op?tr.get(x-1):len-tr.get(x);
	len--,sum-=s;tr.add(x,-1);
}
signed main()
{
	cin>>n>>m;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);blen=unique(b+1,b+n+1)-b-1;tr.n=blen;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+blen+1,a[i])-b;
	for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l],1);
		while(r<q[i].r)add(a[++r],0);
		while(l<q[i].l)del(a[l++],1);
		while(r>q[i].r)del(a[r--],0);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

题意:

给一个长度为n的a序列

进行m次查询，每次查询一个区间

求区间逆序对数

$1<=n,m<=100000$

$a[i]$ 在 $int$ 范围内

---

解法

这个题怎么做呢

首先肯定要离散化的啦

然后我们用莫队+树状数组做

莫队的思想就是对询问排序、分块

保持询问左端点在 $\sqrt N$ 的块长里反复横跳，右端点单调向外拉

用奇偶块还可以减少端点移动次数(就是减少常数啦)

对于奇数块，右端点单调向外拉

对于偶数块，右端点单调往回拉

可以证明，端点移动次数约为 $N\sqrt N$

证明:

左端点在 $\sqrt N$ 的块长里反复横跳，共$n$个询问，复杂度$O(N\sqrt N)$

我们把询问分成了$\sqrt N$组，每一组的右端点都是单调移动的，最多也就移动n次，复杂度还是$O(N\sqrt N)$

嗯，一个sb证明

树状数组维护当前逆序对数即可，复杂度$O(N\sqrt NlogN)$

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
int lowbit(int x){return x&-x;}
int n,m,a[N],p[N];bool cmp(int x,int y){return a[x]<a[y];}
int c[N],size=0;
void add(int x,int k){for(size+=k;x<=n;x+=lowbit(x))c[x]+=k;}
int getsum(int x){int ans=0;for(;x;x-=lowbit(x))ans+=c[x];return ans;}
struct ASK
{
	int l,r,p;
}ask[N];const int block=300;
bool mmp(ASK n1,ASK n2)
{
	if(n1.l/block!=n2.l/block)return n1.l<n2.l;
	if((n1.l/block)&1)return n2.r<n1.r;
	return n1.r<n2.r;
}
ll ans[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		p[i]=i;
	}
	sort(p+1,p+n+1,cmp);
	int tmp=a[p[1]];a[p[1]]=1;
	for(int i=2,t=1;i<=n;i++)
	{
		if(a[p[i]]!=tmp)t++;
		tmp=a[p[i]];a[p[i]]=t;
	}//离散化 
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&ask[i].l,&ask[i].r);
		ask[i].p=i;
	}
	sort(ask+1,ask+m+1,mmp);//莫队排序 
	
	int l=ask[1].l,r=ask[1].l-1;ll sum=0;
	for(int i=1;i<=m;i++)
	{
		int ql=ask[i].l,qr=ask[i].r;
		while(r<qr){r++;sum+=size-getsum(a[r]);add(a[r],1);}
		while(l>ql){l--;sum+=getsum(a[l]-1);add(a[l],1);}
		while(r>qr){add(a[r],-1);sum-=size-getsum(a[r]);r--;}
		while(l<ql){add(a[l],-1);sum-=getsum(a[l]-1);l++;}
		ans[ask[i].p]=sum;
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

但是对于$10w$的数据，上面的代码会T飞的

仔细梳理思路，你会发现，我们只有$n$个数，平均询问复杂度却达到了$O(\sqrt NlogN)$

我们需要一种花里胡哨的操作，大力暴拆，手撕复杂度，达到一个均摊的目的

我们先来诱导♂ 一下

如果你能够在低于$O(\sqrt N)$的时间内知道莫队端点移动后$sum$的变化值，你是不是很开心啊

假设我把变化的量丢进一个数组里，你是不是搞个前缀和就可以搞出来所有的答案啊

然后你发现怎么也搞不出来 (笑容逐渐凝固)

冷静，我们引入lxl的黑科技——莫队二次离线，实质是莫队(莫队本身是离线算法)+离线莫队的移动

操作如下:

我们以莫队的右端点移动为例，假设此时的区间为 $[l,r]$，你要移到 $[l,r+1]$

那么产生的贡献为 $a[r+1]$ 和 $a[l$~$r]$ 产生的逆序对数

强上树状数组就是$O(logN)$的复杂度，那就达不到我们的目的

我们差分这个值，设$f(l,r,r+1)$为 $a[r+1]$ 和区间 $l$~$r$ 产生的逆序对数

则这个值为 $f(1,r,r+1)-f(1,l-1,r+1)$

前面这个可以用一个$R$ 数组$O(NlogN)$预处理出来，就是一个裸的树状数组逆序对，然后可以$O(1)$解决

后面这个不能预处理，我们将二元组$(r+1,i)$丢进vetcor数组$v[l-1]$里，其中$i$表示这个值贡献去的位置

因为右端点移动了$N\sqrt N$次，所以vector里丢进了$N\sqrt N$个二元组

然后，从$1$到$n$，像逆序对一样构建树状数组

假设你 $for$ 到 $i$ ，你就可以把vector数组——$v[i]$里面的所有二元组提出来

我们来明确目的：$v[i]$里面的二元组$(j,p)$，是你当年搞不出来$f(1,l-1,r+1)$才丢进去的

现在你造好了$1$~$l-1$的树状数组，你就可以查一遍大于$a[j]$的数量，然后通过$p$将贡献传向第$p$个莫队转移

还记得vector里丢进了$N\sqrt N$个二元组吗

所以上面几行的"查"操作总复杂度还是$O(N\sqrt NlogN)$

怎么优化呢？

你发现，树状数组查的次数远大于修改次数(修改次数为$O(NlogN)$)

我们使用值域分块搞定——支持$O(\sqrt N)$单次修改，$O(1)$查询

一共$N$个数，修改$O(N\sqrt N)$，$N\sqrt N$个查询，查询$O(N\sqrt N)$

对，搞完了

弄完了？对！结束了！！！

个屁啊！！！

还有个优化，vector里不是丢进了$N\sqrt N$个二元组吗

其实是$N$个询问弄出来的，对于每个询问，右端点移动时，左端点固定，

$f(1,l-1,r+1$ ~ $r')$ 可以变成一个三元组压进$v[l-1]$里，提出来时$for$一波就好

这样空间复杂度就变成$O(N)$的了

考虑完右端点的移动，再搞左端点(操作类似)

搞完这些东西，求一遍前缀和，就搞出所有答案，通过排序前的 $p$ 弄回去再输出就行

为什么是前缀和，因为你搞出来的是相较上次的变化量啊

打代码的时候注意比较普通的莫队，注意一下正负，细节有点多

代码？

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m;ll a[N];
inline int lowbit(int x){return x&-x;}
ll c[N],size=0;
int p[N];bool cmp(int x,int y){return a[x]<a[y];}
inline void add(int x,ll k){size+=k;for(;x<=n;x+=lowbit(x))c[x]+=k;}
inline ll getsum(int x){ll ans=0;for(;x;x-=lowbit(x))ans+=c[x];return ans;}
ll L[N],R[N];//L[i]:1~i-1有多少个数大于a[i];R[i]:i+1~n有多少个数小于a[i] 

const int block=250;
struct ASK
{
	int l,r,p;
}ask[N];
inline bool mmp(ASK n1,ASK n2)
{
	if(n1.l/block!=n2.l/block)return n1.l<n2.l;
	if((n1.l/block)&1)return n2.r<n1.r;
	return n1.r<n2.r;
}
struct node{int l,r,p,op;};
vector<node>ls[N],rs[N];
int B,bl[N/block+5],br[N/block+5],w[N];
int s[N/block+5],C[N];

ll ret[N],ans[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		p[i]=i;
	}
	sort(p+1,p+n+1,cmp);
	ll tmp=a[p[1]];a[p[1]]=1;
	for(int i=2,t=1;i<=n;i++)
	{
		if(a[p[i]]!=tmp)t++;
		tmp=a[p[i]];a[p[i]]=t;
	}//离散化 
	
	for(int i=1;i<=n;i++)
	{
		L[i]=L[i-1]+size-getsum(a[i]);
		add(a[i],1);//L[i]转前缀和 
	}//for(int i=1;i<=n;i++)printf("%lld ",L[i]);puts("");
	memset(c,0,sizeof(c));
	for(int i=n;i>=1;i--)
	{
		R[i]=R[i+1]+getsum(a[i]-1);
		add(a[i],1);//R[i]转后缀和 
	}//for(int i=1;i<=n;i++)printf("%lld ",R[i]);puts("");
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&ask[i].l,&ask[i].r);
		if(ask[i].l>ask[i].r)swap(ask[i].l,ask[i].r);
		ask[i].p=i;
	}
	sort(ask+1,ask+m+1,mmp);//排序 
	ask[0]=(ASK){1,0,0};
	for(int i=1;i<=m;i++)//莫队二次离线 
	{//把莫队的移动离线下来 
		ret[i]=L[ask[i].r]-L[ask[i-1].r]+R[ask[i].l]-R[ask[i-1].l];
			 if(ask[i].r>ask[i-1].r)rs[ask[i-1].l-1].push_back((node){ask[i-1].r+1,ask[i].r,i,-1});
		else if(ask[i].r<ask[i-1].r)rs[ask[i-1].l-1].push_back((node){ask[i].r+1,ask[i-1].r,i, 1});
			 if(ask[i].l<ask[i-1].l)ls[ask[i  ].r+1].push_back((node){ask[i].l,ask[i-1].l-1,i,-1});
		else if(ask[i].l>ask[i-1].l)ls[ask[i  ].r+1].push_back((node){ask[i-1].l,ask[i].l-1,i, 1});
	}
	
	B=(n-1)/block+1;
	for(int i=1;i<=B;i++) 
	{
		bl[i]=br[i-1]+1;
		br[i]=br[i-1]+block;
	}br[B]=n;//值域分块 
	for(int i=1;i<=B;i++)for(int j=bl[i];j<=br[i];j++)w[j]=i;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<w[a[i]];j++)s[j]++;
		for(int j=bl[w[a[i]]];j<=a[i];j++)C[j]++;
		for(int j=0;j<rs[i].size();j++)
		{
			node t=rs[i][j];
			int l=t.l,r=t.r;
			tmp=0;
			for(int k=l;k<=r;k++)tmp+=s[w[a[k]+1]]+C[a[k]+1];
			ret[t.p]+=t.op*tmp;
		}
	}
	memset(C,0,sizeof(C));
	memset(s,0,sizeof(s));
	for(int i=n;i>=1;i--)
	{
		for(int j=w[a[i]]+1;j<=B;j++)s[j]++;
		for(int j=a[i];j<=br[w[a[i]]];j++)C[j]++;
		for(int j=0;j<ls[i].size();j++)
		{
			node t=ls[i][j];
			int l=t.l,r=t.r;
			tmp=0;
			for(int k=l;k<=r;k++)tmp+=s[w[a[k]-1]]+C[a[k]-1];
			ret[t.p]+=t.op*tmp;
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		ret[i]+=ret[i-1];//ret最终的值是差分值 
		ans[ask[i].p]=ret[i];
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}