M_sea

洛谷4559 [JSOI2018]列队
LuoguBZOJ分析主席树+九条可怜。显然,所有学生跑到指定位置后,相对位置不改变会最优。那么最终会有一部分学生...
扫描右侧二维码阅读全文
17
2019/03

洛谷4559 [JSOI2018]列队

Luogu

BZOJ

分析

主席树+九条可怜

显然,所有学生跑到指定位置后,相对位置不改变会最优。

那么最终会有一部分学生向左跑,一部分学生向右跑,而且两部分一定是分开的。

考虑可持久化权值线段树。

设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。

若当前递归的区间是 $[l,r]$ ,分四种情况:

  • 没有学生,直接返回 $0$ 。
  • 全部向左跑,直接返回 $\sum a_i-\sum(k+rk_i-1)$ 。
  • 全部向右跑,直接返回 $\sum(k+rk_i-1)-\sum a_i$ 。
  • 两种都有,继续递归处理左右两个子区间。

在主席树上重复这个过程计算答案即可。

代码

// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

struct node { int ls,rs,sz; ll sum; } t[N*25];
int rt[N],tot=0;

inline void insert(int& o,int l,int r,int x) {
    t[++tot]=t[o],o=tot,++t[o].sz,t[o].sum+=x;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[o].ls,l,mid,x);
    else insert(t[o].rs,mid+1,r,x);
}

inline ll query(int p,int q,int l,int r,int f,int k) {
    int sz_=t[q].sz-t[p].sz; ll sum_=t[q].sum-t[p].sum;
    if (!sz_) return 0;
    if (l>=k+f) return sum_-((ll)k+f+k+f+sz_-1)*sz_/2;
    if (r<=k+f+sz_-1) return ((ll)k+f+k+f+sz_-1)*sz_/2-sum_;
    int mid=(l+r)>>1,lsz=t[t[q].ls].sz-t[t[p].ls].sz;
    return query(t[p].ls,t[q].ls,l,mid,f,k)
          +query(t[p].rs,t[q].rs,mid+1,r,f+lsz,k);
}

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        rt[i]=rt[i-1];
        insert(rt[i],1,1e6,read());
    }
    for (re int i=1;i<=m;++i) {
        int l=read(),r=read(),k=read();
        printf("%lld\n",query(rt[l-1],rt[r],1,1e6,0,k));
    }
    return 0;
}
最后修改:2019 年 03 月 17 日 08 : 28 PM

发表评论