题目链接：传送门

Descrption

动态区间第K大

Solution

本来想写树状数组套主席树的，太难打就学了一发整体二分

Code

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

using namespace std;

const int Maxn = 1e5 + 100;

int N, M, Q;

int A[Maxn];

struct node
{
    int x, y, k, t, ans;
}opt[Maxn << 2];

namespace BIT
{
    int Sum[Maxn << 2];

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

    inline void add (int x, int d)
    {
        while (x <= N)
        {
            Sum[x] += d;
            x += lowbit(x);
        }
    }

    inline int query (int x)
    {
        int ans = 0;
        while (x)
        {
            ans += Sum[x];
            x -= lowbit(x);
        }
        return ans;
    }

}

inline void Init()
{
    memset(BIT :: Sum, 0, sizeof BIT :: Sum);
    M = 0;
}

int q[Maxn << 2], Left[Maxn << 2];
int q1[Maxn << 2], q2[Maxn << 2];

inline void Solve (int l, int r, int head, int tail)
{
    //cout<<l<<" "<<r<<" "<<head<<" "<<tail<<endl;
    if (head > tail) return ;
    if (l == r)
    {
        for (int i = head; i <= tail; ++i)
        {
            int x = q[i];
            if (opt[x].t)
                opt[x].ans = l;
        }
        return ;
    }

    int mid = (l + r) >> 1;
    for (int i = head; i <= tail; ++i)
    {
        int x = q[i];
        if (!opt[x].t && opt[x].y <= mid)
        {
            BIT :: add(opt[x].x, opt[x].k);
            Left[i] = 1;
        }
        else if (opt[x].t)
        {
            int sum = BIT :: query(opt[x].y) - BIT :: query(opt[x].x - 1);
            if (opt[x].k <= sum)
                Left[i] = 1;
            else opt[x].k -= sum;
        }
    }

    for (int i = head; i <= tail; ++i)
    {
        int x = q[i];
        if (!opt[x].t && Left[i])
            BIT :: add(opt[x].x, -opt[x].k);
    }

    int cnt1, cnt2;
    cnt1 = cnt2 = 0;
    for (int i = head; i <= tail; ++i)
    {
        if (Left[i]) q1[++cnt1] = q[i];
        else q2[++cnt2] = q[i];
        Left[i] = 0;
    }
    //cout<<head<<" "<<tail<<" "<<cnt1<<" "<<cnt2<<endl;
    for (int i = head; i <= cnt1 + head - 1; ++i)
        q[i] = q1[i - head + 1];
    for (int i = cnt1 + head; i <= tail; ++i)
        q[i] = q2[i - cnt1 - head + 1];

//  cout<<l<<" "<<mid<<" * "<<head<<" "<<head + cnt1 - 1<<endl;
//  cout<<mid + 1<<" "<<r<<" * "<<head + cnt1<<" "<<tail<<endl;
    Solve(l, mid, head, head + cnt1 - 1);
    Solve(mid + 1, r, head + cnt1, tail);
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%lld", &N))
    {
        Init();
        for (int i = 1; i <= N; ++i)
        {
            scanf("%lld", &A[i]);
            opt[++M] = {i, A[i], 1, 0, 0};
        }
        scanf("%lld", &Q);
        while (Q--)
        {
            int type, x, y, k;
            scanf("%lld", &type);
            if (type == 1)
            {
                scanf("%lld%lld", &x, &y);
                opt[++M] = {x, A[x], -1, 0, 0};
                A[x] = y;
                opt[++M] = {x, A[x], 1, 0, 0};
            }
            else 
            {
                scanf("%lld%lld%lld", &x, &y, &k);
                opt[++M] = {x, y, k, 1, 0};
            }
        }
        for (int i = 1; i <= M; ++i) q[i] = i;
        Solve(1, 1e9 + 1, 1, M);
    //  cout<<"fuck"<<endl;
        for (int i = 1; i <= M; ++i)
            if (opt[i].t)
                printf("%lld\n", opt[i].ans);
    }
    return 0;
}

// 注意： q[i]和i不要搞错