2020-2021:teams:legal_string:jxm2001:数据结构练习_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/09/17 19:26] jxm2001 [习题五] |
2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/10/08 15:00] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 24: | 行 24: | ||
| 但由于区间 $[l,b]$ 可能已经属于某个区间 $[a,b]$，所以需要线段树分裂将其分裂为 $[a,l-1],[l,b]$。 | 但由于区间 $[l,b]$ 可能已经属于某个区间 $[a,b]$，所以需要线段树分裂将其分裂为 $[a,l-1],[l,b]$。 | ||
| - | 同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。 | + | 同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。 |
| + | |||
| + | 最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。 | ||
| 初始化时间复杂度 $O(n\log n)$，产生点数 $O(n\log n)$。每次分裂时间复杂度 $O(\log n)$，且增加 $O(\log n)$ 个点。 | 初始化时间复杂度 $O(n\log n)$，产生点数 $O(n\log n)$。每次分裂时间复杂度 $O(\log n)$，且增加 $O(\log n)$ 个点。 | ||
| 行 811: | 行 813: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| ==== 习题五 ==== | ==== 习题五 ==== | ||
| - | [[https://www.luogu.com.cn/problem/P4197|洛谷p4197]] | + | [[https://www.luogu.com.cn/problem/P3293|洛谷p3293]] |
| === 题意 === | === 题意 === | ||
| - | 给定 $n$ 个点和 $m$ 条边，每个点给定一个点权，每条边给定一个边权。接下来 $q$ 个询问。 | + | 给定长度为 $n$ 的序列 $a$ 和 $q$ 个询问。每次询问给定 $b,x,l,r$，输出 $\max_{l\le i\le r}(b\oplus(a_i+x))$。 |
| - | + | ||
| - | 每次询问从点 $v$ 开始不经过边权超过 $x$ 的边可以走到的点中第 $k$ 大的权值。 | + | |
| === 题解 === | === 题解 === | ||
| - | 考虑 $\text{Kruskal}$ 算法重构树，即求取最小生成树过程中将加边操作改为生成一个新结点同时将新结点作为两个连通块的根节点的祖先。 | + | 考虑按高位到低位贪心枚举。假设当前枚举到第 $4$ 为，答案 $\text{ans}=c_1c_2c_3???,b=b_1b_2b_3b_4??$。 |
| - | 将重构树上的新结点的点权设为该结点代表边的边权，原树中结点点权设为 $0$。于是重构树上的点权从叶子结点到根节点单增。 | + | 优先考虑是否可以使 $\text{ans}=c_1c_2c_31??$，如果 $b_4=1$，则 $\text{ans}\oplus b\in[d_1d_2d_3000,d_1d_2d_3011]$。 |
| - | 于是每次询问从原树某结点开始可以到达的边权不超过 $x$ 的结点等价于询问该结点的权值不超过 $x$ 的最远的祖先结点的子树。 | + | 如果 $b_4=0$，则 $\text{ans}\oplus b\in[d_1d_2d_3100,d_1d_2d_3111]$。而 $a=\text{ans}\oplus b-x$，于是主席树查询即可。 |
| - | + | ||
| - | 于是倍增求出满足条件的祖先结点，最后利用 $\text{dfs}$ 序和主席树处理第 $k$ 大询问即可。时间复杂度 $O((n+q)\log n+m\log m)$。 | + | |
| - | + | ||
| - | 另外这题可以以离线询问，将询问和边然后按权值排序，然后通过线段树合并处理加边操作和询问操作。 | + | |
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #define rch(k) node[node[k].ch[1]] | + | const int MAXN=2e5+5,MAXM=17,MAXV=1e5; |
| - | const int MAXN=1e5+5,MAXM=5e5+5,MAXL=80; | + | int root[MAXN],node_cnt; |
| struct Node{ | struct Node{ | ||
| - | int s,ch[2]; | + | int ch[2],sz; |
| - | }node[MAXN*MAXL]; | + | }node[MAXN*40]; |
| - | int root[MAXN<<1],n,seg_n,node_cnt; | + | void update(int &k,int p,int pos,int lef=0,int rig=MAXV){ |
| - | void update(int &k,int p,int pos,int lef=1,int rig=seg_n){ | + | |
| node[k=++node_cnt]=node[p]; | node[k=++node_cnt]=node[p]; | ||
| - | node[k].s++; | + | node[k].sz++; |
| if(lef==rig)return; | if(lef==rig)return; | ||
| int mid=lef+rig>>1; | int mid=lef+rig>>1; | ||
| - | if(pos<=mid) | + | if(mid>=pos) |
| update(node[k].ch[0],node[p].ch[0],pos,lef,mid); | update(node[k].ch[0],node[p].ch[0],pos,lef,mid); | ||
| else | else | ||
| update(node[k].ch[1],node[p].ch[1],pos,mid+1,rig); | update(node[k].ch[1],node[p].ch[1],pos,mid+1,rig); | ||
| } | } | ||
| - | int query(int k1,int k2,int rk,int lef=1,int rig=seg_n){ | + | int query(int k1,int k2,int ql,int qr,int lef=0,int rig=MAXV){ |
| + | if(lef>qr||rig<ql)return 0; | ||
| + | if(ql<=lef&&rig<=qr)return node[k1].sz-node[k2].sz; | ||
| int mid=lef+rig>>1; | int mid=lef+rig>>1; | ||
| - | if(lef==rig)return mid; | + | return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig); |
| - | if(rk<=rch(k1).s-rch(k2).s) | + | |
| - | return query(node[k1].ch[1],node[k2].ch[1],rk,mid+1,rig); | + | |
| - | else | + | |
| - | return query(node[k1].ch[0],node[k2].ch[0],rk-rch(k1).s+rch(k2).s,lef,mid); | + | |
| - | } | + | |
| - | struct Edge{ | + | |
| - | int u,v,w; | + | |
| - | bool operator < (const Edge &b)const{ | + | |
| - | return w<b.w; | + | |
| - | } | + | |
| - | }edge[MAXM]; | + | |
| - | int a[MAXN],b[MAXN],p[MAXN<<1],ch[MAXN<<1][2],dfn[MAXN<<1][2],dfs_t; | + | |
| - | namespace LCA{ | + | |
| - | const int MAXN=2e5+5; | + | |
| - | int d[MAXN],anc[MAXN][MAXL],w[MAXN],log2[MAXN]; | + | |
| - | void get_log(int n){ | + | |
| - | int log=0; | + | |
| - | while((1<<log)<n){ | + | |
| - | for(int i=1<<log,j=min(1<<(log+1),n);i<j;i++) | + | |
| - | log2[i]=log; | + | |
| - | log++; | + | |
| - | } | + | |
| - | } | + | |
| - | void init(int n){ | + | |
| - | get_log(n); | + | |
| - | for(int j=1;(1<<j)<n;j++){ | + | |
| - | _rep(i,1,n){ | + | |
| - | if(!anc[i][j-1]) | + | |
| - | continue; | + | |
| - | anc[i][j]=anc[anc[i][j-1]][j-1]; | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | int query(int p,int k){ | + | |
| - | for(int i=log2[d[p]];i>=0;i--){ | + | |
| - | if(anc[p][i]&&w[anc[p][i]]<=k) | + | |
| - | p=anc[p][i]; | + | |
| - | } | + | |
| - | return p; | + | |
| - | } | + | |
| - | }; | + | |
| - | int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);} | + | |
| - | void dfs(int u,int fa,int dep){ | + | |
| - | if(!u)return; | + | |
| - | dfn[u][0]=++dfs_t;LCA::d[u]=dep; | + | |
| - | if(u<=n) | + | |
| - | update(root[dfs_t],root[dfs_t-1],a[u]); | + | |
| - | else | + | |
| - | root[dfs_t]=root[dfs_t-1]; | + | |
| - | dfs(ch[u][0],u,dep+1); | + | |
| - | dfs(ch[u][1],u,dep+1); | + | |
| - | dfn[u][1]=dfs_t; | + | |
| } | } | ||
| int main() | int main() | ||
| { | { | ||
| - | n=read_int(); | + | int n=read_int(),q=read_int(); |
| - | int m=read_int(),q=read_int(); | + | _rep(i,1,n) |
| - | _rep(i,1,n)a[i]=b[i]=read_int(); | + | update(root[i],root[i-1],read_int()); |
| - | sort(b+1,b+n+1); | + | while(q--){ |
| - | seg_n=unique(b+1,b+n+1)-b; | + | int b=read_int(),x=read_int(),l=read_int(),r=read_int(); |
| - | _rep(i,1,n)a[i]=lower_bound(b+1,b+seg_n,a[i])-b; | + | int ans=0; |
| - | _for(i,0,m){ | + | for(int i=MAXM;~i;i--){ |
| - | edge[i].u=read_int(); | + | int ql=((ans^b)>>(i+1))<<(i+1); |
| - | edge[i].v=read_int(); | + | if(b&(1<<i)){ |
| - | edge[i].w=read_int(); | + | if(query(root[r],root[l-1],ql-x,ql+(1<<i)-1-x)) |
| - | } | + | ans|=1<<i; |
| - | sort(edge,edge+m); | + | } |
| - | int cur=n+1; | + | else{ |
| - | _for(i,1,2*n)p[i]=i; | + | if(query(root[r],root[l-1],ql+(1<<i)-x,ql+(1<<(i+1))-1-x)) |
| - | _for(i,0,m){ | + | ans|=1<<i; |
| - | int x=Find(edge[i].u),y=Find(edge[i].v); | + | } |
| - | if(x!=y){ | + | |
| - | p[x]=p[y]=cur; | + | |
| - | ch[cur][0]=x,ch[cur][1]=y; | + | |
| - | LCA::anc[x][0]=LCA::anc[y][0]=cur,LCA::w[cur]=edge[i].w; | + | |
| - | cur++; | + | |
| } | } | ||
| - | } | + | enter(ans); |
| - | _for(i,1,cur){ | + | |
| - | if(!root[Find(i)]) | + | |
| - | dfs(Find(i),0,0); | + | |
| - | } | + | |
| - | LCA::init(cur-1); | + | |
| - | while(q--){ | + | |
| - | int v=read_int(),x=read_int(),k=read_int(); | + | |
| - | int rt=LCA::query(v,x); | + | |
| - | if(node[root[dfn[rt][1]]].s-node[root[dfn[rt][0]-1]].s<k) | + | |
| - | enter(-1); | + | |
| - | else | + | |
| - | enter(b[query(root[dfn[rt][1]],root[dfn[rt][0]-1],k)]); | + | |
| } | } | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/数据结构练习_1.1600341985.txt.gz · 最后更改: 2020/09/17 19:26 由 jxm2001
