淘宝天猫优惠卷网站建设,怎么做关于易烊千玺的网站,注册传媒公司流程和费用,室内设计师网上培训班problem
luogu-P5283
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 nnn 种互不相同的粽子馅儿#xff0c;小粽将它们摆放为了一排#xff0c;并从左至右编号为 111 到 nnn。
第 iii 种馅儿具有一个非负整数的属性值 aia_iai。
每种馅儿的数…problem
luogu-P5283
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 nnn 种互不相同的粽子馅儿小粽将它们摆放为了一排并从左至右编号为 111 到 nnn。
第 iii 种馅儿具有一个非负整数的属性值 aia_iai。
每种馅儿的数量都足够多即小粽不会因为缺少原料而做不出想要的粽子。
小粽准备用这些馅儿来做出 kkk 个粽子。
小粽的做法是选两个整数数 l,rl,rl,r满足 1⩽l⩽r⩽n1 \leqslant l \leqslant r \leqslant n1⩽l⩽r⩽n将编号在 [l,r][l, r][l,r] 范围内的所有馅儿混合做成一个粽子所得的粽子的美味度为这些粽子的属性值的异或和。
小粽想品尝不同口味的粽子因此它不希望用同样的馅儿的集合做出一个以上的粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧
solution
考虑如何快速求得对于 iii 而言的一段往前的连续段异或最大值。
显然前缀异或和后转化成求 ji,aj⊕aiji,a_j\oplus a_iji,aj⊕ai 的最大值。
字典树基本应用。
接下来又怎么办呢这么多个区间。
考虑暴力是把所有区间异或和求出来然后扔进堆里面选权值前 kkk 大的。
这里我们找到了对于每个 iii 的最佳位置 jjj但是还有可能第二优秀的位置比其它 iii 的最佳位置权值更大。
我们又要避免找到重复的区间。
这里类比《超级钢琴》的做法。
记录下最佳位置的选择然后把可选区间 [l,r][l,r][l,r] 分成两段 [l,j],(j,r)[l,j],(j,r)[l,j],(j,r)。
也就需要实现可持久化字典树了。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 500005
int root[maxn], cnt;
struct tree { int son[2], id, cnt; }t[maxn * 80];
void insert( int lst, int now, int x, int id ) {root[now] cnt;now root[now], lst root[lst];t[now] t[lst]; t[now].cnt ;for( int i 32;~ i;i -- ) {int k x i 1;t[now].son[k] cnt;now t[now].son[k];lst t[lst].son[k];t[now] t[lst];t[now].cnt ;}t[now].id id;
}
int query( int L, int R, int x ) {for( int i 32;~ i;i -- ) {int k x i 1;if( t[t[R].son[k ^ 1]].cnt - t[t[L].son[k ^ 1]].cnt )R t[R].son[k ^ 1], L t[L].son[k ^ 1];elseR t[R].son[k], L t[L].son[k];}return t[R].id;
}
struct node { int l, r, x, p, val; bool operator ( const node v ) const {return val v.val;}
};
int a[maxn];
int n, k;
priority_queue node q;
signed main() {scanf( %lld %lld, n, k ); n ;for( int i 2;i n;i ) scanf( %lld, a[i] );for( int i 2;i n;i ) a[i] ^ a[i - 1];insert( 0, 1, 0, 1 );for( int i 2;i n;i ) insert( i - 1, i, a[i], i );for( int i 2;i n;i ) {int x query( root[0], root[i], a[i] );q.push( (node){ 0, i, x, i, a[i] ^ a[x] } );}int ans 0;while( ! q.empty() and k ) {node now q.top(); q.pop();k --; ans now.val; if( now.x - 1 now.l ) {int x1 query( root[now.l], root[now.x - 1], a[now.p] );q.push( (node){ now.l, now.x - 1, x1, now.p, a[now.p] ^ a[x1] } );}if( now.x now.r ) {int x2 query( root[now.x], root[now.r], a[now.p] );q.push( (node){ now.x, now.r, x2, now.p, a[now.p] ^ a[x2] } );}}printf( %lld\n, ans );return 0;
}
