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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
struct node {
    int key;
    int siz;
    int val;
    int add;
    LL sum;
    node* lson;
    node* rson;
    int cmp(int x) {
        int cnt = lson->siz + 1;
        if( x == cnt ) return -1;
        return x < cnt? 0: 1;
    }
    void pushdown() {
        if( !add ) return;
        lson->update(add);
        rson->update(add);
        add = 0;
    }
    void update(int add) {
        if( this->lson == NULL ) return;
        this->add += add;
        this->val += add;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX