BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组

时间:2023-03-08 15:53:47
BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组

BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M
接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

 solve(b,e,l,r)表示处理b~e的询问,答案在l~r之间,同时处理插入,权值范围为l~r。
把所有操作都离线下来,同时使得操作在任意时刻都按时间戳顺序。
二分答案mid,对于插入的数大于mid就插进去(区间加),否则丢到左边。
对于询问像正常的整体二分一样,查询区间和,然后往左走或往右走。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
#define N 50050
int n,m,flg[N],ans[N];
struct Bit {
uint c[N];
void fix(int x,uint v) { for(;x<=n;x+=x&(-x)) c[x]+=v; }
uint inq(int x) { uint re=0;for(;x;x-=x&(-x)) re+=c[x];return re;}
}A,B;
struct Q {
int a,b,c,d,id;
}q[N],t[N];
void update(int x,int y,uint v) {
A.fix(x,v); A.fix(y+1,-v);
B.fix(x,x*v); B.fix(y+1,-(y+1)*v);
}
uint query(int x,int y) {
return A.inq(y)*(y+1)-B.inq(y)-A.inq(x-1)*x+B.inq(x-1);
}
void solve(int b,int e,int l,int r) {
int i;
if(b>e) return ;
if(l==r) {
for(i=b;i<=e;i++) if(q[i].a==2) ans[q[i].id]=l;
return ;
}
int mid=(l+r)>>1,lp=b-1,rp=e+1;
for(i=b;i<=e;i++) {
if(q[i].a==1) {
if(q[i].d<=mid) t[++lp]=q[i];
else update(q[i].b,q[i].c,1),t[--rp]=q[i];
}else {
uint tmp=query(q[i].b,q[i].c);
if(q[i].d<=tmp) t[--rp]=q[i];
else q[i].d-=tmp,t[++lp]=q[i];
}
}
for(i=b;i<=e;i++) {
if(q[i].a==1&&q[i].d>mid) update(q[i].b,q[i].c,-1);
}
for(i=b;i<=lp;i++) q[i]=t[i];
for(i=rp;i<=e;i++) q[e-i+rp]=t[i];
solve(b,lp,l,mid);
solve(rp,e,mid+1,r);
}
int main() {
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=m;i++) {
scanf("%d%d%d%d",&q[i].a,&q[i].b,&q[i].c,&q[i].d); q[i].id=i;
if(q[i].a==2) flg[i]=1;
}
solve(1,m,-n,n);
for(i=1;i<=m;i++) if(flg[i]) printf("%d\n",ans[i]);
}