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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#define pii pair< int, int >
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn = 500*600;
const int inf = 0x3f3f3f3f;
int N, M, K;
int num[maxn], pre[maxn], cnt, suf[maxn];
//int getloc(int a) { return lower_bound(snum+1,snum+1+N,a)-snum;  }
int tree[maxn*20], lc[maxn*20], rc[maxn*20], sum[maxn*20];
int build(int l,int r)
{
    int root=cnt++;
    sum[root]=0;
    if(l==r) return root;
    int m=(l+r)/2;
    lc[root]=build(l,m);
    rc[root]=build(m+1,r);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX