题解 SP10500 【HAYBALE - Haybale stacking】

题目链接

此题大概就是维护一个序列，支持两个操作：

1. 区间加
2. 区间取中位数（在此题中已经确定取的是所有数的中位数）

显然此题要求在线，所以莫队萎了。所以为什么要用莫队呢？

咳咳，不说那么多，进入正题。

1.区间加操作

当然可以打个暴力。

int l,r;
scanf("%d%d",&l,&r);	//表示将区间 [l,r] 内的所有数加上1。
for(int i=l;i<=r;i++){
	a[i]++;				//a[] 是原数组
}

不过单次修改复杂度已经达到了恐怖的 $O(n)$ ，$k$ 次修改就成了 $O(nk)$ 。

再看看 $1\le n \le 1000000\ ,\ 1\le k \le 25000$ 的数据范围，复杂度立马爆炸。

好吧，考虑优化。

各位大佬可以写一个线段树/树状数组/分块 等搞♂基高级数据结构，不过此题最简单的做法，还是差分。

此时才算真正进入正题

差分基本思想：对于原数组 $A$ ，我们定义一个新数组 $d$ 表示数组 $A$ 的差分数组，且有 $d[i]=A[i]-A[i-1]$ 。

那么，如果我们将 $d[i]$ 加上 $k$ ，根据差分数组的定义，我们有 $d[i]+A[i-1]=A[i]$ 。

而此时 $d[i]$ 加上了 $k$ ，所以，相应地，$A[i]$ 也加上了 $k$ 。

同样是根据差分数组的定义，$A[i+1]=A[i]+d[i+1]$，而此时 $A[i]$ 加上了 $k$ ，所以，相应地，$A[i+1]$ 也加上了 $k$ 。

依此类推，只要将 $d[i]$ 加上 $k$ ，我们就能将 $A[i],A[i+1],A[i+2],\dots\dots,A[n-1],A[n]$ 全部加上 $k$ 。（此处 $n$ 指数组大小）

不过，题目中要求的是将区间 $[l,r]$ 加上一个值诶，这一下子往后多加了很多个数，怎么办呢🤔🤔🤔？

其实，只要把 $d[r+1]$ 减去 $k$ ，那么区间 $[l,n]$ 全部加上了 $k$ ，区间 $[r+1,n]$ 全部减去了 $k$ ，

其中，区间 $[r+1,n]$ 先加上了 $k$ ，又减去了 $k$ ，刚好抵消，因此不会变。

所以，用这种方法，我们就能做到 $O(1)$ 修改啦\(^o)/！

当然，最后查询的时候，还是要 $O(n)$ 恢复一下原数组。

代码实现：

scanf("%d%d",&n,&p);        //n 是数组大小，p 是操作次数
while(p--){
    int l,r;
    scanf("%d%d",&l,&r);
    d[l]++,d[r+1]--;        //刚才说过的差分
}
for(int i=1;i<=n;i++){
    a[i]=a[i-1]+d[i];       //还原数组
}

2.查询所有数的中位数

当然可以一个sort排序之后，输出最中间的那个数。

不过这么做复杂度是 $O(n \log n)$ ，虽然可以过(?)，但是爱学习的我们怎么会止步于此呢？当然要继续优化啦！

一种方法是用桶排，期望复杂度 $\Theta(n)$ ，不过这里不展开说明。

其实，此题就是要求在一个数组里面查询第 $(n\div2+1)$ 大的数啦。

而线性找第 $k$ 大的数是完全可以做到的。

我们使用类似快速排序的「分治」思想，在使用快速排序「划分」后，把数组 $A_l\dots A_r$ 划分成 $A_l\dots A_{mid}$ 与 $A_{mid+1}\dots A_r$。

此时比较左边元素数量（即 $mid-l+1$）与 $k$ 的大小关系，然后判断在左边还是右边递归求解。

代码实现：

int ans,k;
void find_kth(int a[],int l,int r){
    if(l==r){				//如果找到了，记录答案
        ans=a[l];
        return;
    }
    int i=l,j=r,f=a[(l+r)/2];
    do{
        while(a[i]<f){		//从左边找比哨兵大的值
            i++;
        }
        while(a[j]>f){		//从右边找比哨兵大的值
            j--;
        }
        if(i<=j){			//如果 i<=j
            swap(i,j);		//就交换
            i++,j--;
        }
    }while(i<=j);
    if(k<=j){				//在左区间
        find_kth(a,l,j);
    }
    else if(i<=k){			//在右区间
        find_kth(a,i,r);
    }
    else{					//既不在左区间，也不在右区间
        find_kth(a,j+1,i-1);
    }
}

当然，STL 中有一个好用的 nth_element ，其参数为：nth_element(数组名,数组名+第k小元素,数组名+元素个数)。

作用就是把数组中的第 k 个元素换成这个数组中第 k 小的元素。期望复杂度 $O(n)$ 。

#include<cstdio>
#include<algorithm>
#define MAXN 1000005
using namespace std;
int a[MAXN],d[MAXN];
int n,p;
int main(){
    scanf("%d%d",&n,&p);                //n 是数组大小，p 是操作次数
    while(p--){
        int l,r;
        scanf("%d%d",&l,&r);
        d[l]++,d[r+1]--;                //刚才说过的差分
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+d[i];               //还原数组
    }
    nth_element(a+1,a+n/2+1,a+n+1);     //STL 大法好！
    printf("%d\n",a[n/2+1]);
    return 0;
}

顺利AC！