Dynamic Rankings(整体二分)
带修区间第k小。(n,qle 10^4)。
这次我们旧瓶装新酒,不用带修主席树。我们用整体二分!整体二分是啥东西呢?
二分答案可以解决一次询问的问题。只要二分这个询问的答案就行了。
考虑这道题,如果改成一个询问,怎么用二分答案做(虽然其它方法随便做)。把初始值也看成一个修改,暴力修改值。二分区间第k小数的值v,把小于v的数都改成1,大于的都改成0。那么现在问题就变成了,查询区间中1的个数cnt。如果cnt<=k,那么第k小数的值肯定<=v。否则第k小数的值>v。
对于这道题,如果把所有询问都二分一遍,那么时间复杂度为(O(q*nlogv))。炸了!!
好的,我们来边缘ob一波。我们发现,我们把所有询问都二分答案了一遍。可不可以把询问放到一个二分里呢?
这就是整体二分。把所有修改和询问按照时间排在一起,设当前层二分的答案是v。那么,就可以把小于v的所有数变成1,大于v的则变成0。
那么,对于这个层的每一个询问,它们都需要获得它们[l, r]区间中1的个数。并且,还要支持修改某个位置的值(把那个值变成0或变成1)。用树状数组维护就行了哟。
显然时间复杂度是(O(logv*nlogn)=O(nlog^2n))。但是比起带修主席树来说,整体二分的常数相对小一些,不过也快不了多少。
能用整体二分的条件是:
- 询问满足可二分性
- 修改对询问的贡献独立
- 题目允许离线处理询问
- ……
整体二分可以二分第k大值,也可以二分时间(某个点被消灭的时间)。
还有一个东西,我讲不清楚,摘一下这里的博客:
关于整体二分
整体二分主要是把所有询问放在一起二分答案,然后把操作也一起分治。
什么时候用呢?
当你发现多组询问可以离线的时候
当你发现询问可以二分答案而且check复杂度对于单组询问可以接受的时候
当你发现询问的操作都是一样的的时候
你就可以使用整体二分这个东西了。
具体做法讲起来有些玄学,其实类似主席树转化到区间的操作或者线段树上二分。
想想:二分答案的时候,对于一个答案,是不是有些操作是没用的,有些操作贡献是不变的?
比如二分一个时间,那么时间后面发生的操作就是没有用的,时间前面的贡献是不变的。
二分一个最大值,比mid大的都是没用的,比mid小的个数是一定的。
整体二分就是利用了这么一个性质。
坑点:
树状数组不能暴力清零!((O(n^2logn))预警)
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
#include <cctype> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=5e4+5; struct Query{ int x, y, k, type, dfn; //l, r, k, 2, 询问编号 或者修改时值 }q[maxn], q1[maxn], q2[maxn]; int a[maxn], n, m, t, cntq, ans[maxn]; int seg[maxn]; inline int lowbit(int x){ return x&(-x); } void add(int x, int v){ for (int i=x; i<=n; i+=lowbit(i)) seg[i]+=v; } int query(int x){ int re=0; for (int i=x; i>0; i-=lowbit(i)) re+=seg[i]; return re; } void solve(int qb, int qe, int l, int r){ if (qb>qe) return; if (l==r){ for (int i=qb; i<=qe; ++i) if (q[i].type==2) ans[q[i].dfn]=l; return; } int m=(l+r)>>1, f=0, s=0; //f,s:左边/右边几个操作 //memset(seg, 0, sizeof(seg)); 这行的问题! for (int i=qb; i<=qe; ++i){ if (q[i].type==1) if (q[i].x<=m){ add(q[i].k, q[i].y); q1[f++]=q[i]; } else q2[s++]=q[i]; else { int t=query(q[i].y)-query(q[i].x-1); //区间中有多少1 if (t>=q[i].k) q1[f++]=q[i]; else{ q[i].k-=t; q2[s++]=q[i]; } } } for (int i=0; i<f; ++i) if (q1[i].type==1) add(q1[i].k, -q1[i].y); //左边的修改对右边没影响,右边的修改对左边的也没影响 memcpy(q+qb, q1, f*sizeof(Query)); memcpy(q+qb+f, q2, s*sizeof(Query)); solve(qb, qb+f-1, l, m); solve(qb+f, qe, m+1, r); } int main(){ scanf("%d%d", &n, &m); char c; int x, y, k, maxm=0; for (int i=1; i<=n; ++i){ scanf("%d", &a[i]); maxm=max(maxm, a[i]); q[++cntq]=(Query){a[i], 1, i, 1, cntq}; } for (int i=1; i<=m; ++i){ while (c=getchar(), !isgraph(c)); scanf("%d%d", &x, &y); maxm=max(maxm, y); if (c=='Q'){ scanf("%d", &k); q[++cntq]=(Query){x, y, k, 2, cntq}; //询问区间[x, y],第k小数 }else{ q[++cntq]=(Query){a[x], -1, x, 1, cntq}; //由于只有a[x]<=m时,在前面会打标记,因此也在a[x]<=m时才消去 a[x]=y; //通过a[x]来判断修改要分到哪里 q[++cntq]=(Query){a[x], 1, x, 1, cntq}; //a[k]=x } } solve(1, cntq, 0, maxm); for (int i=1; i<=cntq; ++i) if (ans[i]) printf("%dn", ans[i]); return 0; }
转载于:https://www.cnblogs.com/MyNameIsPc/p/9445731.html
最后
以上就是狂野小笼包最近收集整理的关于Dynamic Rankings(整体二分)的全部内容,更多相关Dynamic内容请搜索靠谱客的其他文章。
发表评论 取消回复