C140 线段树分治+01Trie P4585 [FJOI2015] 火星商店问题

视频链接：C140 线段树分治+01Trie P4585 [FJOI2015] 火星商店问题_哔哩哔哩_bilibili

 

 

 

C09【模板】可持久化字典树（Trie） - 董晓 - 博客园 (cnblogs.com)

P4585 [FJOI2015] 火星商店问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线段树分治 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;#define N 100005
#define mid ((l+r)>>1)
#define rs ((u<<1)|1)
#define ls (u<<1)struct shop{int s,v,t; //商店编号,价格,时间
}p[N],p1[N],p2[N];
struct Q{int l,r,L,R,x; //商店区间,时间区间,密码
}q[N];
int n,m,idx,cnt,top;
int rt[N],ch[N*20][2],siz[N*20]; //01Trie
int s[N],ans[N];
vector<int> tr[N]; //节点bool cmp(shop &x,shop &y){return x.s<y.s;
}
void ins(int v){ //插入Triert[++idx]=++cnt;int x=rt[idx-1],y=rt[idx];for(int i=17;i>=0;i--){int j=v>>i&1;ch[y][!j]=ch[x][!j];   //异位继承ch[y][j]=++cnt;        //新位开点x=ch[x][j];y=ch[y][j]; //走位siz[y]=siz[x]+1;       //新位多1
  }
}
int query(int x,int y,int v){ //查询异或最值int ans=0;for(int i=17;i>=0;i--){int j=v>>i&1;if(siz[ch[y][!j]]>siz[ch[x][!j]])ans+=(1<<i),j=!j;x=ch[x][j]; y=ch[y][j];}return ans;
}
void solve(int u,int l,int r){// 重建当前区间的01Trie，查询区间异或最值top=idx=cnt=0;for(int i=l;i<=r;i++){s[++top]=p[i].s; //用栈记录商店编号ins(p[i].v);     //标价插入Trie
  }for(auto i:tr[u]){// 该区间商店编号有重复值，应该找靠右的编号int a=upper_bound(s+1,s+1+top,q[i].l-1)-s-1;int b=upper_bound(s+1,s+1+top,q[i].r)-s-1;ans[i]=max(ans[i],query(rt[a],rt[b],q[i].x));}if(l==r)return;// 时间小的修改扔到左边，时间大的修改扔到右边。// 分拣后，子区间依然是按商店编号有序的。int n1=0,n2=0;for(int i=l;i<=r;i++)p[i].t<=mid ? p1[++n1]=p[i] : p2[++n2]=p[i];for(int i=1;i<=n1;i++) p[i+l-1]=p1[i];for(int i=1;i<=n2;i++) p[i+mid]=p2[i];solve(ls,l,mid);solve(rs,mid+1,r);
}
void insert(int u,int l,int r,int L,int R,int x){if(L>r||R<l)return ;if(L<=l&&r<=R){tr[u].push_back(x);return;}insert(ls,l,mid,L,R,x);insert(rs,mid+1,r,L,R,x);
}
int main(){scanf("%d%d",&n,&m);for(int i=1,x;i<=n;i++)scanf("%d",&x), ins(x);int cnt=0,tot=0; //cnt天数,tot询问数for(int i=1,opt,s,v,l,r,x,d;i<=m;i++){scanf("%d",&opt);if(!opt){scanf("%d%d",&s,&v);p[++cnt]={s,v,cnt}; //修改
    }else{scanf("%d%d%d%d",&l,&r,&x,&d);q[++tot]={l,r,cnt-d+1,cnt,x}; //询问ans[tot]=query(rt[l-1],rt[r],x);}}for(int i=1;i<=tot;i++) //询问时间插入线段树insert(1,1,cnt,q[i].L,q[i].R,i);sort(p+1,p+1+cnt,cmp);  //按商店编号排序  solve(1,1,cnt);for(int i=1;i<=tot;i++)printf("%d\n",ans[i]);
}