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 "stdio.h"
#include "math.h"
#include "stdlib.h"
#include "memory.h"
#define NUM 100010
int N=0;
typedef struct Node
{
    int l;
    int r;
    int val;
    int flag;
}Node;
Node tree[4*NUM]={0, 0, 0, 0};
long long s[2*NUM]={0};
int ind[2*NUM]={0};
int sq[2*NUM]={0};
int res=0;
int Partition(int low, int high)    //类似半导体中一个空穴转移一个电子
{                                           //取第一个元素把数组分成小于和大于两部分
    // 随机选取中间数
    int p=rand()%(high-low+1)+low;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX