区间逆序对

2018heyuyang · 2019-10-13 20:50:13 · 个人记录

题意:

给一个长度为n的a序列

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

求区间逆序对数

证明:

左端点在 \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个询问弄出来的，对于每个询问，右端点移动时，左端点固定，