Codeforces 706D Vasiliy's Multiset【贪心+字典树】

2019-11-06 06:12:47

字体：大中小

来源：转载

供稿：网友

D. Vasiliy's Multisettime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Author has gone out of the stories about Vasiliy, so here is just a formal task description.

You are given q queries and a multiset A, initially containing only integer 0. There are three types of queries:

"+ x" — add integer x to multiset A."- x" — erase one occurrence of integerx from multiset A. It's guaranteed that at least onex is PResent in the multiset A before this query."? x" — you are given integer x and need to compute the value $\text{[math]}$ , i.e. the maximum value of bitwise exclusive OR (also know as XOR) of integer x and some integery from the multiset A.

Multiset is a set, where equal elements are allowed.

Input

The first line of the input contains a single integer q (1 ≤ q ≤ 200 000) — the number of queries Vasiliy has to perform.

Each of the following q lines of the input contains one of three characters '+', '-' or '?' and an integer x_i (1 ≤ x_i ≤ 10⁹). It's guaranteed that there is at least one query of the third type.

Note, that the integer 0 will always be present in the setA.

Output

For each query of the type '?' print one integer — the maximum value of bitwise exclusive OR (XOR) of integerx_i and some integer from the multisetA.

ExampleInput

10+ 8+ 9+ 11+ 6+ 1? 3- 8? 3? 8? 11Output11101413NoteAfter first five Operations multiset A contains integers0, 8, 9, 11, 6 and 1.
The answer for the sixth query is integer  — maximum among integers,,, and.
题目大意：
一共有三种操作：
+ x 表示我们新添加一个元素x（可以重复添加）.
- x 表示我们删除一个元素x.
？ x 询问此时有的元素可以和x亦或的最大值，（最终值可能是本身）；
思路：
按位压缩为01串，然后将其按照三种操作处理：
+x -x分别就是增添和删除操作。
？x我们就贪心去查询即可。
1、我们按照长度为35位的二进制01字符串建树。将所有数据都建到树中。
因为最终解可能是本身，那么最初的时候添加到树中一个全是0的字符串。
2、接下来对于每个查询，同样处理成35位二进制01字符串，对应进行查询，如果当前位子是0，那么尽量往1那边走，同理，如果当前位子是1，那么尽量往0那边走即可。
Ac代码：
#include<stdio.h>#include<string.h>#include<stdlib.h>using namespace std;#define maxn 2typedef struct tree{    tree *nex[maxn];    int v;    int val;}tree;tree root;void init(){    for(int i=0;i<maxn;i++)    {        root.nex[i]=NULL;    }}void creat(char *str,int va){    int len=strlen(str);    tree *p=&root,*q;    for(int i=0;i<len;i++)    {        int id=str[i]-'0';        if(p->nex[id]==NULL)        {            q=(tree *)malloc(sizeof(root));            q->v=1;            for(int j=0;j<2;j++)            {                q->nex[j]=NULL;            }            p->nex[id]=q;        }        else        {            p->nex[id]->v++;        }        p=p->nex[id];        if(i==len-1)        {            p->val=va;        }    }}void del(char *str){    int len=strlen(str);    tree *p=&root;    for(int i=0;i<len;i++)    {        int id=str[i]-'0';        p->nex[id]->v--;        tree *tmp=p->nex[id];        if(p->nex[id]->v==0)        {            p->nex[id]=NULL;        }        p=tmp;    }    return ;}void find(char *str,int query){    int len=strlen(str);    tree *p=&root;    for(int i=0;i<len;i++)    {        int id=str[i]-'0';        if(p->nex[1-id]!=0)        {            p=p->nex[1-id];        }        else        p=p->nex[id];        if(p==NULL)        return ;        if(i==len-1)printf("%d/n",p->val^query);    }}int main(){    int n;    while(~scanf("%d",&n))    {        init();        char s[50];        s[36]='/0';        for(int i=0;i<=35;i++)s[i]='0';        creat(s,0);        while(n--)        {            char tmp[5];            char s[50];            scanf("%s",tmp);            int val;            scanf("%d",&val);            int a=val;            s[36]='/0';            for(int j=35;j>=0;j--)            {                if(a)                {                    s[j]=a%2+'0';                    a/=2;                }                else                {                    s[j]='0';                }            }            if(tmp[0]=='+')creat(s,val);            if(tmp[0]=='?')find(s,val);            if(tmp[0]=='-')del(s);        }    }}