【OI之路】02数据结构-10整体二分

基于值域的整体分治

推荐资料

2013许昊然论文-《浅谈数据结构题的几个非经典解法》

复杂度保证的关键

通常而言,我们能通过一个log来把问题转化为局部子问题
但这要求我们在判定二分的时候,所需要的时间不能和n有关,而只能和当前的局部区间长度有关

例题

Dynamic Rankings

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int INF=0x3f3f3f3f;
typedef long long ll;
const int MAX_N=110000*3;
int n;
int bit[MAX_N];
int lowbit(int x) {return x&-x;}
void change(int x,int c)
{
while(x<=n)
{
bit[x]+=c;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>=1)
{
ans+=bit[x];
x-=lowbit(x);
}
return ans;
}
struct Qes
{
int op;
int l,r,k;//0询问
int pos,d,num;//1修改
int id;
}q[MAX_N],q1[MAX_N],q2[MAX_N];
int ans[MAX_N];
void solve(int l,int r,int fl,int fr)
{
if(l>r or fl>fr) return;
if(l==r)
{
for(int i=fl;i<=fr;i++) if(q[i].op==0) ans[q[i].id]=l;
return;
}
//printf("(%d,%d,%d,%d)\n",l,r,fl,fr);
int mid=(l+r)/2,tot1=0,tot2=0;
for(int i=fl;i<=fr;i++)
{
if(q[i].op==0)
{
int left=sum(q[i].r)-sum(q[i].l-1);
if(q[i].k<=left) q1[++tot1]=q[i];
else q2[++tot2]=q[i],q2[tot2].k-=left;
}
else
{
if(q[i].d<=mid) change(q[i].pos,q[i].num),q1[++tot1]=q[i];
else q2[++tot2]=q[i];
}
}
for(int i=1;i<=tot1;i++) if(q1[i].op==1) change(q1[i].pos,-q1[i].num);
for(int i=1;i<=tot1;i++) q[fl+i-1]=q1[i];
for(int i=1;i<=tot2;i++) q[fl+tot1+i-1]=q2[i];
solve(l,mid,fl,fl+tot1-1);
solve(mid+1,r,fl+tot1,fr);
}
int a[MAX_N];
void main()
{
int m;scanf("%d%d",&n,&m);
int tot=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
q[++tot]=(Qes){1,0,0,0,i,a[i],1,0};
}
for(int now=1;now<=m;now++)
{
char str[5];scanf("%s",str);
if(str[0]=='Q')
{
int l,r,k;scanf("%d%d%d",&l,&r,&k);
q[++tot]=(Qes){0,l,r,k,0,0,0,now};
}
else
{
int pos,t;scanf("%d%d",&pos,&t);
q[++tot]=(Qes){1,0,0,0,pos,a[pos],-1,0};
q[++tot]=(Qes){1,0,0,0,pos,a[pos]=t,1,0};
}
}
memset(ans,-1,sizeof ans);//debug
solve(0,INF,1,tot);
for(int i=1;i<=m;i++) if(ans[i]>-1) printf("%d\n",ans[i]);
}
}
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/55c7.html
转载请注明出处,谢谢!