[JZOJ4438] K小数查询（经典分块）

Description

给你 N 个数组成的序列，需要支持两种操作

• 1 L R x 将 L 到 R 加上 x
• 2 L R k 求 L 到 R 第 k 小的数

Solution

分块大法好！

我们将序列分成 N−−√ 块，每块中维护原来的顺序的值，以及将该块所有值排序后的值，并且每个值还带有一个指针指向对应的那个值

修改整块的就直接打标记，两边的暴力重构该块

关键在查询！

我们可以二分一个答案（思考一下，二分出来的答案会不会序列中不存在呢？）

然后转化成判定性问题，判断二分出来的答案是不是在第 k 大

只需要对于每个块，找该块中小于这个值的个数，全部加起来看是不是 k−1 ，然后逼近答案。

证明一下这样为什么不会出现不存在的答案

假设正确答案是 s ,那么二分出大于 s 的答案显然不可能，因为个数一定要加上 s 本身这一个

小于等于 s ，都有可能等于 k−1 ，然而二分出来的答案是这些值中的最大值（自己想为什么）

所以二分出来的一定是 s

Code

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define mo 1000000007
using namespace std;
int pl[500],wz[80605],n,m,size;
struct note
{
int x,y;
}a[80605],b[80605];
bool cmp(note x,note y)
{
return x.x<y.x; 
}
int nt(int k)
{
return ((k-1)/size+1)*size+1;
}
int pd(int l,int r,int k)
{
int p=nt(l),sum=0,i;
    note k1;
    k1.x=k;
while (nt(p)<r+1)
    {
        k1.x-=pl[wz[p]];
        sum+=lower_bound(b+p,b+nt(p),k1,cmp)-b-p;
        k1.x+=pl[wz[p]];
        p=nt(p); 
    } 
if (nt(l)>r)
    {
        fo(i,l,r) if (a[i].x<k-pl[wz[i]]) sum++;
    }
else 
    {
        fo(i,l,nt(l)-1) if (a[i].x<k-pl[wz[i]]) sum++;
        fo(i,p,r) if (a[i].x<k-pl[wz[i]]) sum++;
    }
return sum;

}
int main()
{
int i,j;
cin>>n;
    size=(int)sqrt(n);
    fo(i,1,n)
    {
scanf("%d",&a[i].x);
        b[i].x=a[i].x;
        b[i].y=i;
    } 
    j=1;
    wz[j]=1;
while (j+size<=n+1)
    {
        sort(b+j,b+j+size,cmp);
        j+=size;
        wz[j]=wz[j-size]+1;
    }
if(j!=n+1) sort(b+j,b+n+1,cmp);
    fo(i,1,n) 
    {
if (wz[i]==0) wz[i]=wz[i-1]; 
        a[b[i].y].y=i;
    }
cin>>m;
int i1=0;
    fo(i,1,m)
    {
int p,l,r,k,j;
scanf("%d%d%d%d",&p,&l,&r,&k);
if (p==1)
        {
            j=nt(l); 
while (nt(j)<=r)
            {
                pl[wz[j]]+=k;
                j=nt(j);
            } 
int q;
if (nt(l)>r)
            {
                fo(q,l,r) a[q].x=b[a[q].y].x=a[q].x+k;
                sort(b+nt(l)-size,b+nt(l),cmp);
                fo(q,nt(l)-size,nt(l)-1) a[b[q].y].y=q;
            }
else 
            {
                fo(q,l,nt(l)-1) a[q].x=b[a[q].y].x=a[q].x+k;
                sort(b+nt(l)-size,b+nt(l),cmp);
                fo(q,nt(l)-size,nt(l)-1) a[b[q].y].y=q;

                fo(q,j,r) a[q].x=b[a[q].y].x=a[q].x+k;
                sort(b+j,b+nt(j),cmp);
                fo(q,j,nt(j)-1) a[b[q].y].y=q;
            }
        }
else
        {
int x=-5000000,y=5000000,mid;
while (x<y-1)
             { 
                mid=(x+y)/2;
if (pd(l,r,mid)<=k-1) x=mid;
else y=mid;
             }
if (pd(l,r,y)==k-1) printf("%d\n",y);
else printf("%d\n",x); 
        }
    }
}