LibreOJ 2551 「JSOI2018」列队

首先，显然集合后与集合前学生的相对位置不变。
第二，可以找到一个位置，使得在这个位置左边的学生都往右跑，右边的都往左跑。（因为往左往右往左往右太沙雕了……）

假设我们把 a 数组 [l,r] 区间里的数放到了 b 数组里且其有序，并且已经知道了这个分界点和有 c 个学生是往右跑的。
那么这 c 个往右的学生的贡献应该是 c∑i=1K+i−1−bi。
拆开得 K+c−1∑i=Ki−c∑i=1bi。
显然前者就是一个等差数列。

类似的，我们把另一边拆得 r−l+1∑c+1bi−K+r−l∑i=K+ci。

如果我们知道了这个分界点，求出答案就很简单了，只需要使用主席树。
但是我们不知道啊！

考虑二分。
乍一看答案的单调性不明显，但是它只会分成两部分，而且分界点的变化是单调性的。

于是在主席树上二分即可。

代码：

#include <cstdio>
using namespace std;
const int N = 5e5;
const int C = 1e6;
int n,m;
struct node
{
    int cnt;
    long long sum;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot;
    seg[p].cnt += k,seg[p].sum += (long long)x * k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,seg[p].ls,tl,mid);
    else
        insert(x,k,seg[p].rs,mid + 1,tr);
}
long long query(int k,int c,int u,int v,int tl,int tr)
{
    if(!(seg[v].cnt - seg[u].cnt))
        return 0;
    int mid = tl + tr >> 1;
    int cnt = seg[v].cnt - seg[u].cnt;
    long long sum = seg[v].sum - seg[u].sum;
    if(tl >= k + c)
        return sum - (long long)(k + c + k + c + cnt - 1) * cnt / 2;
    if(tr <= k + c + cnt - 1)
        return (long long)(k + c + k + c + cnt - 1) * cnt / 2 - sum;
    return query(k,c,seg[u].ls,seg[v].ls,tl,mid) + query(k,c + seg[seg[v].ls].cnt - seg[seg[u].ls].cnt,seg[u].rs,seg[v].rs,mid + 1,tr);
}
int main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&x),insert(x,1,rt[i] = rt[i - 1],1,C);
    int l,r,k;
    while(m--)
        scanf("%d%d%d",&l,&r,&k),printf("%lld\n",query(k,0,rt[l - 1],rt[r],1,C));
}