2020-2021:teams:legal_string:jxm2001:数据结构练习_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/09/16 22:54] 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$ 大的权值。 | + | |
| === 题解 === | === 题解 === | ||
| + | |||
| + | 考虑按高位到低位贪心枚举。假设当前枚举到第 $4$ 为，答案 $\text{ans}=c_1c_2c_3???,b=b_1b_2b_3b_4??$。 | ||
| + | |||
| + | 优先考虑是否可以使 $\text{ans}=c_1c_2c_31??$，如果 $b_4=1$，则 $\text{ans}\oplus b\in[d_1d_2d_3000,d_1d_2d_3011]$。 | ||
| + | |||
| + | 如果 $b_4=0$，则 $\text{ans}\oplus b\in[d_1d_2d_3100,d_1d_2d_3111]$。而 $a=\text{ans}\oplus b-x$，于是主席树查询即可。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5,MAXM=17,MAXV=1e5; | ||
| + | int root[MAXN],node_cnt; | ||
| + | struct Node{ | ||
| + | int ch[2],sz; | ||
| + | }node[MAXN*40]; | ||
| + | void update(int &k,int p,int pos,int lef=0,int rig=MAXV){ | ||
| + | node[k=++node_cnt]=node[p]; | ||
| + | node[k].sz++; | ||
| + | if(lef==rig)return; | ||
| + | int mid=lef+rig>>1; | ||
| + | if(mid>=pos) | ||
| + | update(node[k].ch[0],node[p].ch[0],pos,lef,mid); | ||
| + | else | ||
| + | update(node[k].ch[1],node[p].ch[1],pos,mid+1,rig); | ||
| + | } | ||
| + | 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; | ||
| + | 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); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),q=read_int(); | ||
| + | _rep(i,1,n) | ||
| + | update(root[i],root[i-1],read_int()); | ||
| + | while(q--){ | ||
| + | int b=read_int(),x=read_int(),l=read_int(),r=read_int(); | ||
| + | int ans=0; | ||
| + | for(int i=MAXM;~i;i--){ | ||
| + | int ql=((ans^b)>>(i+1))<<(i+1); | ||
| + | if(b&(1<<i)){ | ||
| + | if(query(root[r],root[l-1],ql-x,ql+(1<<i)-1-x)) | ||
| + | ans|=1<<i; | ||
| + | } | ||
| + | else{ | ||
| + | if(query(root[r],root[l-1],ql+(1<<i)-x,ql+(1<<(i+1))-1-x)) | ||
| + | ans|=1<<i; | ||
| + | } | ||
| + | } | ||
| + | enter(ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/数据结构练习_1.1600268094.txt.gz · 最后更改: 2020/09/16 22:54 由 jxm2001
