例题: 动态区间第 k 小
先上代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #define mid ((l+r)>>1)
- #define lowbit(x) (x&-x)
- #define N 50005
- #define M 20005
- using namespace std;
- const int inf=1000000007;
- struct zero{
- int x,y,k,op,id;
- }q[N+M],q1[N+M],q2[N+M];
- int tree[N],tot=0,n,m,ans[M];
- int T,x,y,k,cnt=0;
- int input[N];
- char c;
- void add(int a,int k){for(;a<=max(n,m);a+=lowbit(a))tree[a]+=k;}
- int ask(int a){int ans=0;for(;a>0;a-=lowbit(a))ans+=tree[a];return ans;}
- void solve(int ql,int qr,int l,int r){
- 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 t1=0,t2=0;
- for(int i=ql;i<=qr;i++){
- if(q[i].op){
- if(q[i].x<=mid)add(q[i].id,q[i].op),q1[++t1]=q[i];
- else q2[++t2]=q[i];
- }
- else{
- int sum=ask(q[i].y)-ask(q[i].x-1);
- if(sum>=q[i].k)q1[++t1]=q[i];
- else q[i].k-=sum,q2[++t2]=q[i];
- }
- }
- for(int i=1;i<=t1;i++)if(q1[i].op)add(q1[i].id,-q1[i].op);
- for(int i=1;i<=t1;i++)q[i+ql-1]=q1[i];
- for(int i=1;i<=t2;i++)q[i+ql+t1-1]=q2[i];
- solve(ql,t1+ql-1,l,mid);
- solve(t1+ql,qr,mid+1,r);
- }
- int main(){
- scanf("%d",&T);
- while(T--){
- cnt=tot=0;
- memset(q,0,sizeof q);
- memset(tree,0,sizeof tree);
- memset(q1,0,sizeof q1);
- memset(q2,0,sizeof q2);
- memset(ans,0,sizeof ans);
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++){
- scanf("%d",input+i);
- q[++tot].x=input[i],q[tot].op=1,q[tot].id=i;
- }
- for(int i=1;i<=m;i++){
- cin>>c;
- if(c=='C'){
- scanf("%d%d",&k,&x);
- q[++tot].x=input[k],q[tot].op=-1,q[tot].id=k;
- input[k]=x;
- q[++tot].x=input[k],q[tot].op=1,q[tot].id=k;
- }
- else {
- scanf("%d%d%d",&x,&y,&k);
- q[++tot].x=x,q[tot].y=y,q[tot].k=k,q[tot].op=0,q[tot].id=++cnt;
- }
- }
- solve(1,tot,-inf,inf);
- for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
- }
- }
解释一下 struct zero:
对于修改函数: x 表示修改的值, op 表示该操作是修改还是查寻, id 为该操作作用点在数组中的位置
对于查寻函数: x,y 表示查寻区间, k 表示在这区间中查找第 k 小, op 和 id 意义同上
整体二分的主要思路就是把一段操作 (修改和查寻) 序列分成两段, 分治操作
- solve(ql,t1+ql-1,l,mid);
- solve(t1+ql,qr,mid+1,r);
就是这样
那么怎么分段呢
我们来看 solve(ql,qr,l,r)函数,
这里 ql,qr,l,r 的意义就是序列中 ql 到 qr 的所有询问, 它的答案在 l 到 r 之间
算了我在代码里讲吧, 那么请继续看代码
- void solve(int ql,int qr,int l,int r){
- if(ql>qr)return;// 特判防 RE
- if(l==r){//l==r 代表答案已经确定了, 那么把 ql 到 qr 中所有询问答案赋成 l
- for(int i=ql;i<=qr;i++)
- if(q[i].op==0)ans[q[i].id]=l;
- return;
- }
- int t1=0,t2=0;
- for(int i=ql;i<=qr;i++){
- if(q[i].op){
- if(q[i].x<=mid)add(q[i].id,q[i].op),q1[++t1]=q[i];//q[i]/x<=mid 代表这个修改对 ql 到 qr 区间内的查寻有影响, 我们把它加到树状数组里, 又因为答案在 l~mid 里的询问又会受它影响
- // 所以要把它丢进 q1 继续发挥作用. 至于答案在 mid+1~r 里的询问, 虽然受它影响, 但影响为定值, 所以我们用树状数组计算出这个值即可消去影响
- else q2[++t2]=q[i];// 对答案在 l~mid 里的询问没影响, 加入 q2 影响后半段
- }
- else{
- int sum=ask(q[i].y)-ask(q[i].x-1);
- if(sum>=q[i].k)q1[++t1]=q[i];// 同理, sum>=q[i].k 表示 q[i]的答案在 l~mid 内, 查寻 l~mid
- else q[i].k-=sum,q2[++t2]=q[i];// 否则, 减去先前的影响 (定值) 消去影响
- }
- }
- for(int i=1;i<=t1;i++)if(q1[i].op)add(q1[i].id,-q1[i].op);// 重置树状数组
- for(int i=1;i<=t1;i++)q[i+ql-1]=q1[i];
- for(int i=1;i<=t2;i++)q[i+ql+t1-1]=q2[i];
- solve(ql,t1+ql-1,l,mid);
- solve(t1+ql,qr,mid+1,r);// 分治
- }
然后注意 main 里把一个点变成 x 的操作要拆成两个操作实现
- if(c=='C'){
- scanf("%d%d",&k,&x);
- q[++tot].x=input[k],q[tot].op=-1,q[tot].id=k;
- input[k]=x;
- q[++tot].x=input[k],q[tot].op=1,q[tot].id=k;
- }
来源: http://www.bubuko.com/infodetail-2984356.html