树状数组套权值线段数

Posted on | In ,

码量预警

我们常常使用可持久化线段树来二分求得区间第k大，但是主席树只能应对没有修改的情况，一旦有修改，修改量对于主席树来说将是灾难性的打击。所以我们不能直接修改后面每一棵线段树。
处理区间问题我们最常用的套路之一不就是树状数组么，所以我们在这里用树状数组优化出一个log，虽说还是复杂度有点爆炸，但是已经够用了。

树状数组每个点代表一个权值线段树，这棵权值线段树我们也不需要全部建出来，只需要log个点。

虽然叫作带修主席树，但他和主席树本质是不一样的，它的思想更像是原本的若干棵权值线段树，每棵树并非承接上一个，而是独立一棵，没有儿子共享的问题。

趁着今天大概还明白它是什么东西，赶紧记录一下。

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
const int M = 1e4 * 2 + N;
int n, m;

struct query
{
    int x, y, k, type, id;
}q[M];

int a[N], sum[N];

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

void update(int x, int val)
{
    while (x <= n)
    {
        sum[x] += val;
        x += lowbit(x);
    }
}

int get(int x)
{
    if (x == 0)
        return 0;
    int ans = 0;
    while (x)
    {
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}
int maxnum, tot = 0;
char op[5];

query q1[M], q2[M];
int ans[M];
bool is[M];

void init()
{
    memset(sum, 0, sizeof(sum));
    memset(ans, 0, sizeof(ans));
    memset(is, 0, sizeof(is));
    return;
}

void solve(int head, int tail, int l, int r)
{
    if (head > tail)
    {
        return;
    }
/*
    printf("l , r , %d %d\n", l, r);
    for (int i = head; i <= tail; i++)
    {
        printf("query %d %d %d %d %d\n", q[i].x, q[i].y, q[i].k, q[i].type, q[i].id);
    }
*/
    if (l == r)
    {
        for (int i = head; i <= tail; i++)
        {
            if(q[i].type == 2)
            {
                is[q[i].id] = 1;
                ans[q[i].id] = l;
            }
        }
        return;
    }
    int mid = l + r >> 1;
    int f = 0, s = 0;
    for (int i = head; i <= tail; i++)
    {
        if (q[i].type == 1)
        {
            if (q[i].y <= mid)
            {
                update(q[i].x, q[i].k);
                q1[++f] = q[i];
            }
            else
            {
                q2[++s] = q[i];
            }
        }
        if (q[i].type == 2)
        {
            int ss = get(q[i].y) - get(q[i].x - 1);
            // printf("ss   && %d %d\n", get(q[i].y), get(q[i].x - 1));
            if (ss >= q[i].k)
            {
                q1[++f] = q[i];
            }
            else
            {
                q[i].k -= ss;
                q2[++s] = q[i];
            }
        }
    }
    for (int i = 1; i <= f; i++)
        if (q1[i].type == 1)
            update(q1[i].x, -q1[i].k);
    int qpos = head;
    for (int i = 1; i <= f; i++, qpos++)
        q[qpos] = q1[i];
    for (int i = 1; i <= s; i++, qpos++)
        q[qpos] = q2[i];
    solve(head, head + f - 1, l, mid);
    solve(head + f, tail, mid + 1, r);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out1.txt", "w", stdout);
    #endif

    int T;
    scanf("%d", &T);
    while (T--)
    {
        init();
        scanf("%d%d", &n, &m);
        maxnum = 0;
        tot = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            maxnum = max(maxnum, a[i]);
            q[++tot].x = i;
            q[tot].y = a[i];
            q[tot].k = 1;
            q[tot].type = 1;
            q[tot].id = tot;
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%s", op);
            int x, y;
            scanf("%d%d", &x, &y);
            if (op[0] == 'Q')
            {
                q[++tot].type = 2;
                int k;
                scanf("%d", &k);
                q[tot].x = x, q[tot].y = y;
                q[tot].k = k;
                q[tot].id = tot;
            }
            else
            {
                q[++tot].type = 1;
                q[tot].x = x;
                q[tot].y = a[x];
                q[tot].k = -1;
                q[tot].id = tot;

                q[++tot].type = 1;
                q[tot].x = x;
                q[tot].y = y;
                q[tot].id = tot;
                q[tot].k = 1;
                maxnum = max(maxnum, y);
                a[x] = y;
            }
        }
        solve(1, tot, 0, maxnum);
        for (int i = 1; i <= tot; i++)
        {
            if (is[i])
                printf("%d\n", ans[i]);
        }
    }
    return 0;
}
0%