[ZJOI2013]K 大数查询
题目描述
有 N 个位置, M 个操作. 操作有两种, 每次操作如果是:
1 a b c: 表示在第 a 个位置到第 b 个位置, 每个位置加上一个数 c
2 a b c: 表示询问从第 a 个位置到第 b 个位置, 第 C 大的数是多少.
输入输出格式
输入格式:
第一行 N,M 接下来 M 行, 每行形如 1 a b c 或 2 a b c
输出格式:
输出每个询问的结果
solution
整体二分.
假设我们现在要解决 [ql,qr] 并且他们的答案(加数操作就是值) 在[l,r]
二分一个 mid, 我们维护一个区间.
我们把>=mid 的操作对应区间都加 1
对于询问, 如果对应区间的值>=c, 说明 mid-r 有最少 c 个了, 那么它的答案就在 [mid,r] 里.
否则把值减去区间对应值, 丢进 [l,mid-1] 里.
树状数组有个高级的区间加区间查写法, 维护差分和差分 * i
- #include<cstdio>
- #include<iostream>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #define maxn 500005
- using namespace std;
- int n,m,Max,t1[maxn],t2[maxn];
- struct node{
- int op,a,b,c,id,ans;
- }q[maxn],s[maxn];
- void add(int x,int v){
- for(int i=x;i<=n;i+=i&-i)t1[i]+=v,t2[i]+=x*v;
- }
- int ask(int x){
- int sum=0;
- for(int i=x;i;i-=i&-i){
- sum+=(x+1)*t1[i]-t2[i];
- }
- return sum;
- }
- void solve(int l,int r,int ql,int qr){
- if(l==r){
- for(int i=ql;i<=qr;i++)q[i].ans=l;
- return;
- }
- int mid=l+r+1>>1;
- int p=ql;
- for(int i=ql;i<=qr;i++){
- if(q[i].op==1){
- if(q[i].c>=mid){
- add(q[i].a,1);add(q[i].b+1,-1);
- }
- else p++;
- }
- else {
- q[i].ans=ask(q[i].b)-ask(q[i].a-1);
- if(q[i].ans<q[i].c)p++;
- }
- }
- int n1=ql,n2=p;
- for(int i=ql;i<=qr;i++){
- if(q[i].op==1){
- if(q[i].c>=mid){
- add(q[i].a,-1);add(q[i].b+1,1);
- s[n2++]=q[i];
- }
- else s[n1++]=q[i];
- }
- else {
- if(q[i].ans<q[i].c){
- q[i].c-=q[i].ans;
- s[n1++]=q[i];
- }
- else s[n2++]=q[i];
- }
- }
- for(int i=ql;i<=qr;i++)q[i]=s[i];
- solve(l,mid-1,ql,p-1);solve(mid,r,p,qr);
- }
- bool ID(node a,node b){return a.id<b.id;}
- int main()
- {
- cin>>n>>m;
- for(int i=1;i<=m;i++){
- scanf("%d%d%d%d",&q[i].op,&q[i].a,&q[i].b,&q[i].c);
- Max=max(Max,q[i].c);
- q[i].id=i;
- }
- solve(1,Max,1,m);
- sort(q+1,q+m+1,ID);
- for(int i=1;i<=m;i++){
- if(q[i].op==2){
- printf("%d\n",q[i].ans);
- }
- }
- return 0;
- }
- View Code
[ZJOI2013]K 大数查询
来源: http://www.bubuko.com/infodetail-2962533.html