Tang7O

整体二分（poj 2104）

Tang7O
ACM算法

发布于：2020年4月10日
次浏览
字数统计: 1.1k字   |   阅读时长: 5分

所谓整体二分，需要数据结构题满足以下性质：

  1. 询问的答案具有可二分性
  2. 修改对判定答案的贡献相对独立，修改之间互不影响效果
  3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
  4. 贡献满足交换律，结合律，具有可加性
  5. 题目允许离线操作

不妨先来考虑下一个简单易懂的?(?????)的排序算法(?为数值范围)
这个方法是自己在思考整体二分的时候??的 虽然在实际应用上没什么意义 但是有助于理解整体二分的分治过程
我们假设当前处理的区间里最小值不小于? 最大值不大于? 令???=(?+?)/2
然后把当前区间扫描一遍 如果一个数不大于???就放到左子区间 否则放到右子区间
如此下去 直到区间内只剩一个数或者? 与 ?相等 排序就完成了 现在回到静态区间第?小问题 和刚才那个排序算法类似 我们先二分一个答案???，如果区间内小于等于???的数的个数(记为???)不超过? 那么最终答案显然也是不超过???的，这类询问我们把它们划分到左子区间。而对于???大于?的 我们则把它们划分到右子区间 并且把?减去???，换句话说就是把小于等于???的数的贡献全部算上后之后就不用考虑了。
可以发现这样划分的层数是???? 而每一层的询问个数是?个 再加上算贡献时用到的??? 所以复杂度是?(?????????) 以下是poj 2104的参考代码：

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
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define PI acos(-1)
#define debug(a) cout << (a) << endl
typedef long long ll;
int dir8[8][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
int dir4[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
const int INF = 0x3f3f3f3fLL;
const long long LLF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXn = 2e5 + 15;
const int mod = 1e9 + 7;
//priority_queue, vector>, greater>> q;
int n, m, c[MAXn], ans[MAXn],cnt; //c 树状数组， ans：答案
struct node {
    int ty, pos, x, y, k; //ty区别输入和询问， pos ：下标，x：左，y：右， k：第k小
} q[MAXn], q1[MAXn], q2[MAXn]; //q存储 ，q1：左区间，q2：右区间

int lowbit(int x)  // 求x最低位的1
{
    return x & -x;
}
void add(int x, int val) //更新树状数组
{
    while (x <= n) {
        c[x] += val;
        x += lowbit(x);
    }
}
int sum(int x) //求 1-x 的树状数组的值的和
{
    int sum = 0;
    while (x>0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}
void solve(int l, int r, int L, int R) 
{
    if (l > r  L > R) 
        return;
    if (L == R) { //如果相等 更新答案
        for (int i = l; i <= r; i++) {
            if (q[i].ty) {
                ans[q[i].pos] = L;
            }
        }
        return;
    }
    int mid = (L + R) >> 1, cnt1 = 0, cnt2 = 0; 
    for (int i = l; i <= r; i++) {
        if (q[i].ty) {//如果是询问
            int temp = sum(q[i].y) - sum(q[i].x - 1); //temp ：q[i].x 到q[i].y 小于等于mid 的个数 
            if (temp >= q[i].k) //如果小于等于mid的数大于k
                q1[++cnt1] = q[i];//放到左区间
            else { //反之 k减去temp 并放到右区间
                q[i].k -= temp;
                q2[++cnt2] = q[i];
            }
        } else { //如果是输入
            if(q[i].x<=mid){ //如果小于mid
                add(q[i].pos,q[i].y);// 更新树状数组
                q1[++cnt1]=q[i];// 放到左区间
            }
            else q2[++cnt2]=q[i];//反之，放到右区间
        }
    }
    for(int i=1;i<=cnt1;i++){
        if(!q1[i].ty){ //更新树状数组
             add(q1[i].pos,-q1[i].y);
        }
    }//更新 q 数组
    for(int i=1;i<=cnt1;i++){
        q[l+i-1]=q1[i]; 
    }
    for(int i=1;i<=cnt2;i++){
        q[l+i+cnt1-1]=q2[i]; 
    }
    solve(l,l+cnt1-1,L,mid);//左区间
    solve(l+cnt1,r,mid+1,R);//右区间
    return ;
}
int main(){
//输入
    cin>>n>>m;
    int l,r,k;
    for(int i=1;i<=n;i++){
        cin>>k;
        q[++cnt]=node{0,i,k,1,0}; // ty==0 表示是输入
    }
    for(int i=1;i<=m;i++){
        cin>>l>>r>>k;
        q[++cnt]=node{1,i,l,r,k}; //ty==1 表示是询问 
    }
    solve(1,cnt,-INF,INF);
    for(int i=1;i<=m;i++)//输出
        cout<<ans[i]<<endl;
    return 0;
}

本文作者： Tang7O

本文链接：https://tang7o.cn/2020/04/10/%E6%95%B4%E4%BD%93%E4%BA%8C%E5%88%86%EF%BC%88poj-2104%EF%BC%89/

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议。转载请注明出处！

更新于：2022年4月13日

算法

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题

Copyright © 2017-2020 XXX

鲁ICP备-20012065号