2017年浙江工业大学之江学院程序设计竞赛决赛 I: qwb VS 去污棒(可持久化Trie+离线)

问题 I: qwb VS 去污棒

时间限制: 2 Sec  内存限制: 256 MB
提交: 74  解决: 26
[提交][状态][讨论版]

题目描述

qwb表白学姐失败后,郁郁寡欢,整天坐在太阳底下赏月。在外人看来,他每天自言自语,其实他在和自己的影子“去污棒”聊天。
去污棒和qwb互相出题考验对方,去污棒问了qwb这样一个问题:
现已知一个有n个正整数的序列a[1],a[2]...a[n],接下来有m个操作

操作一共有两种:

1.在序列末尾添加一个数x。

2.查询suf[p] xor x的最大值,其中xor是异或 ,l<=p<=r,
suf[t]表示从t开始的后缀的异或和,即suf[t]=a[t] xor a[t+1] xor ...xor a[len],len为序列长度。

输入

第一行一个整数T(<=5),表示一共有T组数据。

每组数据第一行两个整数n(<=200000),m(<=200000),意义如上所述。

随后一行有n个数,表示初始序列。
随后m行,每行表示一个操作。
操作有两种,1: x 表示在末尾添加一个x,2: l r x表示查询suf[p] xor x的最大值,其中l<= p <= r,
所有数及x不超过224 且保证所有操作合法。

输出

每组测试数据的第一行输出"Case x:",x为数据组数的标号,从1开始。

接下来,对每个操作2输出一行答案。

样例输入

1
5 5
1 2 3 4 5
2 1 3 4
1 10
1 7
2 4 4 5
2 1 5 19

样例输出

Case 1:
6
9
31

题目链接:I题

如果用过可持久化Trie就可以发现这题解法已经非常明显了,但是他的序列是会变动的,那么由于题目是后缀异或和的性质,可以倒着做,用可持久化Trie维护最后的后缀异或值序列,然后考虑倒着做的时候每一次是减掉末尾的数x的影响,记后缀异或值序列为{后缀和},那么有:$max(x⊕({后缀和}⊕y))$与$max((x⊕y)⊕({后缀和}))$是等价的,那么我们记录一下倒着做的时候去掉的x的影响即用一个变量维护一下x的倒着的前缀和即可,然后由于是倒着维护的序列且是倒着离线,因此查询区间为$[r+1,l]$,答案也是倒着输出,感动~学的数据结构比赛的时候终于派上用场了……

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
struct Trie
{
    int nxt[2];
    int cnt;
};
Trie L[N * 27];
int tot, root[N];
int suf[N], arr[N];
int Ans[N];
 
struct info
{
    int ops;
    int l, r, x;
};
info P[N];
 
void init()
{
    memset(L, 0, sizeof(L));
    tot = 0;
}
void update(int &cur, int ori, int step, int n, int v)
{
    cur = ++tot;
    L[cur] = L[ori];
    L[cur].cnt += v;
    if (step < 0)
        return ;
    int t = (n >> step) & 1;
    update(L[cur].nxt[t], L[ori].nxt[t], step - 1, n, v);
}
int Find(int S, int E, int step, int n)
{
    if (step < 0)
        return 0;
    int t = (n >> step) & 1;
    if (L[L[E].nxt[t ^ 1]].cnt - L[L[S].nxt[t ^ 1]].cnt > 0)
        return (1 << step) + Find(L[S].nxt[t ^ 1], L[E].nxt[t ^ 1], step - 1, n);
    else
        return Find(L[S].nxt[t], L[E].nxt[t], step - 1, n);
}
int main(void)
{
    //printf("%d
",31^19);
    int tcase, n, m, i;
    scanf("%d", &tcase);
    for (int q = 1; q <= tcase; ++q)
    {
        init();
        scanf("%d%d", &n, &m);
        for (i = 1; i <= n; ++i)
            scanf("%d", &arr[i]);
        for (i = 1; i <= m; ++i)
        {
            scanf("%d", &P[i].ops);
            if (P[i].ops == 1)
            {
                scanf("%d", &P[i].x);
                arr[++n] = P[i].x;
            }
            else if (P[i].ops == 2)
            {
                scanf("%d%d%d", &P[i].l, &P[i].r, &P[i].x);
            }
        }
        suf[n + 1] = 0;
        for (i = n; i >= 1; --i)
        {
            suf[i] = suf[i + 1] ^ arr[i];
            update(root[i], root[i + 1], 25, suf[i], 1);
        }
        int last = 0;
        printf("Case %d:
", q);
        int sz = 0;
        for (i = m; i >= 1; --i)
        {
            if (P[i].ops == 1)
            {
                last ^= P[i].x;
            }
            else if (P[i].ops == 2)
            {
                int one = P[i].x ^ last;
                Ans[++sz] = Find(root[P[i].r + 1], root[P[i].l], 25, one);
            }
        }
        for (i = sz; i >= 1; --i)
            printf("%d
", Ans[i]);
    }
}
原文地址:https://www.cnblogs.com/Blackops/p/6936257.html