jzoj 5851.【NOIP提高组模拟2018.8.25】f 分治+折半搜索

Description

Input

Output

Data Constraint

Hint

分析：
我们考虑这样求逆序对，对于每一位进行计算。也就是求01序列的逆序对，直接记录前面1的个数即可。然后把这位是0的放左边，这位是1的放右边，分治递归下去。很明显，每一次处理的数前面的位都是相同的，而这一位已经决定了大小，后面也不可能分在一个组内。
我们考虑给某个位置异或上一个1$1$，那么这以为01取反，而前面的位置并没有改变，而且后面的分组也不会改变，只改变了当前位的答案，把逆序对变成了顺序对而已。
我们跑出每一个位的逆序对与顺序对，记为ai$a_i$和bi$b_i$，我们每次可以从中选择一个，权值为所选数的和，求第p$p$大。此时如果暴力排序以及特判p=1$p=1$的情况就可以得到65分的高分。
我们可以折半搜索。求出前k/2$k/2$个数的选法和后k/2$k/2$个数的选法，然后排序。我们考虑二分逆序对个数，每次计算有多少种选法逆序对小于等于mid$mid$，相当于选两个数和小于等于mid$mid$，只需要维护两个指针即可。
对于第二问，先算出ans1−1$ans1-1$的选法个数。因为后面的是高位，我们暴力从小到大枚举后k/2$k/2$位的选法，然后倍增求出有多少种选法使得和刚好为ans1$ans1$，跑出第p$p$大即可。

代码：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define LL long long

const LL maxn=5e5+7;
const LL maxp=30;

using namespace std;

LL n,k,p,cnt,cnt1,cnt2,ans2;
LL a[maxn],le[maxn],ri[maxn],bit[maxn];
LL x[maxp],y[maxp],ans1,s;

struct rec{
    LL x;
    LL num;
}dl[maxn],dr[maxn];

void solve(LL d,LL l,LL r)
{
    if ((d<0) || (l>=r)) return;
    LL cnt0=0,cnt1=0;
    for (LL i=l;i<=r;i++)
    {
        if (a[i]&bit[d])
        {
            ri[++cnt1]=a[i];
            y[d]+=(LL)cnt0;
        }
        else
        {
            le[++cnt0]=a[i];
            x[d]+=(LL)cnt1;
        }
    }
    for (LL i=1;i<=cnt0;i++) a[l+i-1]=le[i];
    for (LL i=1;i<=cnt1;i++) a[l+cnt0+i-1]=ri[i];
    solve(d-1,l,l+cnt0-1);
    solve(d-1,l+cnt0,r);
}

bool cmp1(rec x,rec y)
{
    if (x.x==y.x) return x.num<y.num;
    return x.x<y.x;
}

bool cmp2(rec x,rec y)
{
    return x.num<y.num;
}

void dfs1(LL d,LL num,LL sum)
{
    if (d>k/2)
    {
        dl[++cnt1]=(rec){sum,num};
        return;
    }
    dfs1(d+1,num,sum+x[d]);
    dfs1(d+1,num+bit[d],sum+y[d]);
}

void dfs2(LL d,LL num,LL sum)
{
    if (d>=k)
    {
        dr[++cnt2]=(rec){sum,num};
        return;
    }
    dfs2(d+1,num,sum+x[d]);
    dfs2(d+1,num+bit[d],sum+y[d]);
}

LL count(LL k)
{
    LL sum=0;
    for (LL i=1,j=cnt2;i<=cnt1;i++)
    {
        while ((j>0) && (dr[j].x+dl[i].x>k)) j--;
        sum+=j;
    }
    return sum;
}

LL find(LL k)
{
    LL l=0,r=0,d=1<<15;
    while (d>0)
    {
        if (l+d<=cnt1)
        {
            if (dl[l+d].x<k) l+=d;
        }
        d/=2;
    }
    d=1<<15;
    while (d>0)
    {
        if (r+d<=cnt1)
        {
            if (dl[r+d].x<=k) r+=d;
        }
        d/=2;
    }
    if (s<=r-l) return dl[l+s].num;
    s-=r-l;
    return -1;
}

int main()
{
    freopen("f.in","r",stdin);
    freopen("f.out","w",stdout);
    scanf("%lld%lld%lld",&n,&k,&p);
    for (LL i=1;i<=n;i++) scanf("%lld",&a[i]);
    bit[0]=1;
    for (LL i=1;i<maxp;i++) bit[i]=bit[i-1]*2;  
    solve(maxp-1,1,n);
    dfs1(0,0,0);
    dfs2(k/2+1,0,0);
    sort(dl+1,dl+cnt1+1,cmp1);
    sort(dr+1,dr+cnt2+1,cmp1);
    LL l=0,r=n*(n-1)/2;
    while (l<=r)
    {
        LL mid=(l+r)/2;
        if (count(mid)>=p) r=mid-1,ans1=mid;
                      else l=mid+1;
    }   
    s=p-count(ans1-1);
    sort(dr+1,dr+cnt2+1,cmp2);  
    for (LL i=1;i<=cnt2;i++)
    {
        LL d=find(ans1-dr[i].x);
        if (d!=-1)
        {
            ans2=d+dr[i].num;
            break;
        }
    }
    printf("%lld %lld",ans1,ans2);
}