NOIP 模拟 $22\; \rm f$

题解 $by\;zj\varphi$

对于一个数，如果它二进制下第 $i$ 位为 $1$，那么 $\rm x$ 在这一位选 $1$ 的贡献就是和它不同的最高为为 $i$ 的数的个数

这个东西很好搞，整一个 $\rm 01trie$ 就行，每会插入的时候直接统计即可

但是如何求第 $p$ 位，二分，但每回二分时 $2^k$ 搜索一遍就超时了，$\rm meet\;in\;the\;middle$

发现每一位是相互独立的，也就是说它们之间是不会互相影响的，所以将二进制位割半，分别排个序，之后对于一个序列用指针从小往大搜，同时维护另一个指针，而这个指针一定是单调递减的;

所以复杂度就是 $2^\frac{k}{2}log\frac{n×(n-1)}{2}$

对于第二问，对于大的那一半开个桶，维护它能在小的那一半匹配上的数，最后按大的排序，跳区间，每次判断这个数匹配上的 $siz$ 是否大于 $p$，若大于就在区间内暴力，可以保证复杂度不会超过 $2^\frac{k}{2}$

所以总复杂度为 $\mathcal O\rm (nk+2^\frac{k}{2}log\frac{n×(n-1)}{2}+2^\frac{k}{2})$

Code

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;register char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define pb(x) push_back(x)

    #define FI FILE *IN

    #define FO FILE *OUT

    template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}

    template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}

    typedef long long ll;

    static const int N=5e5+7;

    int a[N],tmp[N],st[N],pg[1<<16],id[1<<16],cnt1,cnt2,cnt,n,k,p,mx,hk,kh,S1,S2,bs,num,ans;

    ll al,del[33];

    vector<int> sg[1<<16];

    struct slv{ll f;int id;}so1[1<<16],so2[1<<16];

    inline int operator<(const slv &s1,const slv &s2) {return s1.f<s2.f;}

    struct BIT{

        #define lowbit(x) ((x)&-(x))

        int c[N];

        inline void update(int x) {for (ri i(x);i<=mx;i+=lowbit(i)) p(c[i]);}

        inline int query(int x) {

            int res(0);

            for (ri i(x);i;i-=lowbit(i)) res+=c[i];

            return res;

        }

    }B;

    struct Trie{

        #define sn(x,u) T[x].ch[u]

        struct trie{int ch[2],sz;}T[N*30];

        int tot;

        Trie(){tot=1;}

        inline void insert(int nw) {

            int p=1;

            for (ri i(29);~i;--i) {

                ri cur=(nw>>i)&1;

                if (!cur) del[i]-=T[sn(p,cur^1)].sz;

                else del[i]+=T[sn(p,cur^1)].sz;

                if (!sn(p,cur)) sn(p,cur)=p(tot);

                p=sn(p,cur);

                p(T[p].sz);

            }

        }

    }T;

    inline void init() {

        sort(tmp+1,tmp+n+1);

        int k=unique(tmp+1,tmp+n+1)-tmp;

        for (ri i(1);i<=n;p(i)) st[i]=lower_bound(tmp+1,tmp+k,st[i])-tmp;

        mx=k-1;

        for (ri i(n);i;--i) {

            al+=B.query(st[i]-1);

            B.update(st[i]);

        }

    }

    inline int check(ll f) {

        ri p2=1;

        num=0;

        for (ri p1(cnt1);p1;--p1) {

            while(p2<=cnt2&&so2[p2].f+so1[p1].f+al<=f) p(p2);

            num+=p2-1;

        }

        return num>=p;

    }

    inline void checka(ll f) {

        ri p1=1,tmp;

        num=0;

        for (ri p2(cnt2);p2;--p2) {

            p(cnt);

            id[pg[cnt]=cnt]=so2[p2].id;

            while(p1<=cnt1&&so2[p2].f+so1[p1].f+al<f) p(p1);

            tmp=0;

            while(p1<=cnt1&&so2[p2].f+so1[p1].f+al==f) {

                p(tmp);

                sg[cnt].pb(so1[p1].id);

                p(p1);

            }

            num+=p1-1-tmp;

        }

    }

    inline int cmp(int x,int y) {return id[x]<id[y];}

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(n),read(k),read(p);

        for (ri i(1);i<=n;p(i)) read(a[i]),st[i]=tmp[i]=a[i];

        init();

        for (ri i(1);i<=n;p(i)) T.insert(a[i]);

        hk=k>>1,kh=k-hk;

        bs=(S1=(1<<hk)-1)+1;

        S2=((1<<kh)-1)<<hk;

        for (ri i(0);i<=S1;p(i)) {

            ll tmp=0;

            for (ri j(0);j<hk;p(j)) if ((i>>j)&1) tmp+=del[j];

            so1[p(cnt1)].f=tmp;

            so1[cnt1].id=i;

        }

        for (ri i(0);i<=S2;i+=bs) {

            ll tmp=0;

            for (ri j(hk);j<k;p(j)) if ((i>>j)&1) tmp+=del[j];

            so2[p(cnt2)].f=tmp;

            so2[cnt2].id=i;

        }

        sort(so1+1,so1+cnt1+1);

        sort(so2+1,so2+cnt2+1);

        ll l=0,r=(ll)n*(n-1)/2,res(0);

        while(l<=r) {

            ll mid=(l+r>>1ll);

            if (check(mid)) r=mid-1,res=mid;

            else l=mid+1;

        }

        checka(res);

        sort(pg+1,pg+cnt+1,cmp);

        p-=num;

        for (ri i(1);i<=cnt;p(i)) {

            int cur=pg[i],siz=sg[cur].size();

            if (p>siz) p-=siz;

            else {

                sort(sg[cur].begin(),sg[cur].end());

                ans=id[cur]|sg[cur][p-1];

                break;

            }

        }

        printf("%lld %d\n",res,ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

NOIP 模拟 $22\; \rm f$

题解 \(by\;zj\varphi\)

最新文章

热门文章