NOIP 模拟 $11\; \rm english$

题解

本题有一定代码难度

对于需要区间最大值，可以反过来考虑，先预处理出每个数所能扩展的最大边界，也就是说，求出一个最大的区间，其最大值为这个数，单调栈 $\mathcal O(n)$ 求解

那么对于第一问，我们记录一个数组 $bit$，$bit_{i,j}$ 表示前 $i$ 个数二进制下第 $j$ 位为 $1$ 的有多少

对于每一个数，设其左边界为 $l_i$，右边界为 $r_i$，则我们将这个区间分成两部分 $l_i～i$，$i～r_i$，选取数少的枚举

枚举每一位，若这个数这一为不为 $1$，则贡献为 $r_i-i+1-(bit_{r_i,j}-bit_{i-1,j})$，为 $0$ 同理。

那么对于第二问，我们可以建一颗 $01trie$。

个人认为，可持久化 $01trie$ 就相当于 $01trie$ 前缀和，可以方便得求区间值

所以，我们这一问求得就是对于一个在 $num_j,j\in [l_i,i]$ 有多少 $k$ 满足 ${num_j}\;\;xor\;\;{num_k} > num_i$，$01trie$ 求解即可

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 FM(x) x>=MOD?x-MOD:x

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    typedef long long ll;

    static const int N=1e5+7,MOD=1e9+7;

    int que[N],num[N],l[N],r[N],bit[N][21],cm[21],pce,n,opt;

    ll tmp[21],nmc[21],ans1,ans2;

    struct Trie{

        #define ls(x) T[x].ch[0]

        #define rs(x) T[x].ch[1]

        struct trie{int ch[2],nm;}T[N*22];

        int rt[N],tot;

        inline void insert(int x,int pre,int &nw) {

            nw=p(tot);ri cur=nw;

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

                int p=(x>>i)&1;

                T[cur].nm=T[pre].nm+1;

                T[cur].ch[p^1]=T[pre].ch[p^1];

                T[cur].ch[p]=p(tot);

                cur=T[cur].ch[p],pre=T[pre].ch[p];

            }

            T[cur].nm=T[pre].nm+1;

        }

        inline int query(int sl,int pre,int cur) {

            ri res=0,nm=0;

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

                if (sl&cm[i]) {

                    if (nm+cm[i]>pce) {

                        int k=res;

                        res+=T[ls(cur)].nm-T[ls(pre)].nm;

                        cur=rs(cur),pre=rs(pre);

                    } else {

                        nm+=cm[i];

                        cur=ls(cur),pre=ls(pre);

                    }

                } else {

                    if (nm+cm[i]>pce) {

                        int k=res;

                        res+=T[rs(cur)].nm-T[rs(pre)].nm;

                        cur=ls(cur),pre=ls(pre);

                    } else {

                        nm+=cm[i];

                        cur=rs(cur),pre=rs(pre);

                    }

                }

            }

            return res;

        }

    }T;

    inline void add(int x,int p) {

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

            bit[p][i]=x&1;x>>=1;

            if (!x) return;

        }

    }

    inline int main() {

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

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

        read(n),read(opt);

        cm[0]=1;

        for (ri i(1);i<=20;p(i)) cm[i]=cm[i-1]<<1;

        for (ri i(1);i<=n;p(i)) read(num[i]);

        ri tl=0;

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

            add(num[i],i);

            T.insert(num[i],T.rt[i-1],T.rt[i]);

            while(tl&&num[que[tl]]<=num[i]) r[que[tl--]]=i-1;

            l[i]=que[tl]+1;

            que[p(tl)]=i;

            for (ri j(0);j<=20;p(j)) bit[i][j]+=bit[i-1][j];

        }

        while(tl) r[que[tl--]]=n;

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

            register ll res1=0,res2=0;

            pce=num[i];

            if (i-l[i]<=r[i]-i) {

                for (ri j(0);j<=20;p(j)) nmc[j]=bit[r[i]][j]-bit[i-1][j];

                ri len=r[i]-i+1;

                for (ri j(l[i]);j<=i;p(j)) {

                    for (ri k(0);k<=20;p(k)) {

                        if (num[j]&(1<<k)) tmp[k]=len-nmc[k];

                        else tmp[k]=nmc[k];

                        res1+=tmp[k]*cm[k]%MOD;

                        res1=FM(res1);

                    }

                    res2+=T.query(num[j],T.rt[i-1],T.rt[r[i]])%MOD;

                    res2=FM(res2);

                }

            } else {

                for (ri j(0);j<=20;p(j)) nmc[j]=bit[i][j]-bit[l[i]-1][j];

                ri len=i-l[i]+1;

                for (ri j(i);j<=r[i];p(j)) {

                    for (ri k(0);k<=20;p(k)) {

                        if (num[j]&(1<<k)) tmp[k]=len-nmc[k];

                        else tmp[k]=nmc[k];

                        res1+=tmp[k]*cm[k]%MOD;

                        res1=FM(res1);

                    }

                    res2+=T.query(num[j],T.rt[l[i]-1],T.rt[i])%MOD;

                    res2=FM(res2);

                }

            }

            ans1+=res1*num[i]%MOD,ans1=FM(ans1);

            ans2+=res2*num[i]%MOD,ans2=FM(ans2);

        }

        if (opt==1) printf("%lld\n",ans1);

        else if (opt==2) printf("%lld\n",ans2);

        else if (opt==3) printf("%lld\n%lld\n",ans1,ans2);

        return 0;

    }

}

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

巴特西

NOIP 模拟 $11\; \rm english$

题解

最新文章

热门文章