2020-2021:teams:legal_string:jxm2001:可持久化数据结构_3
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:可持久化数据结构_3 [2020/09/20 19:20] jxm2001 |
2020-2021:teams:legal_string:jxm2001:可持久化数据结构_3 [2020/09/20 19:30] (当前版本) jxm2001 [习题三] |
||
|---|---|---|---|
| 行 232: | 行 232: | ||
| 给定一个长度为 $n$ 的序列 $X$ 和长度为 $m$ 的序列 $Y$，定义矩阵元素 $A_{i,j}=X_i\oplus Y_j$，接下来 $q$ 个询问。 | 给定一个长度为 $n$ 的序列 $X$ 和长度为 $m$ 的序列 $Y$，定义矩阵元素 $A_{i,j}=X_i\oplus Y_j$，接下来 $q$ 个询问。 | ||
| - | 每次询问 $\max_{l_1\le i\le r_1,l_2\le j\le r_2}A_{i,j}$。 | + | 每次询问 $A_{i,j}(l_1\le i\le r_1,l_2\le j\le r_2)$ 第 $k$ 大。数据保证 $n\le 1000,m\le 300000,q\le 500$。 |
| === 题解 === | === 题解 === | ||
| + | 对序列 $Y$ 建字典树，差分维护区间结点个数。每次询问时同时对序列 $X_i(l_1\le r_1)$ 跳字典树。 | ||
| + | 考虑按位贪心，先查询异或结果为 $1$ 的结点个数，根据结点个数考虑跳边方向。时间复杂度 $O((nq+m)\log v)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e3+5,MAXM=3e5+5,MAXL=31; | ||
| + | struct Node{ | ||
| + | int ch[2],sz; | ||
| + | }node[MAXM*40]; | ||
| + | int root[MAXM],node_cnt; | ||
| + | void Insert(int &k,int p,int v){ | ||
| + | int pos=k=++node_cnt; | ||
| + | for(int i=MAXL-1;~i;i--){ | ||
| + | int dir=(v>>i)&1; | ||
| + | node[pos].ch[!dir]=node[p].ch[!dir]; | ||
| + | node[pos].ch[dir]=++node_cnt; | ||
| + | pos=node[pos].ch[dir]; | ||
| + | p=node[p].ch[dir]; | ||
| + | node[pos].sz=node[p].sz+1; | ||
| + | } | ||
| + | } | ||
| + | int x[MAXN],y[MAXM],cur_pos[MAXN][2]; | ||
| + | int query(int l1,int r1,int l2,int r2,int rk){ | ||
| + | int ans=0; | ||
| + | _rep(i,l1,r1){ | ||
| + | cur_pos[i][0]=root[r2]; | ||
| + | cur_pos[i][1]=root[l2-1]; | ||
| + | } | ||
| + | for(int i=MAXL-1;~i;i--){ | ||
| + | int cnt=0; | ||
| + | _rep(j,l1,r1){ | ||
| + | int dir=((x[j]>>i)&1)^1; | ||
| + | cnt+=node[node[cur_pos[j][0]].ch[dir]].sz-node[node[cur_pos[j][1]].ch[dir]].sz; | ||
| + | } | ||
| + | int flag=cnt>=rk; | ||
| + | if(flag) | ||
| + | ans|=1<<i; | ||
| + | else | ||
| + | rk-=cnt; | ||
| + | _rep(j,l1,r1){ | ||
| + | int dir=((x[j]>>i)&1)^flag; | ||
| + | cur_pos[j][0]=node[cur_pos[j][0]].ch[dir]; | ||
| + | cur_pos[j][1]=node[cur_pos[j][1]].ch[dir]; | ||
| + | } | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,n)x[i]=read_int(); | ||
| + | _rep(i,1,m){ | ||
| + | y[i]=read_int(); | ||
| + | Insert(root[i],root[i-1],y[i]); | ||
| + | } | ||
| + | int q=read_int(); | ||
| + | while(q--){ | ||
| + | int l1=read_int(),r1=read_int(),l2=read_int(),r2=read_int(); | ||
| + | enter(query(l1,r1,l2,r2,read_int())); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/可持久化数据结构_3.1600600830.txt.gz · 最后更改: 2020/09/20 19:20 由 jxm2001
