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
#define _CRT_SECURE_NO_WARNINGS
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<limits.h>
#include<set>
using namespace std;
const int maxn = 100001;
// splay
struct Node{
    Node *ch[2];
    int r;      // 优先级，数值越大，优先级越高
    int v;      // 值
    int s,addv,mx;      // 需要维护的值
    // mx是当前结点为根的子树中结点最大值，addv是对当前结点为根的子树所有区间操作。
    bool operator < (const Node& rhs) const{
        return  r < rhs.r;
    }
    int cmp( int x ) const { // isLessThan
        if( x == v ) return -1;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX