题解：P6309 「Wdsr-1」人间之里

· · 题解

P6309 「Wdsr-1」人间之里 题解

/bangbangt（指棒棒题）。教练讲了一遍就懂了，教练太有实力了。

题目大意

每个房子有位置 x_{1 \sim n} 和人数 v_{1 \sim n}，l \sim r 区间避难所为 z 时不便程度为 \displaystyle\sum_{i=l}^{z-1} [v_i \times (x_i-z)]+\displaystyle\sum_{i=z+1}^{r} [v_i \times (z-x_i)]。现有查询修改操作。

思路

化简不便程度的式子：

=\displaystyle\sum_{i=l}^{z-1} (v_ix_i-v_iz)+\displaystyle\sum_{i=z+1}^{r} (v_iz-v_ix_i) =\displaystyle\sum_{i=l}^{z-1}v_ix_i-z\times\displaystyle\sum_{i=l}^{z-1}v_i+z\times\displaystyle\sum_{i=z+1}^{r}v_i-\displaystyle\sum_{i=z+l}^{r}v_ix_i

只需知道每个区间 v_i 的和与 v_ix_i 的和即可，又有修改，考虑线段树，两棵就好，我用的结构体。

注意到房屋位置（包括查询两端的位置，和修改后的位置）在 -10^9 \sim 10^9 之间，所以将所有输入存下来，把所有位置信息离散化，线段树里放离散后的值就好了。

那 z 咋求呢？

由贪心得，避难所的位置在所有人（不是房子） 的中间，不便程度最小。比如房间人数依次为 \{2,1,0,3,4\} 时，总人数是 10 ，人数的一半就是 5，而第五个人在 v_4 的房屋里，所以 v_4 为避难所最优。我们要求出这个点，就是求区间内第“区间人数和 /2”小的数，可以将线段树当做权值线段树求第 k 小的数来写，k=[(\displaystyle\sum_{i=l}^{r}v_i)+1]/2。要 +1 因为要向上取整。（若总共有 9 个人，第 5 个人是最中间的。）

注意！求的是区间内第 k 小的数，所以对于整棵树，求的就是第 \displaystyle\sum_{i=1}^{l-1}v_i+k 小的数。

代码中有详细注释和草图，可参考。

Code

惆怅惆怅的代码，改了好几遍才过。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=3e5+5;
int n,m;
struct node
{
    int pos,val;
}a[N]; // 房屋信息
struct inin
{
    int op,x,y,k;
}q[N]; // 存储输入
int b[N*3]; // 所有位置进行离散化
// 初始位置n个，询问或更新用到的位置m*2个，因为询问的左右两个端点有可能都未离散
int cnt; // 所有位置的数量
int len; // 离散化后所有位置的数量，去重后的
struct tree
{
    int sum,mul; 
    // sum:区间人数和
    // mul:区间每个房子的（和*位置），位置是未离散的
}tr[N*3*4]; // 线段树4倍空间

void push_up(int k)
{
    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    tr[k].mul=tr[k<<1].mul+tr[k<<1|1].mul;
}

void change(int l,int r,int k,int v)
{
    tr[k].sum+=v;
    tr[k].mul+=b[l]*v; // 注意是b[l]不是l，要用未离散的位置
}
void update(int p,int v,int l,int r,int k)
{
    if(p==l && p==r)
    {
        change(l,r,k,v);
        return ;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
      update(p,v,l,mid,k<<1);
    if(mid+1<=p)
      update(p,v,mid+1,r,k<<1|1);
    push_up(k);
}

tree query(int ll,int rr,int l,int r,int k)
{
    if(ll>rr)
      return {0,0}; // 剪枝越界了找不到
    if(ll<=l && r<=rr)
      return tr[k];
    int mid=(l+r)>>1;
    if(rr<=mid) // 不包含要求的区间，且要求的区间偏左
      return query(ll,rr,l,mid,k<<1);
    if(mid+1<=ll) // 不包含要求的区间，且要求的区间偏右
      return query(ll,rr,mid+1,r,k<<1|1);
    tree lt=query(ll,rr,l,mid,k<<1);
    tree rt=query(ll,rr,mid+1,r,k<<1|1);
    return {lt.sum+rt.sum,lt.mul+rt.mul}; // 合并区间
}

int query_pos(int x,int l,int r,int k)
{
    if(l==r)
      return l; // 这里回的是离散后的，因为不计入最终输出
    int mid=(l+r)>>1;
    if(tr[k<<1].sum>=x) // 当左面数很多，说明第x小的数在左面
      return query_pos(x,l,mid,k<<1); // 去左面
    return query_pos(x-tr[k<<1].sum,mid+1,r,k<<1|1);
    // 否则去右面，变成求第（之前要求的第x小 - 左面数的数量）小的数
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
      scanf("%lld",&a[i].pos),b[++cnt]=a[i].pos; // 记录要离散的位置，记得++b数组的下标
    for(int i=1;i<=n;i++)
      scanf("%lld",&a[i].val);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&q[i].op);
        if(q[i].op==1)
        {
            scanf("%lld%lld",&q[i].x,&q[i].y); // 记录询问
            b[++cnt]=q[i].x;
            b[++cnt]=q[i].y; // 这俩也要离散
        }
        if(q[i].op==2)
        {
            scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].k); // 记录修改
            b[++cnt]=q[i].y; // x是第几个，不是位置，不用离散
        }
    }
    sort(b+1,b+cnt+1);
    len=unique(b+1,b+cnt+1)-b-1; // 离散
    for(int i=1;i<=n;i++) // 先把初始的更新了
    {
        int x=lower_bound(b+1,b+len+1,a[i].pos)-b; // 取离散化后的位置
        update(x,a[i].val,1,len,1);
    }
    for(int i=1;i<=m;i++) // 处理询问+修改
    {
        if(q[i].op==1)
        {
            int x=lower_bound(b+1,b+len+1,q[i].x)-b;
            int y=lower_bound(b+1,b+len+1,q[i].y)-b; // 离散后的左右端点
            int z=query_pos( query(1,x-1,1,len,1).sum + 
                                  (query(x,y,1,len,1).sum+1)/2 ,1,len,1);
            /* z是避难所的位置，在区间人数和的一半的位置，换成权值线段树的话就是：
               求第k小的数的位置，k=(1~(区间左端点-1)的人数和)+区间人数和的一半（注：这个一半向上取整，所以(+1)/2）
               因为这棵树存的是整个村，不是询问的那个区间，所以要把区间左面所有房屋都算上
                 这是询问的区间--> ____________
               ------------------|-----------|-------
               |_______________________| <--这是要找的k，它的右端点就是避难所的位置
            */
            tree l=query(x,z-1,1,len,1);
            tree r=query(z+1,y,1,len,1); // 左半人数和&右半人数和
            int ans=(b[z]*l.sum-l.mul)+(r.mul-b[z]*r.sum); // 文中讲的公式
            printf("%lld\n",ans);
        }
        if(q[i].op==2)
        {
            int id=q[i].x; // 要修改的房屋
            int oldp=lower_bound(b+1,b+len+1,a[id].pos)-b; // 修改前的位置，离散后的
            if(a[id].val) // 屋里有人
              update(oldp,-a[id].val,1,len,1); // 把人数清空掉
            int newp=lower_bound(b+1,b+len+1,q[i].y)-b; // 修改后的位置，离散后的
            update(newp,q[i].k,1,len,1);
            a[id]={q[i].y,q[i].k}; // 更新房屋信息
        }
    }
    return (0.0);
}

给我赞赞 qwq