\(SPT（Super\ Piano\ Trick）\)
超级钢琴
选出 \(k\) 个最大的区间和，限制区间长度。
想到前缀和维护，然后区间最大值，可以确定每个左端点，对应的最大值。
维护前 \(k\) 大想到压堆，但是不可能全都压进去。
仍然是考虑对于每个左端点，右端点所在范围确定，那么当前的最大值就是确定的。
选完这个最大值，右端点所在范围中，当前选的这个点不能再选，其他的仍可能成为答案。
所以堆维护当前决策的区间和，最优决策点，左端点，以及右端点能取到的范围，每次相当于将右端点能取到的范围分成两部分，再找出最优决策压进去。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mx(x,y) (a[x]>a[y]?x:y)
const int N = 5e5+5;
int n,a[N],L,R,k,st[40][N],lg[N];
LL ans;
struct A
{
int l,L,R,v,p;
bool operator < (const A &x) const {return v<x.v;}
};
priority_queue<A> q;
inline int get(int l,int r)
{
if(l>r) return -1;
int k=lg[r-l+1];
return mx(st[k][l],st[k][r-(1<<k)+1]);
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d%d%d%d",&n,&k,&L,&R); lg[0]=-1;
for(int i=1,x;i<=n;i++) scanf("%d",&x),a[i]=a[i-1]+x,st[0][i]=i,lg[i]=lg[i>>1]+1;
for(int i=1;i<=30;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=mx(st[i-1][j],st[i-1][j+(1<<(i-1))]);
for(int i=1;i<=n;i++)
{
if(i+L-1>n) break;
int l=i+L-1,r=min(n,i+R-1),p=get(l,r);
q.push({i,l,r,a[p]-a[i-1],p});
}
while(k)
{
A tmp=q.top(); q.pop();
ans+=tmp.v; k--;
int p1=get(tmp.L,tmp.p-1),p2=get(tmp.p+1,tmp.R);
if(tmp.L<=tmp.p-1) q.push({tmp.l,tmp.L,tmp.p-1,a[p1]-a[tmp.l-1],p1});
if(tmp.p+1<=tmp.R) q.push({tmp.l,tmp.p+1,tmp.R,a[p2]-a[tmp.l-1],p2});
}
printf("%lld\n",ans);
return 0;
}
异或粽子
只是把用 ST 表维护的区间最大值改成维护区间最大异或，用可持久化 Trie 维护。
注意可持久化 Trie 维护区间信息一般不维护子树 size，很麻烦，可以直接维护最靠右的出现位置，类扫描线的做法。
一般线性基维护区间信息也是类似。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5+5;
int n,k;
LL a[N],ans;
namespace TRIE
{
int son[N<<6][2],mx[N<<6],rt[N],num;
inline void ins(LL x,int u,int lst)
{
rt[u]=++num;
int now=rt[u],now1=rt[lst];
for(int i=35;i>=0;i--)
{
int c=(x>>i)&1;
son[now][c]=++num;
son[now][c^1]=son[now1][c^1];
now=son[now][c]; now1=son[now1][c];
mx[now]=u;
}
}
inline int que(int a,int b,LL x)
{
if(b>a) return -1;
int now=rt[a];
for(int i=35;i>=0;i--)
{
int c=(x>>i)&1;
if(son[now][c^1]&&mx[son[now][c^1]]>=b) now=son[now][c^1];
else now=son[now][c];
}
return mx[now];
}
} using namespace TRIE;
struct A
{
int l,L,R,p; LL v;
inline bool operator < (const A &x) const {return v<x.v;}
};
priority_queue<A> q;
inline LL read()
{
LL res=0; char x=getchar();
while(x<'0'||x>'9') x=getchar();
while(x>='0'&&x<='9') res=(res<<1)+(res<<3)+(x^48),x=getchar();
return res;
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n=read(); k=read();
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]^read();
ins(a[i],i,i-1);
}
for(int i=1;i<=n;i++)
{
int p=que(n,i,a[i-1]);
q.push({i,i,n,p,a[p]^a[i-1]});
}
while(k)
{
A tmp=q.top(); q.pop();
ans+=tmp.v; k--;
int p1=que(tmp.R,tmp.p+1,a[tmp.l-1]),p2=que(tmp.p-1,tmp.L,a[tmp.l-1]);
if(p2!=-1) q.push({tmp.l,tmp.L,tmp.p-1,p2,a[p2]^a[tmp.l-1]});
if(p1!=-1) q.push({tmp.l,tmp.p+1,tmp.R,p1,a[p1]^a[tmp.l-1]});
}
printf("%lld\n",ans);
return 0;
}