[BZOJ3261&BZOJ3166]可持久化trie树及其应用

可持久化trie树

　　可持久化trie树现在想来是比较好理解的了，但却看了一个下午...

　　相当于对于每个状态建立一条链（或者说一棵trie），求解的时候只要让两个点按照相同的步子走然后看sum的大小关系即可。

　　tr[y].son[p xor 1]:=tr[x].son[p xor 1];

　　tr[y].sum:=tr[x].sum+1;

　　这两句要好好体会，对之后理解query过程中的语句很有帮助。

　　if (tr[tr[x].son[p xor 1]].sum=tr[tr[x].son[p xor 1]].sum) then...

　　刚开始曾经想过这个x已不一定在区间中，这样对吗？

　　我们分情况讨论，如果上述语句值为真，考虑右边的y，y就算不是右边界但显然是因为>y中的链已经不能满足走到当前步了。

　　再考虑左边界，如果一个在左边界以左的数都与后面的sum相等了，也就是[l,r]区间，以及其左边的一段都没有存在的链。

　　这种情况显然是对的。

　　如果不等呢？会因为左边界而导致原本应该不存在的链算入答案吗？

　　如果存在一个在[l,r]以左的x以右的链，那当前走到的一定是这条链...因为从insert过程可以看出，我们的插入是按照下标的顺序的

　　所以这种情况不存在，那不等的时候也是满足的。

　　这样一来，对于可持久化trie树就完全理解了。但是应用的时候还是要注意一些东西。

BZOJ3261

　　Description

　　给定一个非负整数序列 {a}，初始长度为 N。
　　有 M个操作，有以下两种操作类型：

　　1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
　　2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：

　　a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。

　　首先看到异或，还是可以比较自然地想到可持久化trie

　　然后对于题目让我们求的这一串东西，可以想到前缀和。

　　但由于异或运算的特殊性，设b[i]为1~i的异或和，b[i-1]^b[n]^x就是所求答案（∵ x^x=0）

　　A操作就是普通的insert操作，对于Q，我们只需要执行一次query操作即可。

　　在未学习可持久化trie之前这道题query的思维可圈可点但是学习了以后再回头看就是一道简单的模板题了~

program bzoj3261;

const maxn=;

var n,m,tot,tem,i,x,l,r:longint;

    ch:char;

    tr:array[-..maxn]of record sum:longint;son:array[..]of longint;end;

    root,a:array[-..maxn div ]of longint;

procedure insert(x:longint;var y:longint;ave,v:longint);

var p:longint;

begin

    inc(tot);y:=tot;

    tr[y].sum:=tr[x].sum+;

    if v< then exit;

    p:=(ave >> v) and ;

    tr[y].son[p xor ]:=tr[x].son[p xor ];

    insert(tr[x].son[p],tr[y].son[p],ave,v-);

end;

function query(x,y,ave,v:longint):longint;

var p:longint;

begin

    if v< then exit();

    p:=(ave >> v) and ;

    if (tr[tr[x].son[p xor ]].sum=tr[tr[y].son[p xor ]].sum) then exit(query(tr[x].son[p],tr[y].son[p],ave,v-)) else

    exit(query(tr[x].son[p xor ],tr[y].son[p xor ],ave,v-)+ << v);

end;

begin

    readln(n,m);

    tot:=;

    insert(root[-],root[],,);
　　//这道题有个特殊之处在于0点也是要插入trie树的点
　　//因此要小心越界
　　//由于平时的习惯就是数组下标从-1开始，所以“好习惯能避免错误”^_^也是张老师说的

    tem:=;

    for i:= to n do

    begin

        read(a[i]);

        insert(root[i-],root[i],a[i] xor tem,);

        tem:=tem xor a[i];

    end;

        readln;

        for i:= to m do

    begin

        read(ch);

        if ch='A' then

        begin

            inc(n);readln(a[n]);

                insert(root[n-],root[n],a[n] xor tem,);

             tem:=tem xor a[n];

        end else

        begin

            readln(l,r,x);

                writeln(query(root[l-],root[r-],x xor tem,));

        end;

    end;

end.

BZOJ3166：[Heoi2013]Alo

　　Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，
如名字所见，到处充满了数学的谜题。
现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量
密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai, ai+1, …, a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值
与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次大值
为k，则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。

　　首先这道题的解法是显而易见的...将每个数插入trie树中，然后我们最终答案所在的区间一定是极大区间

　　然后可以枚举次大值，显然当这个数定下来的时候，它存在两个极大区间

　　一个是它左边比它大的第二个数的下标+1~右边比它大的第一个数的下标-1

　　一个是它左边比它大的第一个数的下标+1~右边比它大的第二个数的下标-1

　　左右处理起来都一样~遇到的第一个数前几天正好做到过，用单调栈可以完美解决

　　至于第二大...我写的比较长

　　就是先按照值从大到小排序，然后用树状数组存以下标为下标的最大值和次大值，get的时候调的参数也是下标

　　为什么可以这样呢..?因为当初学树状数组的时候我就用它求过最大值，当时老师也很惊奇我居然可以那么写

　　但既然树状数组把1~i分成若干块，每一块都是到它前面一块的答案，那求最大值为何不可呢？

　　然后今天又用它来保存两个值..一个最大一个次大...感觉非常爽啊...

program bzoj3166;

const maxn=;

var tot,ans,i,n,x,y:longint;

    a,l,r,opt,root,id,l2,r2,aa:array[-..maxn div ]of longint;

    tar:array[-..maxn div ]of record x,y:longint;end;

    tr:array[-..maxn]of record sum:longint;son:array[..]of longint;end;

function max(a,b:longint):longint;

begin

    if a>b then exit(a) else exit(b);

end;

procedure swap(var x,y:longint);

var tem:longint;

begin

        tem:=x;x:=y;y:=tem;

end;

procedure insert(x:longint;var y:longint;ave,v:longint);

var p:longint;

begin

    inc(tot);y:=tot;

    tr[y].sum:=tr[x].sum+;

    if v< then exit;

    p:=(ave >> v)and ;

    tr[y].son[p xor ]:=tr[x].son[p xor ];

    insert(tr[x].son[p],tr[y].son[p],ave,v-);

end;

function query(x,y,ave,v:longint):longint;

var p:longint;

begin

    if v< then exit();

    p:=(ave >> v)and ;

    if tr[tr[y].son[p xor ]].sum=tr[tr[x].son[p xor ]].sum then exit(query(tr[x].son[p],tr[y].son[p],ave,v-)) else

    exit(query(tr[x].son[p xor ],tr[y].son[p xor ],ave,v-)+ << v);

end;

procedure qsort(L,R:longint);

var i,j,mid:longint;

begin

    i:=L;j:=R;mid:=a[random(R-L+)+L];

    repeat

        while (i<R)and(a[i]>mid) do inc(i);

        while (L<j)and(a[j]<mid) do dec(j);

        if i<=j then

        begin

                        swap(a[i],a[j]);swap(id[i],id[j]);

            inc(i);dec(j);

        end;

    until i>j;

    if i<R then qsort(i,R);

    if L<j then qsort(L,j);

end;

procedure mend(x,y:longint);

begin

    if y>tar[x].x then

    begin

        tar[x].y:=tar[x].x;

        tar[x].x:=y;

    end else

    if y>tar[x].y then tar[x].y:=y;

end;

procedure put(x,y:longint);

begin

    if x= then

    begin

        mend(,y);

        exit;

    end;

    while x<=n+ do

    begin

        mend(x,y);

        x:=x+x and (-x);

    end;

end;

function get(x:longint):longint;

var ans1,ans2,tem:longint;

begin

    ans1:=tar[].x;ans2:=tar[].y;

        tem:=x;

    while x<> do

    begin

        if tar[x].x>ans1 then

        begin

            ans2:=ans1;

            ans1:=tar[x].x;

        end else if tar[x].x>ans2 then ans2:=tar[x].x;

        if tar[x].y>ans1 then

        begin

            ans2:=ans1;

            ans1:=tar[x].y;

        end else if tar[x].y>ans2 then ans2:=tar[x].y;

        x:=x-x and (-x);

    end;

    exit(ans2);

end;

procedure solve_lr;

var i,tail:longint;

begin

    a[]:=maxlongint;

    tail:=;opt[]:=;

    for i:= to n do

    begin

        while a[opt[tail]]<a[i] do dec(tail);

        l[i]:=opt[tail];

        inc(tail);opt[tail]:=i;

    end;

    a[n+]:=maxlongint;

    tail:=;opt[]:=n+;

    for i:=n downto  do

    begin

        while a[opt[tail]]<a[i] do dec(tail);

        r[i]:=opt[tail];

        inc(tail);opt[tail]:=i;

    end;

        for i:= to n+ do id[i]:=i;

    qsort(,n+);

    fillchar(tar,sizeof(tar),);

    for i:= to n+ do

    begin

        l2[id[i]]:=get(id[i]);

        put(id[i],id[i]);

    end;

        fillchar(tar,sizeof(tar),);

    for i:= to n+ do

    begin

        r2[id[i]]:=n-get(n-id[i]+)+;

        put(n-id[i]+,n-id[i]+);

    end;

end;

begin

    readln(n);

    for i:= to n do read(a[i]);

        aa:=a;

    solve_lr;

        a:=aa;

    tot:=;ans:=;

    for i:= to n do insert(root[i-],root[i],a[i],);

        for i:= to n do

    begin

        x:=l2[i]+;y:=r[i]-;

        ans:=max(ans,query(root[x-],root[y],a[i],));

        x:=l[i]+;y:=r2[i]-;

        ans:=max(ans,query(root[x-],root[y],a[i],));

    end;

    writeln(ans);

end.

　　感觉BZOJ对可持久化trie树特别偏爱，但是网上不像其他算法有大波的教程。

　　其实我觉得这个算法真的很优美在异或的类型题中尤其好用

　　好好掌握其实理解了之后根本不需要背

　　大概数据结构题就是这样形象的吧

巴特西

[BZOJ3261&BZOJ3166]可持久化trie树及其应用

Description

BZOJ3166：[Heoi2013]Alo

Description

最新文章

热门文章