Noble 的博客

Noble 的博客

♡虹蓝♡

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

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

这里给出一个考场玄学做法。

首先我们可以看出这题可持久化01trie可做

然后我们可以发现对于答案中的每个区间,它必然有一个右端点(废话)

既然每个答案有一个右端点,那么我们只要能对所有可行的右端点,得到可行的最大区间异或和就行了。

把序列弄成前缀异或和,当trie树深度为d时,这可以O(nd)搞出来,O(nlogn)塞进堆里。

当我们弹出一个区间和时,对于这个右端点,它的答案需要更新成次大的区间异或和。

这很明显可以通过trie树节点上记录size,直接求第k大搞定。

但是其实可以不这么做。

当在trie树上找最大异或值时,其实就是贪心在搜索树上找到一条链的过程。

但是这里的贪心和一般的贪心不同,很明显,每层只有两个决策,并且在树深度较深处转向,比更浅处更优。

这不就是dfs的回溯吗

所以我们可以开一个n * d的二维数组作为堆栈。每在堆中取出一个区间异或和,我们就对对应的右端点回溯。

但是看这个数据:3 2 2 ...

它的异或前缀和是:3 1 3 ...

这个3,在异或前缀和里出现了不止一次,但对于trie树,它只出现了一次,如果对于某个右端点,3需要对答案提供不止一次的贡献,喜提Wa。(大样例都过不去但是可以80分)

好办,维护计数器

MLE

为啥会mle呢,因为这个做法需要保留对于每个右端点,取答案时trie树上走的路径。算上堆栈,就相当于是开了1颗半可持久化trie。

而且还要记录路径上每个节点走过方向,又是一个2nd大小的bool数组。

如果给trie树维护计数器,那么内存又会增加4 n d/1024/1024≈123MB。加上之前那些乱七八糟的东西和系统栈,内存十分爆炸,1G刚好不够。

凉凉? 不,强行续命!

我们可以发现这个做法并不需要维护节点的子树size,只需要对叶子结点维护计数器,而叶子节点没有左右儿子,这不是明显可以 一var多用。

如果是数组写的trie树,那么题已经做完了。

指针只能凉凉? 其实还能再续。

虽然在c++(或者说oi版c++)中,变量是有类型的,但是我们还有强制类型转换!反正都是一段内存,而且指针保存的东西本质上就是个作为偏移量的整数,怎么不能当计数器?

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

貌似强制类型转换返回的是常量,不能做左值。所以还是凉凉?

这个东西其实是可以绕过去的。

我们可以把它写成这样 (int)(&p->son[0])=1;

这样(int*)(&p->son[0])是一个指向变量的常量指针,指向的变量是(p->son[0])(当做int处理),这不就可以做修改了吗。

然后就可以 写出来ac代码 强行续命80分代码了。

时间复杂度考虑trie树深度应该是O(nd+mlogn+(m-n)d),本题d=64.

跑的奇慢,交之前或许需要洗把脸。

// 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;
}

幸好考场上死也没想出来需要维护计数器,否则MLE 80变60就很惨了(80变0更惨)