# Noble 的博客

♡虹蓝♡

### 题解 P5283 【[十二省联考2019]异或粽子】

posted on 2019-04-08 21:14:41 | under 题解 |

### MLE

(int)p->son[0]=1;//ce

// luogu-judger-enable-o2
//01trie
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define reg register
typedef long long vt;
const int kmaxn = 500000 + 5;
const int kmaxd = 65;//64//<< 0-63
const int kmaxs = 62 * 500000;
struct node
{
node* son[2]={nullptr,nullptr};
};
node mempool[kmaxs];
int mpt;
node* root[kmaxn];
node* stk[kmaxn][kmaxd];
bool hsh[kmaxn][kmaxd][2];
short st[kmaxn];
int n, k;
vt arr[kmaxn];
inline node* alloc_node()
{
return mpt<kmaxs ? &mempool[mpt++] : new node;
}
void insert(node* lp, node*& p, vt v, int pos = 62)
{
p = alloc_node();
if (lp)*p = *lp;
if (pos<0) {
*(int*)(&(p->son[0])) = *(int*)(&(p->son[0]))+1;
//*(int*)(&p->son[0])=1;
//      cout<<(int)p->son[0]<<endl;
return;
}
bool b = (v)&(((vt)1) << pos);
insert((lp ? lp->son[b] : nullptr), p->son[b], v, pos - 1);
}
vt init(node* p, vt v, int num, int pos = 62)
{
stk[num][++st[num]] = p;
if (pos<0)return 0;
bool b = !((v)&(((vt)1) << pos));
if (p->son[b])
{
hsh[num][pos][b] = true;
return (((vt)1) << pos) + init(p->son[b], v, num, pos - 1);
}
else {
hsh[num][pos][!b] = true;
return init(p->son[!b], v, num, pos - 1);
}
}
//priority_queue<pair<vt,int>> q;
struct unit {
vt v;
int cnt, pos;
unit(vt _v = 0, int c = 0, int p = 0) :v(_v), cnt(c), pos(p) {
};
inline const bool operator<(const unit& u)const {
return v<u.v;
}
};
/*class pq{
public:
unit u[kmaxn];
int len=0;
inline void push(const unit& v)
{
u[len++]=v;
push_heap(u,u+len);
}
inline unit pop()
{
pop_heap(u,u+len);
return u[--len];
}
}q;*/
priority_queue<unit> q;
int dfs(int pos, vt v, vt& ans)
{
short& tail = st[pos];
reg bool dir = false;
reg bool b = false;
reg int dp = 0;
while (tail>1)
{
dir = (stk[pos][tail - 1]->son[1] == stk[pos][tail]);
dp = 63 - (--tail);
b = (v)&(((vt)1) << (dp));
if (b != dir)
ans -= (((vt)1) << (dp));
dir = !dir;
if (!hsh[pos][dp][dir] && stk[pos][tail]->son[dir])//find
{
break;
}
hsh[pos][dp][0] = hsh[pos][dp][1] = 0;
}
while (tail<64)//9223372032559812379
{
dp = 63 - tail;
dir = !((v)&(((vt)1) << dp));
if (stk[pos][tail]->son[dir] && !hsh[pos][dp][dir])//have and can turn
{
ans += (((vt)1) << (dp));
}
else
{
dir = !dir;
}
hsh[pos][dp][dir] = true;
stk[pos][tail + 1] = stk[pos][tail]->son[dir];
++tail;
}
return *(int*)(&(stk[pos][tail]->son[0]));
}
inline void solve()
{
unsigned long long ans = 0;
reg int pos = 0;
reg int c = 0;
vt t = -1;
unit temp;
while (k)
{
//      printf("k %d\n", k);
//temp=q.pop();
temp = q.top();
q.pop();
t = temp.v;
c = min(temp.cnt, k);
k -= c;
pos = temp.pos;
ans += t*c;
c = dfs(pos, arr[pos], t);
if (t >= 0)
q.push(unit(t, c, pos));
t = -1;
}
printf("%lld\n", ans);
}
int main()
{
//  freopen("xor19.in", "r", stdin);
scanf("%d%d", &n, &k);
//  printf("%d  %d\n", n, k);
insert(nullptr, root[0], 0);
vt t=0;
for (reg int i = 1; i <= n; ++i)
{
//cin>>arr[i];
scanf("%lld", &arr[i]);
arr[i] ^= arr[i - 1];
insert(root[i - 1], root[i], arr[i]);
t = init(root[i], arr[i], i);
//      printf("%d  cnt %d\n", i, *(int*)(void*)(&(stk[i][64]->son[0])));
q.push(unit(t, *(int*)(&(stk[i][64]->son[0])), i));
}
solve();
//  while (1);
return 0;
}