当前位置：首页 > news >正文

整体二分

news 2025/9/21 3:10:42

前言

注意：以下的 “元素” 都代表原题中的一个操作。

大说

把当前值域一分为二，把当前元素集合，每个元素的决策只有左区间 or 右区间，可以把同决策的元素放在一起去分治子区间（类似于线段树的结构）。

如下图（左边是值域区间，右边是元素集合）：

上图每个询问的答案：

①：2

②：2

③：4

④：9

⑤：6

⑥：10

中说

那么怎么给元素们分决策呢？

首先我们二分值域区间，那么肯定有一个 \(mid\) ！

然后我们用 \(f(mid,i)\) 与 \(g(i)\) 比较来进行分配 \(i\) 元素去处。

以区间第 k 大举例：

一个元素 \(i\) 包含 \(l_i、r_i、k_i\)，表示询问 \([l_i,r_i]\) 中第 \(k_i\) 大的数。

\(f(mid,i)\) 就是 \(mid\) 在 \([l_i,r_i]\) 区间有多少个数比他小。

\(g(i)\) 就是 \(k_i\)。

如果前者大，那么值域区间肯定为 \([l,mid]\)，决策至左。

如果后者大，那么值域区间肯定为 \([mid+1,r]\)，决策至右。

小说：

【模板】带修整体二分

修改和询问一起放在元素集合里就行，修改如询问一般决策，所以这两个我都称作元素。
若询问元素决策到 \([mid+1,r]\) ，那么 \(k_i-=g(i)\)，因为关于 \(g(i)\) 的修改都决策到 \([l,mid]\) 了。
遇到修改就修改，遇到询问就询问。在顺序把每个元素决策到两个子区间时，子区间内各元素之间不会改变相对位置，所以可以带修。

#include<bits/stdc++.h>
using namespace std;
const int QAQ=510000;
int s[QAQ],n,m,ans[QAQ],cnt,shang[QAQ],a[QAQ];
int lbd(int x) {return (x&(-x));}
void gai(int x,int c) {for(int i=x;i<=n;i+=lbd(i)) s[i]+=c;}
int cha(int x) {int da=0;for(int i=x;i;i-=lbd(i)) da+=s[i];return da;}
char op;
struct xxx {int op,id,x,y,k;} q[QAQ],q1[QAQ],q2[QAQ];
void work(int l,int r,int ql,int qr)
{if(ql>qr) return ;if(l==r) {for(int i=ql;i<=qr;i++) if(q[i].op==0) ans[q[i].id]=l;return ;}int o1=0,o2=0,mid=(l+r)>>1;for(int i=ql;i<=qr;i++)if(q[i].op==0){int pai=cha(q[i].y)-cha(q[i].x-1);if(q[i].k<=pai) q1[++o1]=q[i];else q[i].k-=pai,q2[++o2]=q[i];}else{if(q[i].y<=mid) q1[++o1]=q[i],gai(q[i].x,q[i].k);else q2[++o2]=q[i];}for(int i=1;i<=o1;i++) if(q1[i].op) gai(q1[i].x,-q1[i].k);for(int i=1;i<=o1;i++) q[ql+i-1]=q1[i];for(int i=1;i<=o2;i++) q[ql+o1+i-1]=q2[i];work(l,mid,ql,ql+o1-1),work(mid+1,r,ql+o1,qr);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],q[++cnt]={1,114514,i,a[i],1},shang[i]=a[i];for(int i=1,l,r,k,x,y;i<=m;i++){ans[i]=-114514,cin>>op;if(op=='Q') cin>>l>>r>>k,q[++cnt]={0,i,l,r,k};else cin>>x>>y,q[++cnt]={1,114514,x,shang[x],-1},q[++cnt]={1,114514,x,y,1},shang[x]=y;}work(0,1000000000,1,cnt);for(int i=1;i<=m;i++) if(ans[i]!=-114514) cout<<ans[i]<<'\n';return 0;
}