https://www.lydsy.com/JudgeOnline/problem.php?id=5319
https://www.luogu.org/problemnew/show/P4559
题面见上。
40pts：
不难想到询问应当在主席树上做。
[l,r]为我们询问的这些人所在位置的坐标区间，[l1,r1]为这些人最终要去这个区间里站着。
我们维护主席树节点代表的区间的人数，则设当前节点左子树人数为ls，则可以递归处理[l,mid][l1,l1+ls-1]和[mid+1,r][l1+ls,r1]，复杂度O(n^2)。
100pts：
然后我们就试图剪枝呗看看我们能剪成啥样。
我们能处理r<=l1和r1<=l的情况吗？当然可以。
我们举前一种情况为例（后面的情况基本同理）：
只需要先让这些人都跑到l1，然后再让这些人在[l1,r1]站好就行了。
于是算出这些人到l1的距离，再算这些人在[l1,r1]的体力值就行了，主席树维护当前人坐标之和即可做到前者，而后者就是等差数列求和。
其实写到这里就可以AC了（数据有点弱（笑））。
真·100pts：
那我们继续想，我们能处理r<=r1和l1<=l的情况吗？当然可以。
还是举前一种情况为例（后面的情况基本同理）：
只需要先让这些人都跑到r1，然后再让这些人在[l1,r1]站好就行了。
注意唯一不同的是"站好"这个过程实际上是“退流”——退体力值的过程，因为我们能够证明这种情况下每个人只可能跑多不可能跑少，所以我们前者减后者即可，维护方法同上。
那么复杂度到底是什么呢？思考一下不难发现，当mid<=l1+ls-1时候我们前子问题可以O(1)算出，后子问题O(log)继续递归，当mid>l1+ls-1时后子问题可以O(1)算出，前子问题O(log)继续递归。
复杂度O(nlog)可以通过本题。
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+;
const int M=1e6;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct tree{
int l,r,sum;
ll dis;
}tr[M*+];
int n,m,pool,rt[N];
void insert(int y,int &x,int l,int r,ll a){
tr[x=++pool]=tr[y];
tr[x].sum++;tr[x].dis+=a;
if(l==r)return;
int mid=(l+r)>>;
if(a<=mid)insert(tr[y].l,tr[x].l,l,mid,a);
else insert(tr[y].r,tr[x].r,mid+,r,a);
}
ll query(int nl,int nr,int l,int r,int l1,int r1){
if(l1>r1)return ;
if(r<=r1){
return (ll)r1*(r1-l1+)-(tr[nr].dis-tr[nl].dis)-(ll)(r1-l1)*(r1-l1+)/;
}
if(l1<=l){
return (tr[nr].dis-tr[nl].dis)-(ll)l1*(r1-l1+)-(ll)(r1-l1)*(r1-l1+)/;
}
int mid=(l+r)>>;
int delta=tr[tr[nr].l].sum-tr[tr[nl].l].sum;
return query(tr[nl].l,tr[nr].l,l,mid,l1,l1+delta-)
+query(tr[nl].r,tr[nr].r,mid+,r,l1+delta,r1);
}
int main(){
n=read(),m=read();
for(int i=;i<=n;i++)insert(rt[i-],rt[i],,M,read());
for(int i=;i<=m;i++){
int l=read(),r=read(),k=read();
printf("%lld\n",query(rt[l-],rt[r],,M,k,k+r-l));
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++