6308.中间值

input:median.in output:median.out

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

Input

Output

Sample Input

1
2
3
4
5
6
7
8
5 5
12 41 46 68 69
35 61 82 84 96
2 1 4 3 5
1 0 5 75
2 2 4 3 4
2 3 4 1 5
2 1 4 2 4

Sample Output

1
2
3
4
68
68
68
61

Data Constraint

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define IL inline
#define RI register int
using namespace std;
const int N=5e5;
IL bool num(char ch){
return '0'<=ch&&ch<='9';
}
IL void read(int &x){
char ch;
while(!num(ch=getchar()));
x=ch-'0';
while(num(ch=getchar()))
x=(x<<3)+(x<<1)+ch-'0';
}
IL void write(int x){
int s[13],k=0;
while(x>0){
s[++k]=x%10; x/=10;
}
do
putchar(s[k]+'0');
while(--k);
}
IL void read(int &p1,int &p2){
read(p1);
read(p2);
}
IL void read(int &p1,int &p2,int &p3){
read(p1);
read(p2);
read(p3);
}
IL void read(int &p1,int &p2,int &p3,int &p4){
read(p1);
read(p2);
read(p3);
read(p4);
}
IL void writeln(int x){
write(x);
putchar('\n');
}
int n,m,a[N+3],b[N+3];
IL int find(int *a,int l,int r,int k){
return (l+k-1)>r?r:(l+k-1);
}
int sol(int l1,int r1,int l2,int r2,int k){
if(l1>r1)
return b[l2+k-1];
if(l2>r2)
return a[l1+k-1];
if(k==1)
return min(a[l1],b[l2]);
int x=find(a,l1,r1,k>>1);
int y=find(b,l2,r2,k>>1);
if(a[x]<b[y])
return sol(x+1,r1,l2,r2,k-(x-l1+1));
return sol(l1,r1,y+1,r2,k-(y-l2+1));
}
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
read(n,m);
for(RI i=1;i<=n;i++)
read(a[i]);
for(RI i=1;i<=n;i++)
read(b[i]);
int opt,p1,p2,p3,p4;
for(RI i=1;i<=m;i++){
int opt;
read(opt);
if(opt==1){
read(p1,p2,p3);
if(p1==0)
a[p2]=p3;
else
b[p2]=p3;
}
else {
read(p1,p2,p3,p4);
writeln(sol(p1,p2,p3,p4,(p2-p1+p4-p3+3)>>1));
}
}
return 0;
}
暗影 微信

微信