概述

整体二分可用于

  • 支持离线的查询和修改
  • 询问的答案可以二分

简单来说就是对答案进行二分
然后再将查询和操作划分到不同的答案区间

题目

hdu5412

动态区间第k大

可以作为模板
树状数组维护

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<(n);++i)
#define fill(a,b) memset(a,b,sizeof(a))

const int maxn = 1e5 + 10;

int n,m,tot;
int bit[maxn],a[maxn],ans[maxn];

struct Q{
int x,y,k,op,id;
} q[maxn*3],q1[maxn*3],q2[maxn*3];


void add(int x,int t)
{
for(;x <= n;x += x&-x) bit[x] += t;
}

int query(int x)
{
int res = 0;
for(;x>0;x -= x&-x) res += bit[x];
return res;
}

void deal(int L,int R,int l,int r)
{
if(L > R) return;
if(l == r)
{
F(i,L,R) if(!q[i].op) ans[q[i].id] = l;
return;
}
int m = l+r >> 1,cnt1,cnt2;
cnt1 = cnt2 = 0;
F(i,L,R)
{
if(q[i].op)
{
if(q[i].y <= m)
{
add(q[i].x,q[i].op);
q1[++cnt1] = q[i];
}
else q2[++cnt2] = q[i];
}
else
{
int t = query(q[i].y) - query(q[i].x-1);
if(q[i].k <= t)
{
q1[++cnt1] = q[i];
}
else
{
q[i].k -= t;
q2[++cnt2] = q[i];
}
}
}

F(i,1,cnt1) if(q1[i].op) add(q1[i].x,-q1[i].op);

F(i,1,cnt1) q[L+i-1] = q1[i];
F(i,1,cnt2) q[L+i+cnt1-1] = q2[i];

deal(L,L+cnt1-1,l,m);
deal(L+cnt1,R,m+1,r);
}


int main()
{
//freopen("test.txt","r",stdin);
int T;
while(~scanf("%d",&n))
{
int cnt = 0;
tot = 0;
F(i,1,n) scanf("%d",a+i),q[tot++] = (Q){i,a[i],0,1};
scanf("%d",&m);
F(i,1,m)
{
int op,x,y,k;
scanf("%d %d %d",&op,&x,&y);
if(op == 1)
{
q[tot++] = (Q){x,a[x],0,-1,0};
q[tot++] = (Q){x,y,0,1,0};
a[x] = y;
}
else
{
scanf("%d",&k);
q[tot++] = (Q){x,y,k,0,++cnt};
}
}
fill(bit,0);
deal(0,tot-1,1,0x3f3f3f3f);
F(i,1,cnt) printf("%d\n",ans[i]);
}
return 0;
}

atcoder-agc002