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
9
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;
}