即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

qwb VS 去污棒 可持续化01字典树

编程语言 Littlewhite520 11℃ 0评论

Problem I: qwb VS 去污棒


Time Limit: 2 Sec Memory Limit: 256 MB


Submit: 95 Solved: 36


[Submit][Status][Web Board]


Description

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为序列长度。

Input

第一行一个整数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 且保证所有操作合法。

Output

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

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

Sample Input


1


5 5


1 2 3 4 5


2 1 3 4


1 10


1 7


2 4 4 5


2 1 5 19

Sample Output


Case 1:


6


9


31

HINT

这种涉及到可持续的增添元素而且频繁的求最值的,用离线会比较方便。然后如果学过trie树来处理数的异或的话,会知道,数的异或最大值,只要往异或的相反方向走就好。

对于这种持续删减修改,明显是可持续结构,可以保留上一个边界的值。


每个结点保存的是一个后缀和 然后利用 x^(y^k)=(x^y)^k 来得到结果。 x指的是 p[i].x y指的是后缀和。但是对于后面的操作1(在末尾增加元素),后缀和也加了进去,所以需要用异或删掉 这个是k。

可持续化就是有这么一个优点,你能得到所有的区间变化的情况。


而且从中选出最优的


还是太难,即使明白原理也不想不到。

#include 
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];
int n,m;

struct node
{
    int ops;
    int l,r,x;
}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<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()
{
    int t;
    scanf("%d",&t);
    for(int cc=1;cc<=t;cc++){
        init();
        scanf("%d%d",&n,&m);
        tot=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
        }
        for(int i=1;i<=m;i++)
        {
            int op,x;
            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(int 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;
        int sz=0;
        printf("Case %d:\n", cc);

        for(int i=m;i>=1;i--)
        {
            if(p[i].ops==1)
            {
                last^=p[i].x;
            }
            else
            {
                int one=last^p[i].x;
                Ans[++sz]=Find(root[p[i].r+1],root[p[i].l],25,one);//可以得到 l到r 的所有后缀和异或值 情况。然后从中选出 
                //异或one的 最大情况
            }
        }
        for(int i=sz;i>=1;i--)
        {
            printf("%d\n",Ans[i]);
        }
    }
}

转载请注明:CodingBlog » qwb VS 去污棒 可持续化01字典树

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情