数据结构 【树状数组】 【线段树】 【珂朵莉树】

发表于 更新于 分类于

数据结构

树状数组、线段树、珂朵莉树

一.区间合并

1.AcWing245你能回答这些问题吗

img
img
分析：

线段树。维护四个变量，即可实现区间合并。

mx 区间最大连续子段和

mx_l 以区间左端点为左界的最大连续字段和

mx_r 以区间左端点为左界的最大连续字段和

sum 区间和

AC代码:

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
87
88
#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
int n, m;
int ar[500050];
struct node
{
    int l, r;
    int mx, mx_l, mx_r, sum;
}tree[2000050];
int op, x, y;

void pushup(node &a, node &b, node &c)
{
    a.mx = max(max(b.mx, c.mx), b.mx_r + c.mx_l);
    a.mx_l = max(b.mx_l, b.sum + c.mx_l);
    a.mx_r = max(c.mx_r, c.sum + b.mx_r);
    a.sum = b.sum + c.sum;
}

void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;

    if(l == r)
    {
        tree[p].mx = tree[p].mx_l = tree[p].mx_r = tree[p].sum = ar[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

node query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r) return tree[p];

    int mid = (tree[p].l + tree[p].r) >> 1;
    if(r <= mid) return query(p<<1, l, r);
    else if(l > mid) return query(p<<1|1, l, r);
    else
    {
        node left = query(p<<1, l, r);
        node right = query(p<<1|1, l, r);
        node res;
        pushup(res, left, right);
        return res;
    }
}

void updata(int p, int x, int y)
{
    if(tree[p].l == tree[p].r) tree[p].mx = tree[p].mx_l = tree[p].mx_r = tree[p].sum = y;
    else
    {
        int mid = (tree[p].l + tree[p].r) >> 1;
        if(mid >= x) updata(p<<1, x, y);
        else updata(p<<1|1, x, y);
        pushup(tree[p], tree[p<<1], tree[p<<1|1]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);

    build(1, 1, n);

    while(m--)
    {
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1)
        {
            if(x > y) swap(x, y);
            printf("%d\n", query(1, x, y).mx);
        }
        else updata(1, x, y);
    }

    return 0;
}

2.Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma

img
img
题意：

长度为n的数组，q次询问，每次询问三个参数op,x,y

op==1,ar[x]=y;

op==2,查询区间内有多少个不降的子数组。

分析：

同上一个题一样，除了维护询问的属性sum以外,再维护子数组左右边界分别为区间边界时最长的长度len_l,len_r,，以及区间长度len,即可实现区间合并。

AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int n, q;
ll ar[200050];
struct node
{
    int l, r;
    ll len_l, len_r, sum, len;

//    void print()
//    {
//        cout << l << ' ' << r << ' ' << len_l << ' ' << len_r << ' ' << sum << ' ' << len << '\n';
//    }
}tree[800050];
int op;
ll x, y;

ll calc(ll n)
{
    return (1ll + n) * n / 2ll;
}

void pushup(node &p, node &le, node &ri)
{
    p.l = le.l;
    p.r = ri.r;
    if(ar[le.r] <= ar[ri.l])
    {
        p.sum = le.sum + ri.sum - calc(le.len_r) - calc(ri.len_l) + calc(le.len_r + ri.len_l);

        if(le.len == le.len_l) p.len_l = le.len + ri.len_l;
        else p.len_l = le.len_l;

        if(ri.len_r == ri.len) p.len_r = ri.len + le.len_r;
        else p.len_r = ri.len_r;

        p.len = le.len + ri.len;
    }
    else
    {
        p.sum = le.sum + ri.sum;
        p.len_l = le.len_l;
        p.len_r = ri.len_r;
        p.len = le.len + ri.len;
    }
}

void pushup(int p)
{
    pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;

    if(l == r)
    {
        tree[p].len_l = tree[p].len_r = tree[p].sum = tree[p].len = 1;
        return ;
    }

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int pos, ll y)
{
    if(tree[p].l == tree[p].r) ar[pos] = y;
    else
    {
        int mid = (tree[p].l + tree[p].r) >> 1;
        if(mid >= x) updata(p<<1, pos, y);
        else updata(p<<1|1, pos, y);
        pushup(p);
    }
}

node query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        //tree[p].print();
        return tree[p];
    }

    int mid = (tree[p].l + tree[p].r) >> 1;
    if(r <= mid) return query(p<<1, l, r);
    else if(l > mid) return query(p<<1|1, l, r);
    else
    {
        node res;
        node left = query(p<<1, l, r);
        node right = query(p<<1|1, l, r);
        pushup(res, left, right);
        //res.print();
        return res;
    }

}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> ar[i];

    build(1, 1, n);

//    for(int i = 1; i <= n * 4; ++i)
//    {
//        cout << i << ' ' ;
//        tree[i].print();
//    }

    while(q--)
    {
        cin >> op >> x >> y;
        if(op == 1) updata(1, x, y);
        else
        {
            //query(1, x, y).print();
            cout << query(1, x, y).sum << '\n';
        }
    }
    return 0;
}

二.珂朵莉树

牛客练习赛100 E 小红的公倍数(珂朵莉树)

img
img
分析：
  看题目特征，首先，题目数据随机生成，其次，存在区间推平操作，故可以考虑珂朵莉树。
  另外，需要注意 $lcm(a,b) \% mod \neq lcm(a\%mod, b)$。故直接维护区间lcm是行不通的，由此我们质因数分解，维护每个质因数在区间内最多出现多少次方。20000以内的质数个数不是很多，不到2300个，再考虑的推平操作，考虑使用珂朵莉树。（线段树的话，由于要开4倍的空间，所以还是有点卡的)
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vv;
#define itt set<node>::iterator
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

const int maxn = 20005;
const ll mod = 1e9 + 7;
int n, q, l, r, num;
ll ar[maxn];
struct node
{
    int l, r;
    vv vt;
    bool operator < (const node &b) const
    {
        return l < b.l;
    }
};
set<node> tree;
bool prime[maxn];
int Prime[maxn];
int pid[maxn];

void make_prime()
{
    memset(prime, true, sizeof(prime));
    memset(pid, -1, sizeof(pid));
    prime[0] = prime[1] = false;
    for(int i = 2; i <= maxn; i++)
    {
        if(prime[i])
        {
            Prime[num]=i;
            pid[i] = num++;
        }
        for(int j=0; j < num && i * Prime[j] < maxn; j++)
        {
            prime[i * Prime[j]] = false;
            if(!(i % Prime[j]))
                break;
        }
    }
}

ll pow_mod(ll a, ll n)
{
    ll ans = 1;
    a %= mod;
    while(n)
    {
        if(n & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

itt split(int pos)
{
    itt it = tree.lower_bound({pos, 0, {}});
    if(it != tree.end() && it -> l == pos) return it;

    --it;
    int l = it -> l;
    int r = it -> r;
    vector<int> v = it -> vt;
    tree.erase(it);
    tree.insert({l, pos - 1, v});
    return tree.insert({pos, r, v}).first;
}

void solve(int l, int r)
{
    itt itr = split(r + 1);
    itt itl = split(l);
//    cout << itl -> l << ' ' << itl -> r << '\n';
//    cout << itr -> l << ' ' << itr -> r << '\n';

    vector<int> vt(2300, 0);
    for(itt it = itl; it != itr; ++it)
    {
        //cout << it -> l << ' ' << it -> t << '\n';
        for(int i = 0; i < 2300; ++i)
        {
            vt[i] = max(vt[i], it->vt[i]);
            //cout << vt[i] <<
        }
    }

    ll ans = 1;
    for(int i = 0; i < 2300; ++i)
    {
        //cout << i << ' ' << vt[i] << ' ';
        ans = (ans * pow_mod(Prime[i], vt[i])) % mod;
        //cout << ans << '\n';
    }
    cout << ans << '\n';
    tree.erase(itl, itr);
    tree.insert(node{l, r, vt});
}

void print()
{
    for(itt it = tree.begin(); it != tree.end(); ++it)
    {
        cout << it -> l << ' ' << it -> r << '\n';
    }
}

signed main()
{
    io;
    make_prime();
//    for(int i = 0; i <= 100; ++i)
//    {
//        cout << i << ' ' << prime[i] << ' ' << Prime[i] << ' ' << pid[i] << '\n';
//    }

    cin >> n >> q;
    vector<int> vt(2300, 0);
    int cnt = 0;

    for(int i = 1; i <= n; ++i)
    {
        cin >> ar[i];
        vt.clear();
        vt = vector<int>(2300, 0);
        for(int j = 2; j * j <= ar[i]; ++j)
        {
            cnt = 0;
            while(ar[i] % j == 0)
            {
                ++cnt;
                ar[i] /= j;
            }
            if(pid[j] == -1) continue;
            vt[pid[j]] += cnt;
        }
        if(ar[i] > 1) ++vt[pid[ar[i]]];
        tree.insert(node{i, i, vt});
    }

    while(q--)
    {
        cin >> l >> r;
        solve(l, r);
        //print();
    }
    return 0;
}

三.区间操作

1.2022 ACM 湖北省赛 L (线段树)

题意：
输入长度为n的数组，q次询问，n个数字每个数字有两个权值，权值ar[i] (1 <= ar[i] <= 10^8),s[i](s[i]=0/1)。询问分为一下四种。
1 x : 将s[x]变成0，保证原来的 s[x] = 1
2 x : 将s[x]变成1，保证原来的 s[x] = 0
3 L R x : 给区间 [l,r] 中所有的s[i]=1的ar[i]都加上一个数
4 L R ： 输出区间 [l,r] 中的 ar[i] 的和
分析：
维护$\sum ar[i]$和$\sum s[i]$即可，由于是区间修改，所以还需要懒标记。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

const int maxn = 1e5 + 5;
int n, m;
int ar[maxn];
bool s[maxn];
struct node
{
    int l, r;
    int lazy_sum;
    int cnt, sum;

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << lazy_sum << ' ' << cnt << ' ' << sum << '\n';
    }
} tree[maxn<<2];
int op, l, r, x;

void pushup(int p)
{
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
    tree[p].cnt = tree[p<<1].cnt + tree[p<<1|1].cnt;
}

void pushdown(int p)
{
    tree[p<<1].sum += tree[p<<1].cnt * tree[p].lazy_sum;
    tree[p<<1].lazy_sum += tree[p].lazy_sum;
    tree[p<<1|1].sum += tree[p<<1|1].cnt * tree[p].lazy_sum;
    tree[p<<1|1].lazy_sum += tree[p].lazy_sum;
    tree[p].lazy_sum = 0;
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].lazy_sum = 0;

    if(l == r)
    {
        tree[p].sum = ar[l];
        tree[p].cnt = s[l];
        return ;
    }

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata1(int p, int pos)
{
    if(tree[p].l == tree[p].r)
    {
        tree[p].cnt ^= 1;
        return ;
    }

    if(tree[p].lazy_sum) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(pos <= mid) updata1(p<<1, pos);
    else updata1(p<<1|1, pos);
    pushup(p);
}

void updata2(int p, int l, int r, int x)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        tree[p].sum += tree[p].cnt * x;
        tree[p].lazy_sum += x;
        return ;
    }

    if(tree[p].lazy_sum) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) updata2(p<<1, l, r, x);
    if(r > mid) updata2(p<<1|1, l, r, x);
    pushup(p);
}

ll query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;

    if(tree[p].lazy_sum) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    ll res = 0;
    if(l <= mid) res = query(p<<1, l, r);
    if(r > mid) res += query(p<<1|1, l, r);

    return res;
}

signed main()
{
    io;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> ar[i];
    for(int i = 1; i <= n; ++i) cin >> s[i];

    build(1, 1, n);

//    for(int i = 1; i <= 3 * n; ++i)
//    {
//        cout << i << ' ';
//        tree[i].print();
//    }

    while(m--)
    {
        cin >> op;
        if(op == 1 || op == 2)
        {
            cin >> x;
            updata1(1, x);
//            for(int i = 1; i <= 7; ++i)
//            {
//                cout << i << ' ';
//                tree[i].print();
//            }
        }
        else if(op == 3)
        {
            cin >> l >> r >> x;
            updata2(1, l, r, x);
//            for(int i = 1; i <= 7; ++i)
//            {
//                cout << i << ' ';
//                tree[i].print();
//            }
        }
        else
        {
            cin >> l >> r;
            cout << query(1, l, r) << '\n';
//            for(int i = 1; i <= 7; ++i)
//            {
//                cout << i << ' ';
//                tree[i].print();
//            }
        }
    }

    return 0;
}

2.2022牛客寒假算法基础集训营4 B-进制 (线段树)

img
img
img
分析：
维护区间最大值，和作为i进制数的大小即可维护。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'

const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
struct node
{
    int l, r, mx;
    int ar[12];

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << mx << '\n';
        for(int i = 1; i <= 10; ++i) cout << ar[i] << ' ';
        cout << '\n';
    }
}tree[maxn<<2];
int n, q, op, x, y;
string s;
node ans;

ll pow_mod(ll a, ll n)
{
    ll ans = 1;
    a %= mod;
    while(n)
    {
        if(n & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

void pushup(node &p, node &le, node &ri)
{
    p.mx = max(le.mx, ri.mx);
    p.l = le.l;
    p.r = ri.r;
    for(int i = 1; i <= 10; ++i)
    {
        if(i <= p.mx) p.ar[i] = inf;
        else p.ar[i] = ((le.ar[i] * pow_mod(i, ri.r - ri.l + 1)) % mod + ri.ar[i]) % mod;
    }
}

void pushup(int p)
{
    pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;

    if(l == r)
    {
        tree[p].mx = s[l] - '0';
        for(int i = 1; i <= 10; ++i)
        {
            if(i <= tree[p].mx) tree[p].ar[i] = inf;
            else tree[p].ar[i] = tree[p].mx;
        }
        return ;
    }

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int x, int y)
{
    if(tree[p].l == tree[p].r)
    {
        tree[p].mx = y;
        for(int i = 1; i <= 10; ++i)
        {
            if(i <= tree[p].mx) tree[p].ar[i] = inf;
            else tree[p].ar[i] = tree[p].mx;
        }
        return ;
    }

    int mid = tree[p].mid();
    if(x <= mid) updata(p<<1, x, y);
    else updata(p<<1|1, x, y);
    pushup(p);
}

node query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r) return tree[p];

    int mid = tree[p].mid();
    if(mid >= r) return query(p<<1, l, r);
    else if(mid < l) return query(p<<1|1, l, r);
    else
    {
        node res;
        node le = query(p<<1, l, r);
        node ri = query(p<<1|1, l, r);
        pushup(res, le, ri);
        return res;
    }
}

signed main()
{
    io;

    cin >> n >> q;
    cin >> s;
    s = " " + s;

    build(1, 1, n);

//    for(int i = 1; i <= 9; ++i)
//    {
//        cout << i << ' ';
//        tree[i].print();
//    }

    while(q--)
    {
        cin >> op >> x >> y;
        if(op == 1) updata(1, x, y);
        else
        {
            ans = query(1, x, y);
            cout << ans.ar[ans.mx + 1] << '\n';
        }
    }

    return 0;
}

3.Codeforces Round #254 (Div. 1) C. DZY Loves Colors (线段树)

img
分析：
  维护区间权值和，区间的颜色，如果区间内颜色统一则区间修改，使用lazy标记，不统一则暴力单点修改。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator

const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
struct node
{
    int l, r;
    int color, sum, cnt;
    int lazy;
    bool flag;

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << color << ' ' << flag << ' ' << sum << ' '<< cnt << ' ' << lazy << '\n';
    }
}tree[maxn<<2];
int n, m, op, l, r, x;

void pushup(int p)
{
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
    tree[p].flag = false;
    tree[p].color = 0;
    if(tree[p<<1].flag && tree[p<<1|1].flag && tree[p<<1].color == tree[p<<1|1].color)
    {
        tree[p].flag = true;
        tree[p].color = tree[p<<1].color;
    }
}

void pushdown(int p)
{
    tree[p<<1].sum += tree[p<<1].cnt * tree[p].lazy;
    tree[p<<1].lazy += tree[p].lazy;
    tree[p<<1].color = tree[p].color;
    tree[p<<1|1].sum += tree[p<<1|1].cnt * tree[p].lazy;
    tree[p<<1|1].lazy += tree[p].lazy;
    tree[p<<1|1].color = tree[p].color;
    tree[p].lazy = 0;
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].cnt = r - l + 1;
    tree[p].lazy = 0;

    if(l == r)
    {
        tree[p].color = l;
        tree[p].flag = true;
        tree[p].sum = 0;
        return ;
    }

    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int l, int r, int x)
{
    if (tree[p].l > r || tree[p].r < l) return;
    if(l <= tree[p].l && tree[p].r <= r && tree[p].flag)
    {
        tree[p].sum += tree[p].cnt * abs(tree[p].color - x);
        tree[p].lazy += abs(tree[p].color - x);
        tree[p].color = x;
        return ;
    }

    if(tree[p].lazy) pushdown(p);
    updata(p<<1, l, r, x);
    updata(p<<1|1, l, r, x);
    pushup(p);
}

ll query(int p, int l, int r)
{
    if(tree[p].l > r || tree[p].r < l) return 0;
    if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;

    if(tree[p].lazy) pushdown(p);
    return query(p<<1, l, r) + query(p<<1|1, l, r);
}

signed main()
{
    io;

    cin >> n >> m;

    build(1, 1, n);

    while(m--)
    {
        cin >> op;
        if(op == 1)
        {
            cin >> l >> r >> x;
            updata(1, l, r, x);
        }
        else
        {
            cin >> l >> r;
            cout << query(1, l, r) << '\n';
        }
    }

    return 0;
}


四.推结论+数据结构

1.同济大学程序设计竞赛 G(离线+树状数组)

另外，这场比赛的D题 两串糖果，区间DP
img
img
分析：
  注意到数据范围，k>ar[i] ，那要么把ar[i]变成0，要么变成k。
  对于一次询问[l,r,k]。
  对于区间内满足ar[i] <= k/2的元素ar[i]，对答案的贡献是：$\sum ar[i]$
  对于剩下的元素ar[i]，对答案的贡献是：$cnt \times k - \sum ar[i]$。其中 $cnt$ 是区间内大于等于k/2的元素个数，假设cnt1是区间中满足ar[i]<=k/2的个数。则cnt = r - l + 1 - cnt1。
  对于上面的几个变量如何求解，我们可以先考虑下面这个问题。
  daimayuan464. 数数 【离线+离散化+树状数组】
  做完这个题，容易发现上面所说的cnt1就是这个题所求解的量，即区间内小于等于某个数的个数，而对于区间内小于等于某个数的数字之和，我们可以利用同样的方法求解，只需要再维护一颗树状数组，维护的是前缀和。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int maxn = 4e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int ar[maxn], pre[maxn];
struct node
{
    int k, x, id;
};
vector<node> vt[maxn];
int ans[maxn], ans_1[maxn], ans_2[maxn], ans_3[maxn];
//答案，区间内小于等于k/2的数字之和，区间内大于k/2的数字个数，区间内大于k/2的数字之和
vector<int> vv;
int tree[maxn];
int sum[maxn];
int t, n, q, l, r, h;
struct node1
{
    int l, r, k, id;
}ask[maxn];

int lowbit(int x)
{
    return (-x) & x;
}

void updata(int pos, int x)
{
    while(pos <= n + q)
    {
        ++tree[pos];
        sum[pos] += x;
        pos += lowbit(pos);
    }
}

pii get_sum(int pos)
{
    pii pi;
    pi.first = pi.second = 0;
    while(pos)
    {
        pi.first += tree[pos];
        pi.second += sum[pos];
        pos -= lowbit(pos);
    }
    return pi;
}

void work()
{
    cin >> n >> q;

    for(int i = 1; i <= n; ++i)
    {
        cin >> ar[i];
        pre[i] = pre[i - 1] + ar[i];
        vv.push_back(ar[i]);
    }

    for(int i = 1; i <= q; ++i)
    {
        cin >> l >> r >> h;
        ask[i].l = l;
        ask[i].r = r;
        ask[i].k = h;
        ask[i].id = i;
        vv.push_back(h / 2);
        vt[l - 1].push_back({-1, h / 2, i});
        vt[r].push_back({1, h / 2, i});
    }

    sort(vv.begin(), vv.end());
    vv.erase(unique(vv.begin(), vv.end()), vv.end());

    int id, pos;
    pii pi;
    for(int i = 1; i <= n; ++i)
    {
        pos = lower_bound(vv.begin(), vv.end(), ar[i]) - vv.begin() + 1;
        updata(pos, ar[i]);

        for(int j = 0; j < vt[i].size(); ++j)
        {
            id = vt[i][j].id;
            pos = lower_bound(vv.begin(), vv.end(), vt[i][j].x) - vv.begin() + 1;
            pi = get_sum(pos);
            ans_1[id] += vt[i][j].k * pi.second;
            ans_2[id] += vt[i][j].k * pi.first;
        }
    }

    for(int i = 1; i <= q; ++i)
    {
        ans[i] = ans_1[i];
        ans_2[i] = (ask[i].r - ask[i].l + 1) - ans_2[i];
        ans_2[i] = ans_2[i] * ask[i].k;
        ans_3[i] = pre[ask[i].r] - pre[ask[i].l - 1] - ans_1[i];
        ans[i] += ans_2[i] - ans_3[i];
        cout << ans[i] << '\n';
    }
}

signed main()
{
    //io;
    work();
    return 0;
}

2.daimayuan 喵 ~ 喵~ 喵 ~

img
分析：
  每次添加操作相当于添加一个区间，询问相当于问你与这个区间有交集的区间的个数。
  那么对于一次询问[L,R]相当于，与区间[1,R]有交集的区间个数cnt1减去完全在L-1及其左侧的区间个数cnt2。
  cnt1即在此之前有多少个小于等于R的 l
  cnt2即在此之前有多少个小于等于L - 1的r
  开两个树状数组维护即可。
AC代码：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int maxn = 4e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int n, m, op, l, r;
int sum1[maxn], sum2[maxn];

int lowbit(int x)
{
    return (-x) & x;
}

void updata1(int pos)
{
    while(pos <= n)
    {
        ++sum1[pos];
        pos += lowbit(pos);
    }
}

void updata2(int pos)
{
    while(pos <= n)
    {
        ++sum2[pos];
        pos += lowbit(pos);
    }
}

int get_sum1(int pos)
{
    int res = 0;
    while(pos)
    {
        res += sum1[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int get_sum2(int pos)
{
    int res = 0;
    while(pos)
    {
        res += sum2[pos];
        pos -= lowbit(pos);
    }
    return res;
}

signed main()
{
    io;
    cin >> n >> m;
    while(m--)
    {
        cin >> op >> l >> r;
        if(op == 1)
        {
            updata1(l);
            updata2(r);
        }
        else
        {
            cout << get_sum1(r) - get_sum2(l - 1) << '\n';
        }
    }
    return 0;
}

3.Educational Codeforces Round 126 (Rated for Div. 2) D. Progressions Covering

img
img
等差数列，结合差分，可以线段树维护

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int maxn = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int n, k;
int ar[maxn];
struct node
{
    int l, r;
    int sum, lazy, len;

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << sum << '\n';
    }
}tree[maxn<<2];

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].len = r - l + 1;
    tree[p].lazy = tree[p].sum = 0;

    if(l == r) return ;

    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

void pushdown(int p)
{
    tree[p<<1].sum += tree[p].lazy * tree[p<<1].len;
    tree[p<<1].lazy += tree[p].lazy;
    tree[p<<1|1].sum += tree[p].lazy * tree[p<<1|1].len;
    tree[p<<1|1].lazy += tree[p].lazy;
    tree[p].lazy = 0;
}

void pushup(int p)
{
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}

void updata(int p, int l, int r, int x)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        tree[p].sum += tree[p].len * x;
        tree[p].lazy += x;
        return ;
    }

    int mid = tree[p].mid();
    if(tree[p].lazy) pushdown(p);
    if(l <= mid) updata(p<<1, l, r, x);
    if(r > mid) updata(p<<1|1, l, r, x);
    pushup(p);
}

int query(int p, int l, int r)
{
    if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;

    int mid = tree[p].mid();
    int res = 0;
    if(tree[p].lazy) pushdown(p);
    if(l <= mid) res += query(p<<1, l, r);
    if(r > mid) res += query(p<<1|1, l, r);
    return res;
}

signed main()
{
    io;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> ar[i];

    build(1, 1, n);

    int sub, mx, cnt, ans = 0;
    for(int i = n; i > 0; --i)
    {
        sub = query(1, 1, i);
        ar[i] -= sub;
        if(ar[i] <= 0) continue;
        mx = min(i, k);
        cnt = (ar[i] + mx - 1) / mx;
        ans += cnt;
        updata(1, i - mx + 1, i, cnt);
    }

    cout << ans << '\n';

    return 0;
}

更简单的方法，深入理解一下等差数列，一个队列即可维护

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int maxn = 4e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int n, k, cnt, len;
int ar[maxn];
queue<pii> q;
int ans;

signed main()
{
    io;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> ar[i];

    int sum = 0, sum_cnt = 0;
    for(int i = n; i > 0; --i)
    {
        sum -= sum_cnt;
        ar[i] -= sum;
        if(ar[i] > 0)
        {
            len = min(i, k);
            cnt = (ar[i] + len - 1ll) / len;
            q.push({i - len + 1ll, cnt});
            sum += len * cnt;
            sum_cnt += cnt;
            ans += cnt;
        }
        if(q.front().first == i)
        {
            sum -= q.front().second;
            sum_cnt -= q.front().second;
            q.pop();
        }
    }

    cout << ans << '\n';

    return 0;
}

五.dp/思维+数据结构

1.最长上升子序列计数（Bonus）(DP/线段树/树状数组)

img
img
分析：
  对于数据没加强版
  直接暴力dp即可，代码长这个样子。
img
  一方面，我们需要优化这份代码，另一方面我们需要根据这个的递推确定如何利用一些数据结构递推，维护什么样的数据结构。
  很明显需要优化j那个循环，即对于每个位置i，我们需要快速的找到前面的dp最大值，和其对应的子序列数量。
  做法是，进行离散化，维护的是以i（离散化后）为结尾的最长上升子序列长度，和数量。
  对于i(离散化后)，我们要求解是就需要query(1,i-1)，据此递推，主要确定sum的递推，是直接覆盖还是累加，另外，初识化和边界也是特别难调的。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int maxn = 4e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int n;
int ar[maxn], dp[maxn], sum[maxn];
vector<int> vt;
int ans;
struct node
{
    int l, r;
    int mx_len, sum;

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << mx_len << ' ' << sum << '\n';
    }
} tree[maxn<<2];

void pushup(node &p, node &le, node &ri)
{
    p.l = le.l;
    p.r = ri.r;
    p.mx_len = max(le.mx_len, ri.mx_len);
    p.sum = 0;
    if(le.mx_len == p.mx_len) p.sum = (p.sum + le.sum) % mod;
    if(ri.mx_len == p.mx_len) p.sum = (p.sum + ri.sum) % mod;
}

void pushup(int p)
{
    pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].mx_len = tree[p].sum = 0;

    if(l == r) return ;
    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

void updata(int p, int pos, int len, int num)
{
    if(tree[p].l == tree[p].r)
    {
        tree[p].mx_len = len;
        tree[p].sum = num;
        return ;
    }

    int mid = tree[p].mid();
    if(pos <= mid) updata(p<<1, pos, len, num);
    else updata(p<<1|1, pos, len, num);
    pushup(p);
}

node query(int p, int l, int r)
{
    if(l > r) return {0, 0, 0, 0};
    if(l <= tree[p].l && tree[p].r <= r) return tree[p];

    int mid = tree[p].mid();
    if(r <= mid) return query(p<<1, l, r);
    else if(l > mid) return query(p<<1|1, l, r);
    else
    {
        node res;
        node le = query(p<<1, l, r);
        node ri = query(p<<1|1, l, r);
        pushup(res, le, ri);
        return res;
    }
}

signed main()
{
    io;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> ar[i];
        vt.push_back(ar[i]);
    }

    build(1, 1, n);

    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());

    int pos;
    node pp;
    for(int i = 1; i <= n; ++i)
    {
        pos = lower_bound(vt.begin(), vt.end(), ar[i]) - vt.begin() + 1;
        dp[pos] = max(1ll, dp[pos]);
        sum[pos] = max(0ll, sum[pos]);
        pp = query(1, 1, pos - 1);
        if(pp.mx_len + 1 == 1)
        {
            dp[pos] = 1;
            ++sum[pos];
        }
        else if(dp[pos] < pp.mx_len + 1)
        {
            dp[pos] = pp.mx_len + 1;
            sum[pos] = pp.sum;
        }
        else if(dp[pos] == pp.mx_len + 1) sum[pos] = (sum[pos] + pp.sum) % mod;
        updata(1, pos, dp[pos], sum[pos]);
    }

    cout << query(1, 1, n).sum << '\n';

    return 0;
}

2.Codeforces Round #783 (Div. 2) D. Optimal Partition 【dp+线段树】

题意：
img
分析：
  首先，很容易想到暴力的dp。
  定义dp[i]为将1~i分完的最大值，状态转移方程dp[i] = max(dp[i], dp[j] + sign(sum[j, i]) * (i - (j + 1) + 1)),复杂度是$O(n^2)$，考虑优化。
  将方程具体写开
if(sum[j] == sum[i]) dp[i] = max(dp[i], dp[j]);
if(sum[j] > sum[i]) dp[i] = max(dp[i], dp[j] + j - i);
if(sum[j] < sum[i]) dp[i] = max(dp[i],dp[j] - j + i);
  即对于dp[i]
我们需要所有满足sum[j] == sum[i]的max(dp[j])
所有满足sum[j] > sum[i]的max(dp[j] + j)
所有满足sum[j] < sum[i]的max(dp[j] - j)
  dp[i]可以由上面的3个值转移过来。
  需要离散化，维护三个区间最大值即可。复杂度$O(nlogn)$。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int t, n, x;
int sum[maxn];
int dp[maxn];
vector<int> vt;
struct node
{
    int l, r;
    int dp, dp1, dp2;

    int mid()
    {
        return (l + r) >> 1;
    }

    void print()
    {
        cout << l << ' ' << r << ' ' << dp << ' ' << dp1 << ' ' << dp2 << '\n';
    }
} tree[maxn<<2];

void pushup(node &p, node &le, node &ri)
{
    p.l = le.l;
    p.r = ri.r;
    p.dp = max(le.dp, ri.dp);
    p.dp1 = max(le.dp1, ri.dp1);
    p.dp2 = max(le.dp2, ri.dp2);
}

void pushup(int p)
{
    pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;

    if(l == r)
    {
        tree[p].dp = tree[p].dp1 = tree[p].dp2 = -inf;
        return ;
    }

    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int pos, int dp, int id)
{
    if(tree[p].l == tree[p].r)
    {
        tree[p].dp = max(tree[p].dp, dp);
        tree[p].dp1 = max(tree[p].dp1, dp - id);
        tree[p].dp2 = max(tree[p].dp2, dp + id);
        return ;
    }

    int mid = tree[p].mid();
    if(pos <= mid) updata(p<<1, pos, dp, id);
    else updata(p<<1|1, pos, dp, id);
    pushup(p);
}

node query(int p, int l, int r)
{
    if(l > r) return {-inf, -inf, -inf, -inf};
    if(l <= tree[p].l && tree[p].r <= r) return tree[p];

    int mid = tree[p].mid();
    if(mid >= r) return query(p<<1, l, r);
    else if(mid < l) return query(p<<1|1, l, r);
    else
    {
        node le = query(p<<1, l, r);
        node ri = query(p<<1|1, l, r);
        node res;
        pushup(res, le, ri);
        return res;
    }
}

signed main()
{
    io;
    cin >> t;
    while(t--)
    {
        vt.clear();
        cin >> n;
        for(int i = 1; i <= n; ++i)
        {
            cin >> x;
            sum[i] = sum[i - 1] + x;
            vt.push_back(sum[i]);
            dp[i] = 0;
        }
        vt.push_back(0);

        sort(vt.begin(), vt.end());
        vt.erase(unique(vt.begin(), vt.end()), vt.end());

        build(1, 1, vt.size());

        node pp;
        int mx1, mx2, mx3, pos;
        pos = lower_bound(vt.begin(), vt.end(), 0) - vt.begin() + 1;
        updata(1, pos, 0, 0);
        for(int i = 1; i <= n; ++i)
        {
            pos = lower_bound(vt.begin(), vt.end(), sum[i]) - vt.begin() + 1;
            mx1 = query(1, 1, pos - 1).dp1;
            mx2 = query(1, pos, pos).dp;
            mx3 = query(1, pos + 1, vt.size()).dp2;
            dp[i] = max(mx1 + i, max(mx2, mx3 - i));
            updata(1, pos, dp[i], i);
        }

        cout << dp[n] << '\n';
    }
    return 0;
}

3.Codeforces Round #609 (Div. 1) C. K Integers

题意：
img
分析：
  很明显答案分为两部分，一是对应区间的逆序对的个数cnt1，二是将不应该存在的数字移出去区间最少需要操作多少次cnt2（等于将这k个数字挤在一起最少需要操作多少次）。
  cnt1即求逆序对，树状数组维护即可。
  对于cnt2,我们考虑将这k个数字挤在一起最少需要操作多少次。
  假设1~k这k个数的位置中，中间那个数字的位置是mid，mid及其左侧一共cnt个数字。
  对于mid左侧的第1个数字，需要移动到mid,需要mid-pos1次操作 （posi表示mid左侧第i个数字的位置）
  第2个，需要移动到mid-1的位置，需要mid-1-pos2次操作
  第3个，需要移动到mid-1的位置，需要mid-1-pos3次操作
  则左侧一共需要的操作次数是$mid \times cnt - cnt \times (cnt - 1) / 2 - \sum_{i=1}^{cnt} posi$
  右侧同理。
  利用两个树状数组即可维护。
AC代码：

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set<node>::iterator
#define pii pair<int,int>

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
int t, n, x;
int ar[maxn];
int pos[maxn];
int ans[maxn];
int tree1[maxn], tree2[maxn];

int lowbit(int x)
{
    return (-x) & x;
}

void updata(int x)
{
    int i = x;
    while(i <= n)
    {
        tree1[i]++;
        tree2[i] += x;
        i += lowbit(i);
    }
}

int get_cnt(int x)
{
    int res = 0;
    while(x)
    {
        res += tree1[x];
        x -= lowbit(x);
    }
    return res;
}

int get_sum(int x)
{
    int res = 0;
    while(x)
    {
        res += tree2[x];
        x -= lowbit(x);
    }
    return res;
}

int binary_find(int x)
{
    int r = n, l = 1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(get_cnt(mid) >= x) r = mid - 1;
        else l = mid + 1;
    }
    return r + 1;
}

signed main()
{
    io;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> ar[i];
        pos[ar[i]] = i;
    }

    ans[1] = 0;
    updata(pos[1]);
    int mid, cnt, sum, pre = 0;

    for(int i = 2; i <= n; ++i)
    {
        ans[i] += pre;
        ans[i] += get_cnt(n) - get_cnt(pos[i]);
        pre = ans[i];
        updata(pos[i]);
        cnt = (i + 1ll) / 2ll;
        mid = binary_find(cnt);
        sum = get_sum(mid);
        ans[i] += cnt * mid - cnt * (cnt - 1ll) / 2ll - sum;
        cnt = i - cnt;
        sum = get_sum(n) - get_sum(mid);
        ans[i] += sum - cnt * (mid + 1ll) - cnt * (cnt - 1ll) / 2ll;
    }

    for(int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}