P4585 [fjoi2015] Mars shop problem line segment tree tree transformation + canmontal TRIE tree - FJOI, FJOI2015, line segments, Mars, P4585, problems, Shops, Tree

Title: There are stores numbered 1-n, and each store has a permanent merchandise value of v

Operation 1: One day has passed The xth store adds a goods with a value of val

Operation 2: The Martian has his own password value x Ask the current day from the Lth store to the Rth store-d+1 to the current day The maximum value of XOR x among all goods (including permanent products)

The maximum XOR value is obviously a persistent trie tree

In the beginning If it is permanent, it can be updated at the beginning

Create a timeline segment tree First throw Martians into the timeline segment tree

Then follow the time Just do cdq.

Note that the operations should be sorted by store number, because persistent update requires ordering

Note that store numbers are not necessarily continuous, so Use a sequence to maintain a persistent trie

#include

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b); i++)

#define repp(i,a,b) for(int i=(a);i>=(b);--i)

#define ll long long

#define see(x) (cerr<<(#x)<<‘=‘<<(x)<#define inf 0x3f3f3f3f

#define CLR(A,v) memset(A,v,sizeof A)

///////////////////////////////// ///

const int N=1e5+10;

int t[N<<5][< span style="color: #800080;">2],T[N],siz[N<<5],ncnt,b[N];

void upnode(int k,int x,int pre,int &pos)

{

 pos=++ncnt;

 t[pos][0]=t[pre][0 ];t[pos][1]=t[pre][1];

 siz[pos]=siz[pre]+1;

 if(k<0)return;

 int c=(x>>k)&1;

 upnode(k-1,x,t[pre][c ],t[pos][c]);

}

int qmax(int k,int x,int pre,int pos)

{

 if(k<0)return 0;

 int c=(x>>k)&1;

 if( siz[t[pos][c^1]-t[pre][c^1]]>0 )< span style="color: #0000ff;">return (1<1,x,t[pre][c^1],t[pos][c^1]);

 else return qmax(k-1,x,t[pre][c],t[pos][c]);

}

vector<int>node[N<<2 ];

int n,m,ans[N];

void addnode(int x,int L,int R,int l,int r,int pos)

{

 if(L>R)return;

 if(L<=l&&r<=R){node[pos].push_back(x);return;}

 int m=(l+r)>>1;

 if(L<=m)addnode(x,L,R,l,m,pos<<1);

 if(R>m)addnode(x,L,R,m+1,r,pos<<1|1);

}

struct marspeo{int L, R, s, t, x;}peo[N];

struct upp{int t,x,val;}up[N],s1[N],s2[N];

int cnt1,cnt0;



void calc(int L,int R,int pos)

{

 int nn=0;ncnt=0;

 rep(i,L,R)

 {

 nn++;b[nn]=up[i].x;

 upnode(20,up[i].val,T[nn-1],T[nn]);

}

 for(auto v:node[pos])

 {

 int l=lower_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].L)-b;

 int r=upper_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].R)-b-1;

 int temp=qmax(20,peo[v ].x,T[l-1],T[r]);

 ans[v]=max(ans[v],temp);

}

}

void cdq(int L,int R,int l,int r,int pos)//LR is the operand

{

 if(L>R)return;

 calc(L,R,pos);

 if(l==r)return;

 int temp1=0,temp2=0,mid=(l+r)>>1;

 rep(i,L,R)

 if(up[i].t<=mid)s1[++temp1]=up[i];

 else s2[++temp2]=up[i];

 rep(i,1,temp1)up[i+L- 1]=s1[i];

 rep(i,1,temp2)up[i+L+temp1-1]=s2[i];

 cdq(L,L+temp1-1, l,mid,pos<<1);

 cdq(L+temp1,R, mid+1,r,pos<<1|1);

}

int main()

{

 scanf("%d%d",&n,&m);int x ,l,r,op,d;

 rep(i,1,n)scanf("%d",&x),upnode(20,x,T[i-1],T[i ]);

 while(m--)

 {

 scanf("%d",&op);

 if(!op){scanf("< span style="color: #800000;">%d%d",&l,&r);cnt0++;up[cnt0]=< span style="color: #000000;">(upp){cnt0,l,r};}

 else

 {

 scanf("%d%d%d%d",&l,&r,&x,&d);

 peo[++cnt1]=(marspeo){l,r,max(1,cnt0-d+1),cnt0,x};

 ans[cnt1]=qmax(20,x,T[l-1],T[r]);

}

}

 rep(i,1,cnt1)addnode(i,peo[i].s,peo[i].t, 1,cnt0,1) ;

 sort(up+1,up+1+cnt0 ,[](upp a,upp b){return ax<bx;});

 cdq(1,cnt0,1,cnt0, 1);

 rep(i,1,cnt1)printf("%d
" ,ans[i]);

 return 0;

}

View Code

share picture

#include

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b); i++)

#define repp(i,a,b) for(int i=(a);i>=(b);--i)

#define ll long long

#define see(x) (cerr<<(#x)<<‘=‘<<(x)<#define inf 0x3f3f3f3f

#define CLR(A,v) memset(A,v,sizeof A)

///////////////////////////////// ///

const int N=1e5+10;

int t[N<<5][< span style="color: #800080;">2],T[N],siz[N<<5],ncnt,b[N];

void upnode(int k,int x,int pre,int &pos)

{

 pos=++ncnt;

 t[pos][0]=t[pre][0 ];t[pos][1]=t[pre][1];

 siz[pos]=siz[pre]+1;

 if(k<0)return;

 int c=(x>>k)&1;

 upnode(k-1,x,t[pre][c ],t[pos][c]);

}

int qmax(int k,int x,int pre,int pos)

{

 if(k<0)return 0;

 int c=(x>>k)&1;

 if( siz[t[pos][c^1]-t[pre][c^1]]>0 )< span style="color: #0000ff;">return (1<1,x,t[pre][c^1],t[pos][c^1]);

 else return qmax(k-1,x,t[pre][c],t[pos][c]);

}

vector<int>node[N<<2 ];

int n,m,ans[N];

void addnode(int x,int L,int R,int l,int r,int pos)

{

 if(L>R)return;

 if(L<=l&&r<=R){node[pos].push_back(x);return;}

 int m=(l+r)>>1;

 if(L<=m)addnode(x,L,R,l,m,pos<<1);

 if(R>m)addnode(x,L,R,m+1,r,pos<<1|1);

}

struct marspeo{int L, R, s, t, x;}peo[N];

struct upp{int t,x,val;}up[N],s1[N],s2[N];

int cnt1,cnt0;



void calc(int L,int R,int pos)

{

 int nn=0;ncnt=0;

 rep(i,L,R)

 {

 nn++;b[nn]=up[i].x;

 upnode(20,up[i].val,T[nn-1],T[nn]);

}

 for(auto v:node[pos])

 {

 int l=lower_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].L)-b;

 int r=upper_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].R)-b-1;

 int temp=qmax(20,peo[v ].x,T[l-1],T[r]);

 ans[v]=max(ans[v],temp);

}

}

void cdq(int L,int R,int l,int r,int pos)//LR is the operand

{

 if(L>R)return;

 calc(L,R,pos);

 if(l==r)return;

 int temp1=0,temp2=0,mid=(l+r)>>1;

 rep(i,L,R)

 if(up[i].t<=mid)s1[++temp1]=up[i];

 else s2[++temp2]=up[i];

 rep(i,1,temp1)up[i+L- 1]=s1[i];

 rep(i,1,temp2)up[i+L+temp1-1]=s2[i];

 cdq(L,L+temp1-1, l,mid,pos<<1);

 cdq(L+temp1,R, mid+1,r,pos<<1|1);

}

int main()

{

 scanf("%d%d",&n,&m);int x ,l,r,op,d;

 rep(i,1,n)scanf("%d",&x),upnode(20,x,T[i-1],T[i ]);

 while(m--)

 {

 scanf("%d",&op);

 if(!op){scanf("< span style="color: #800000;">%d%d",&l,&r);cnt0++;up[cnt0]=< span style="color: #000000;">(upp){cnt0,l,r};}

 else

 {

 scanf("%d%d%d%d",&l,&r,&x,&d);

 peo[++cnt1]=(marspeo){l,r,max(1,cnt0-d+1),cnt0,x};

 ans[cnt1]=qmax(20,x,T[l-1],T[r]);

}

}

 rep(i,1,cnt1)addnode(i,peo[i].s,peo[i].t, 1,cnt0,1) ;

 sort(up+1,up+1+cnt0 ,[](upp a,upp b){return ax<bx;});

 cdq(1,cnt0,1,cnt0, 1);

 rep(i,1,cnt1)printf("%d
" ,ans[i]);

 return 0;

}

View Code

#include

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b); i++)

#define repp(i,a,b) for(int i=(a);i>=(b);--i)

#define ll long long

#define see(x) (cerr<<(#x)<<‘=‘<<(x)<#define inf 0x3f3f3f3f

#define CLR(A,v) memset(A,v,sizeof A)

///////////////////////////////// ///

const int N=1e5+10;

int t[N<<5][< span style="color: #800080;">2],T[N],siz[N<<5],ncnt,b[N];

void upnode(int k,int x,int pre,int &pos)

{

 pos=++ncnt;

 t[pos][0]=t[pre][0 ];t[pos][1]=t[pre][1];

 siz[pos]=siz[pre]+1;

 if(k<0)return;

 int c=(x>>k)&1;

 upnode(k-1,x,t[pre][c ],t[pos][c]);

}

int qmax(int k,int x,int pre,int pos)

{

 if(k<0)return 0;

 int c=(x>>k)&1;

 if( siz[t[pos][c^1]-t[pre][c^1]]>0 )< span style="color: #0000ff;">return (1<1,x,t[pre][c^1],t[pos][c^1]);

 else return qmax(k-1,x,t[pre][c],t[pos][c]);

}

vector<int>node[N<<2 ];

int n,m,ans[N];

void addnode(int x,int L,int R,int l,int r,int pos)

{

 if(L>R)return;

 if(L<=l&&r<=R){node[pos].push_back(x);return;}

 int m=(l+r)>>1;

 if(L<=m)addnode(x,L,R,l,m,pos<<1);

 if(R>m)addnode(x,L,R,m+1,r,pos<<1|1);

}

struct marspeo{int L, R, s, t, x;}peo[N];

struct upp{int t,x,val;}up[N],s1[N],s2[N];

int cnt1,cnt0;



void calc(int L,int R,int pos)

{

 int nn=0;ncnt=0;

 rep(i,L,R)

 {

 nn++;b[nn]=up[i].x;

 upnode(20,up[i].val,T[nn-1],T[nn]);

}

 for(auto v:node[pos])

 {

 int l=lower_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].L)-b;

 int r=upper_bound(b+1,b+< span style="color: #800080;">1+nn,peo[v].R)-b-1;

        int temp=qmax(20,peo[v].x,T[l-1],T[r]);

        ans[v]=max(ans[v],temp);

}

}

void cdq(int L,int R,int l,int r,int pos)//L R 为操作数

{

    if(L>R)return ;

    calc(L,R,pos);

    if(l==r)return ;

    int temp1=0,temp2=0,mid=(l+r)>>1;

    rep(i,L,R)

    if(up[i].t<=mid)s1[++temp1]=up[i];

    else s2[++temp2]=up[i];

    rep(i,1,temp1)up[i+L-1]=s1[i];

    rep(i,1,temp2)up[i+L+temp1-1]=s2[i];

    cdq(L,L+temp1-1, l,mid,pos<<1);

    cdq(L+temp1,R,   mid+1,r,pos<<1|1);

}

int main()

{

    scanf("%d%d",&n,&m);int x,l,r,op,d;

    rep(i,1,n)scanf("%d",&x),upnode(20,x,T[i-1],T[i]);

    while(m--)

 {

        scanf("%d",&op);

        if(!op){scanf("%d%d",&l,&r);cnt0++;up[cnt0]=(upp){cnt0,l,r};}

        else 

        {   

            scanf("%d%d%d%d",&l,&r,&x,&d);

            peo[++cnt1]=(marspeo){l,r,max(1,cnt0-d+1),cnt0,x};

            ans[cnt1]=qmax(20,x,T[l-1],T[r]);

}

}

    rep(i,1,cnt1)addnode(i,peo[i].s,peo[i].t,1,cnt0,1);

    sort(up+1,up+1+cnt0,[](upp a,upp b){return a.x<b.x;});

    cdq(1,cnt0,1,cnt0,1);

    rep(i,1,cnt1)printf("%d
",ans[i]);

 return 0;

}

Leave a Comment Cancel reply