题意

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 n n n 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 1 1 1 到 n n n。第 i i i 种馅儿具有一个非负整数的属性值 a i a_i ai​。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k k k 个粽子。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

小粽的做法是：选两个整数数 l l l, r r r，满足 1 ⩽ l ⩽ r ⩽ n 1 \leqslant l \leqslant r \leqslant n 1⩽l⩽r⩽n，将编号在 [ l , r ] [l, r] [l,r] 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符）

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的 粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

输入输出格式

输入格式：

第一行两个正整数 n n n, k k k，表示馅儿的数量，以及小粽打算做出的粽子的数量。

接下来一行为 n n n 个非负整数，第 i i i 个数为 a i a_i ai​，表示第 i i i 个粽子的属性值。 对于所有的输入数据都满足： 1 ⩽ n ⩽ 5 × 1 0 5 1 \leqslant n \leqslant 5 \times 10^5 1⩽n⩽5×105, 1 ⩽ k ⩽ min ⁡ { n ( n − 1 ) 2 , 2 × 1 0 5 } 1 \leqslant k \leqslant \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\} 1⩽k⩽min{2 n(n−1)​,2×105}, 0 ⩽ a i ⩽ 4 2 9 4 9 6 7 2 9 5 0 \leqslant a_i \leqslant 4 294 967 295 0⩽ai​⩽4294967295。

输出格式：

输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。

输入输出样例

输入样例#1： 复制 
3 2
1 2 3
输出样例#1： 复制 
6

说明

测试点 n n n k k k
1 1 1, 2 2 2, 3 3 3, 4 4 4, 5 5 5, 6 6 6, 7 7 7, 8 8 8 ⩽ 1 0 3 \leqslant 10^3 ⩽103 ⩽ 1 0 3 \leqslant 10^3 ⩽103
9 9 9, 1 0 10 10, 1 1 11 11, 1 2 12 12 ⩽ 5 × 1 0 5 \leqslant 5 \times 10^5 ⩽5×105 ⩽ 1 0 3 \leqslant 10^3 ⩽103
1 3 13 13, 1 4 14 14, 1 5 15 15, 1 6 16 16 ⩽ 1 0 3 \leqslant 10^3 ⩽103 ⩽ 2 × 1 0 5 \leqslant 2 \times 10^5 ⩽2×105
1 7 17 17, 1 8 18 18, 1 9 19 19, 2 0 20 20 ⩽ 5 × 1 0 5 \leqslant 5 \times 10^5 ⩽5×105 ⩽ 2 × 1 0 5 \leqslant 2 \times 10^5 ⩽2×105

分析

又是问前k大，可以参考线段树求所有区间前k大的做法，拆区间。

但是Trie树不支持任意区间查询，即使可持久化后也只能查询右端点固定的。但是没有关系，把每个右端点对应的部分区间都插入二叉堆就行了。

时间复杂度\(O(n \log v+k \log v)\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=2e5+5,INF=0x3f3f3f3f;
char s[N];
int n,na,nb,m;
pair<int,int> a[N],b[N];
int trie[N][26],tot,root;
vector<int> val[N],edge[N];
int newnode(){
    ++tot,memset(trie[tot],0,sizeof trie[tot]),val[tot].clear();
    return tot;
}
void insert(char*s,int n,int id){
    int u=root;
    for(int i=0;i<n;++i){
        int k=s[i]-'a';
        if(!trie[u][k]) trie[u][k]=newnode();
        u=trie[u][k],val[u].push_back(id);
    }
}
void link(char*s,int n,int id){
    int u=root;
    for(int i=0;u&&i<n;++i){
        int k=s[i]-'a';
        u=trie[u][k];
    }
    if(!u) return;
    for(int i=0;i<val[u].size();++i)
        edge[id].push_back(val[u][i]);
}
int deg[N],dis[N],pos[N],ref[N],ans;
queue<int> que;
int lpfa(){
    fill(deg+1,deg+na+1,0);
    fill(pos,pos+na+1,0);
    fill(dis+1,dis+na+1,-INF);
    for(int i=1;i<=na;++i)
        for(int j=0;j<edge[i].size();++j)
            ++deg[edge[i][j]];
    for(int i=1;i<=na;++i)
        if(!deg[i]) que.push(i),dis[i]=a[i].second-a[i].first+1;
    for(int u;que.size();){
        u=que.front(),que.pop();
        pos[u]=++pos[0],::ref[pos[0]]=u;
        for(int i=0,v;i<edge[u].size();++i){
            v=edge[u][i];
            if(--deg[v]==0) que.push(v);
        }
    }
    if(pos[0]<na) return -1;
    ans=-INF;
    for(int i=1,u;i<=na;++i){
        u=::ref[i],ans=max(ans,dis[u]);
        for(int j=0,v;j<edge[u].size();++j){
            v=edge[u][j];
            if(dis[v]<dis[u]+a[v].second-a[v].first+1)
                dis[v]=dis[u]+a[v].second-a[v].first+1;
        }
    }
    return ans;
}
void String(){
    scanf("%s",s+1),n=strlen(s+1);
    read(na),tot=0,root=newnode();;
    for(int i=1;i<=na;++i){
        read(a[i].first),read(a[i].second),edge[i].clear();
        insert(s+a[i].first,a[i].second-a[i].first+1,i);
    }
    read(nb);
    for(int i=1;i<=nb;++i) read(b[i].first),read(b[i].second);
    read(m);
    for(int i=1,x,y;i<=m;++i){
        read(x),read(y);
        link(s+b[y].first,b[y].second-b[y].first+1,x);
    }
    printf("%d\n",lpfa());
}
int main(){
//  freopen(".in","r",stdin),freopen(".out","w",stdout);
    for(int T=read<int>();T--;) String();
    return 0;
}

伪作法

逐位考虑，计数。\(O(n \log^2 v)\)。最慢的点要跑13s。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
il char nc(){
    static char buf[6000000], *p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
il unsigned read(){
    rg char ch=nc();rg unsigned sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
typedef long long ll;
using namespace std;

co int N=5e5+1;
int n,k;
unsigned s,a[N];
unordered_map<unsigned,int> c;
unordered_map<unsigned,unordered_map<int,int> > v;
ll cnt,ans,res;
int main(){
//  freopen("xor.in","r",stdin),freopen("xor.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;++i) a[i]=read()^a[i-1];
    for(int p=31;k&&p>=0;--p){
        s|=1U<<p,c.clear(),cnt=0;
        for(int i=0;i<=n;++i){
            cnt+=c[(s^a[i])>>p];
            if(cnt>k) break;
            ++c[a[i]>>p];
        }
//      fprintf(stderr,"%d s=%u cnt=%lld\n",p,s,cnt);
        if(cnt<=k){
            ans+=(ll)s*cnt,k-=cnt,c.clear(),v.clear();
            for(int i=0;i<=n;++i){
                for(int q=p-1;q>=0;--q){
                    if(a[i]>>q&1) ans+=(1LL<<q)*(c[(s^a[i])>>p]-v[(s^a[i])>>p][q]),++v[a[i]>>p][q];
                    else ans+=(1LL<<q)*v[(s^a[i])>>p][q];
                }
                ++c[a[i]>>p];
            }
            s^=1U<<p;
        }
    }
    ans+=(ll)s*k;
    printf("%lld\n",ans);
    return 0;
}

伪作法2

从前往后扫描，建立Trie树，直接用每个点更新二叉堆，当这个点的当前最大值小于堆中的最小值时continue，时间复杂度\(O(n^2 \log v)\)，爆踩标算。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
const int MAXN=5e5+10;
const int N=32;
ll a[MAXN];
ll s[MAXN],t=0;
struct Trie
{
    int idx;
    int ch[MAXN*32][2];
    int tot[MAXN*32][2];
    Trie(){idx=0;}
    void ins(ll x)
    {
        int u=0;
        for(int i=N-1; i>=0; --i)
        {
            int k=(int)((x>>i)&1LL);
            tot[u][k]++;
            if(ch[u][k])
                u=ch[u][k];
            else
                u=(ch[u][k]=++idx);
        }
    }
    ll query(ll x,int p)
    {
        int u=0;
        --p;
        ll res=0;
        for(ll i=N-1; i>=0; --i)
        {
            int k=(int)((x>>i)&1LL);
            int v;
            if(ch[u][k^1])
            {
                if(p>=tot[u][k^1] && ch[u][k])
                {
                    v=k;
                    p-=tot[u][k^1];
                }
                else
                {
                    v=k^1;
                    res+=(1LL<<i);
                }
            }
            else
            {
                v=k;
            }
            u=ch[u][v];
        }
        return res;
    }
} T;
priority_queue<ll> q;
int siz=0;
int n,k;
void solve()//One Must Have His Dream.
{
    srand(19260817);
    random_shuffle(a+1,a+1+n);
    reverse(a+1,a+1+n);
    for(int i=1; i<=n; ++i)
    {
        int f=1;
        for(int p=1; p<=min(k,i-1) && f; ++p)
        {
            ll c=T.query(a[i],p);
            if(siz<k)
                q.push(-c),++siz;
            else
            {
                if(c<=-q.top())
                    f=0;
                else
                {
                    q.pop();
                    q.push(-c);
                }
            }
        }
        T.ins(a[i]);
    }
    ll ans=0;
    while(!q.empty())
    {
        ll x=q.top();
        ans-=x;
        q.pop();
    }
    cout<<ans<<endl;
}
int main()
{
//  freopen("xor.in","r",stdin);
//  freopen("xor.out","w",stdout);
    n=read(),k=read();
    for(int i=1; i<=n; ++i)
        a[i]=a[i-1]^read();
    a[++n]=0;
    solve();
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄