首页 > 代码库 > bzoj3110
bzoj3110
3110: [Zjoi2013]K大数查询
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 5881 Solved: 1958
[Submit][Status][Discuss]
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
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
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。?
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
整体二分是什么东西? 我们知道 主席树查询是一个类似二分的过程,但是这道题有修改,一次一次修改太慢了,这时就用上二分的思想了。
一个一个二分太慢了,那么我们把一堆东西一起二分,也就是把他们不断地划分,归类。
二分一个lb和ub,比(lb+ub)/2大的归到右边,小的归到左边,然后就完了。
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; #define N 500010 typedef long long ll; struct data { ll v; ll l,r,type,pos; }op[N]; vector<data> lp,rp; ll n,m; ll tag[N*6],t[N*6],ans[N]; bool flag[N*6]; void update(int l,int r,int x,int a,int b,int num) { if(l>b||r<a) return; if(l>=a&&r<=b) { tag[x]+=num; return; } t[x]+=(min(r,b)-max(l,a)+1)*num; update(l,(l+r)/2,x*2,a,b,num); update((l+r)/2+1,r,x*2+1,a,b,num); } ll query(int l,int r,int x,int a,int b) { if(l>b||r<a) return 0; if(l>=a&&r<=b) return t[x]+(r-l+1)*tag[x]; ll ret=0; ret+=(min(r,b)-max(l,a)+1)*tag[x]; ret+=query(l,(l+r)/2,x*2,a,b); ret+=query((l+r)/2+1,r,x*2+1,a,b); return ret; } void solve(int l,int r,int lb,int ub) { // printf("((((((((((((((((((((((\n"); // printf("lb=%d ub=%d\n",lb,ub); // printf("left=%d right=%d\n",l,r); if (l > r) return ; if(lb==ub) { for(int i=l;i<=r;i++) if(op[i].type==2) { flag[op[i].pos]=true; ans[op[i].pos]=lb; } return; } ll mb=lb+(ub-lb)/2; lp.clear(); rp.clear(); for(int i=l;i<=r;i++) { if(op[i].type==1) { if(op[i].v>mb) { // printf("------------\n"); // printf("l=%d r=%d\n",op[i].l,op[i].r); update(1,n,1,op[i].l,op[i].r,1); // printf("------------\n"); rp.push_back(op[i]); } else lp.push_back(op[i]); } else { ll c=query(1,n,1,op[i].l,op[i].r); // printf("op[i].l=%d op[i].r=%d\n",op[i].l,op[i].r); // printf("c=%d\n",c); if(c>=op[i].v) { rp.push_back(op[i]); } else { op[i].v-=c; lp.push_back(op[i]); } } } for(int i=l;i<=r;i++) { if(op[i].type==1&&op[i].v>mb) update(1,n,1,op[i].l,op[i].r,-1); } ll mid=l+lp.size(); for(int i=0;i<lp.size();i++) { op[i+l]=lp[i]; } for(int i=0;i<rp.size();i++) { op[mid+i]=rp[i]; } // printf(")))))))))))))))))))))\n"); solve(l,mid-1,lb,mb); solve(mid,r,mb+1,ub); } int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { scanf("%lld%lld%lld%lld",&op[i].type,&op[i].l,&op[i].r,&op[i].v); op[i].pos=i; } solve(1,m,-n,n); for(int i=1;i<=m;i++) { if(flag[i]) printf("%lld\n",ans[i]); } return 0; }
bzoj3110
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。