首页 > 其他分享 >【学习笔记】整体二分

【学习笔记】整体二分

时间:2024-01-17 18:59:41浏览次数:27  
标签:二分 int 值域 询问 笔记 学习 leq 答案

一. 整体二分概念

整体二分的主体思路就是把多个查询一起解决,是一个离线算法。

其要求:

  1. 询问的答案具有可二分性

  2. 修改对判定答案的贡献互相独立,修改之间互不影响效果

  3. 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值

  4. 贡献满足交换律,结合律,具有可加性

  5. 题目允许使用离线算法

其大体结构框架:

设 \([l,r]\) 为答案的值域,\([s,t]\) 为答案的定义域

那么二分答案时考虑下标在 \([s,t]\) 中的操作和询问,答案在值域 \([l,r]\) 中

二. 静态区间第 \(k\) 小

由一道题引入整体二分的具体实现。

给定 \(n\) 个整数构成的序列 \(a\),将对于指定的闭区间 \([l, r]\) 查询其区间内的第 \(k\) 小值。

\(1 \leq n,m \leq 2\times 10^5\),\(|a_i| \leq 10^9\),\(1 \leq l \leq r \leq n\),\(1 \leq k \leq r - l + 1\)。

静态区间第 \(k\) 小,一个经典的问题。

显然可以用主席树做,这里我们考虑用整体二分。

cdq 分治类似,将询问和修改都看成“操作”。我们首先把所有操作按时间顺序存入数组中,然后开始分治,定义函数

solve(l,r,s,t) 表示在值域 \([l,r]\) 上二分处理 \([s,t]\) 这些操作

在每一层分治中,考虑利用数据结构(常用树状数组)统计当前查询的答案和 \(mid =\dfrac{l+r}{2}\) 之间的关系。

根据查询出来的答案和 \(mid\) 间的关系(\(<=mid\) 或者 \(>mid\) )将当前处理的操作序列分为两份,并分别递归处理(注意修改和询问都要递归)。

边界:当 \(l=r\) 时,找到答案,记录答案并返回即可。

需要注意的是,在整体二分过程中,solve(l,r,s,t) 只处理答案在 \([l,r]\) 内的询问,最终答案范围不在 \([l, r]\) 的询问会在其他 solve 函数中处理。

比如,我们现在有这样一个 \(n=7\) 的序列:

\([1,5,3,6,4,7,2]\)

查询次数为 \(3:\)

\(q_1=2,5,3\to ans=4\)

\(q_2=4,4,1\to ans=6\)

\(q_3=1,6,2\to ans=3\)

考虑用整体二分的思想。

原序列的值域显然为 \([1,7]\)。

这里注意最好先将原序列离散化后求值域。

那么 \(mid=\dfrac{1+7}{2}=4\)。

考虑将这个序列分成两类:

一类是权值 \(\le 4\),另一类是 \(>4\) 的。

我们把这两类用下标表示出来:

\(\le 4:(1,3,5,7)\)

\(>4:(2,4,6)\)

注意这里指下标,而不是权值。

考虑第一个询问 \(q_1=2,5,3\)。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+6;
const int inf=1e9;

int n,m,tr[N],ans[N];

struct node{
	int x,y,k,id;
    bool flag;
}a[N],b[N],c[N];

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

inline void update(int x,int val){
    while(x<=n){
        tr[x]+=val;
        x+=lowbit(x);
    }
    return;
}

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

inline void solve(int l,int r,int s,int t){
    if(s>t)return;
    if(l==r){
        for(int i=s;i<=t;i++)if(a[i].flag)ans[a[i].id]=l;
		return;
    }
    int mid=(l+r)>>1,p=0,q=0;
    for(int i=s;i<=t;i++){
        if(!a[i].flag){
            if(a[i].x<=mid){
                update(a[i].id,1);
                b[++p]=a[i];
            }
            else c[++q]=a[i];
        }
        else{
            int res=query(a[i].y)-query(a[i].x-1);
            if(res>=a[i].k)b[++p]=a[i];
            else{
                a[i].k-=res;
                c[++q]=a[i];
            }
        }
    }
    for(int i=1;i<=p;i++)if(!b[i].flag)update(b[i].id,-1);
	for(int i=1;i<=p;i++)a[i+s-1]=b[i];
	for(int i=1;i<=q;i++)a[i+s+p-1]=c[i];
	solve(l,mid,s,s+p-1);
	solve(mid+1,r,s+p,t);
    return;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        a[i].x=x;
        a[i].y=1;
        a[i].k=inf;
        a[i].id=i;
        a[i].flag=false;
    }
    for(int i=1;i<=m;i++){
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        a[i+n].x=x;
        a[i+n].y=y;
        a[i+n].k=k;
        a[i+n].id=i;
        a[i+n].flag=true;
    }
    solve(-inf,inf,1,n+m);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

标签:二分,int,值域,询问,笔记,学习,leq,答案
From: https://www.cnblogs.com/trsins/p/17970741

相关文章

  • 【学习笔记】线段树合并
    一.普通线段树合并线段树合并就是建立一棵新的线段树保存原有的两棵线段树的信息。两棵线段树当前要合并的点所表示的区间是一样的。线段树合并的过程很简单。如果A有p位置,B没有,新的线段树p位置赋成A,返回A;如果B有p位置,A没有,新的线段树p位置赋成B,返回A;如果合并到叶子结......
  • 【学习笔记】权值线段树
    一.权值线段树权值线段树即一种线段树,以序列的数值为下标。节点里所统计的值为节点所对应的区间\([l,r]\)中,\([l,r]\)这个值域中所有数的出现次数。举个例子,有一个长度为\(10\)的序列\(\{1,5,2,3,4,1,3,4,4,4\}\)。那么统计每个数出现的次数。易知\(1\)出现了\(2\)......
  • 【学习笔记】数论杂谈
    一.素数相关0.约定若无特殊说明,本部分做以下记号规定。\(p\in\mathbb{P}\),\(\mathbbP\)为质数集。\(\pi(n)\)表示\(1\)至\(n\)内的素数个数。\(P^{+}(n),P^-(n)\)分别表示\(n\)的最大/最小质因子。\(\nu_i\)表示\(i\)的可重质因子个数。1.素数定理\[\pi(......
  • 【学习笔记】数论函数与莫比乌斯反演
    一.数论函数基础数论函数:满足值域为整数的函数。本文下述的数若无特殊说明均为整数。若无特殊说明则钦定\(\displaystylen=\prod_{i=1}^kp_i^{e_i},p_i\in\mathbb{P}\)。\(\mathbb{P}\)表示质数集合,\(p_i\)互不相同。介绍几个常见的数论函数:\(I(n)\):恒等函数,无论\(n\)......
  • 【学习笔记】Segment Tree Beats/吉司机线段树
    一.区间最值操作本文对吉如一老师在\(2016\)年国家集训队论文中的线段树处理历史区间最值的问题的一些杂谈。区间最值笼统地指求区间的最值以及区间所有数对\(x\)取最值(即令\(a_i=\max/\min(a_i,x)\))这一类的查询与修改操作。HDU5306GorgeousSequence支持对区间......
  • 拓扑排序_学习记录
    拓扑排序_学习记录第一次在读入数据时被TLE……Whatis拓扑排序?拓扑排序——Topologicalsorting(所以说写函数名时用ts而不是tp),拓扑排序要解决的问题是给一个有向无环图的所有节点排序。顾名思义,就是可以把一个有向的无环的图中所有的点按照一定规则排序的算法……emm......
  • 学习笔记6
    Scala匿名函数(函数字面量)Scala中的匿名函数也叫做函数字面量,既可以作为函数的参数使用,也可以将其赋值给一个变量,在匿名函数的定义中“=>”可理解为一个转换器,它使用右侧的算法,将左侧的输入数据转换为新的输出数据,使用匿名函数后,我们的代码变得更简洁了。valtest=(x:Int)=>......
  • 一起学习Avalonia
    一起学习Avalonia(一)一起学习Avalonia(二)一起学习Avalonia(三)一起学习Avalonia(四)一起学习Avalonia补充(Linux下的使用开发)一起学习Avalonia(五)一起学习Avalonia补充(deepin下的使用开发t调试)一起学习Avalonia(六)一起学习Avalonia(七)一起学习Avalonia(八)一起学习Avalonia(......
  • Print linked list using recursion【1月17日学习笔记】
    点击查看代码//Printlinkedlistusingrecursion#include<iostream>usingnamespacestd;structnode{ intdata; node*next;};voidprint(node*p){ if(p==NULL)return;//递归中止条件 cout<<p->data<<""; print(p->next)......
  • Reverse a linked list【1月17日学习笔记·】
    点击查看代码//Reverssealinkedlist#include<iostream>usingnamespacestd;structnode{ intdata; node*next;};node*A;voidreverse(){ node*next;//用于保存下一个·节点地址以便索引 node*current=A;//当前索引 node*prev=NULL;//保存上一个节点......