2020-2021:teams:legal_string:jxm2001:数据结构练习_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/09/16 22:14] 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)$ 个点。 | ||
| 行 746: | 行 748: | ||
| 于是考虑将每个结点的权值设为该结点的子树大小减一，于是贡献和为所有深度为 $[d_a+1,d_a+k]$ 且 $\text{dfs}$ 序属于 $a$ 的子树的结点的权值和。 | 于是考虑将每个结点的权值设为该结点的子树大小减一，于是贡献和为所有深度为 $[d_a+1,d_a+k]$ 且 $\text{dfs}$ 序属于 $a$ 的子树的结点的权值和。 | ||
| - | 于是问题转化为二维偏序统计问题，考虑主席树统计答案。时间复杂度 $O((n+q)\log n)$。 | + | 于是问题转化为二维偏序问题，考虑主席树统计答案。时间复杂度 $O((n+q)\log n)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 806: | 行 808: | ||
| int p=read_int(),k=read_int(),u=dfn[p]; | int p=read_int(),k=read_int(),u=dfn[p]; | ||
| enter(1LL*(sz[u]-1)*min(d[u]-1,k)+query(root[u+sz[u]-1],root[u],d[u],min(d[u]+k,n))); | enter(1LL*(sz[u]-1)*min(d[u]-1,k)+query(root[u+sz[u]-1],root[u],d[u],min(d[u]+k,n))); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | |||
| + | ==== 习题五 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P3293|洛谷p3293]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定长度为 $n$ 的序列 $a$ 和 $q$ 个询问。每次询问给定 $b,x,l,r$，输出 $\max_{l\le i\le r}(b\oplus(a_i+x))$。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 考虑按高位到低位贪心枚举。假设当前枚举到第 $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; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/数据结构练习_1.1600265677.txt.gz · 最后更改: 2020/09/16 22:14 由 jxm2001
