P4559 [JSOI2018]列队
首先思考：
对于 [ l , r ] [l,r] [l,r]区间内的同学，他们集合之后与集合之前的相对大小是不会改变的，所有无论是否集合他们的相对的顺序是不变的，那么集合到 [ k , k + r − l ] [k,k+r-l] [k,k+r−l]的时候，他们的位置一定是固定的，我们可以将其称之为最终位，我们将他们的相对大小记为 r a n k i rank_i ranki。
那么这么思考，有一部分一定往右跑，有一部分一定往左跑。
如果一个同学向右跑，他的起始位置都知道，那么他跑的距离就是 k + r a n k i − 1 − a i k+rank_i-1-a_i k+ranki−1−ai
如果想做跑，那么他跑的距离就是 − ( k + r a n k i − 1 − a i ) -(k+rank_i-1-a_i) −(k+ranki−1−ai)
我们可以采取主席树来存他们的位置，那么就相当于一个区间前缀的问题，如果在一个子区间内所有同学都像同一个方向跑，那么就可以直接得出答案。
首先对于这个区间，我们可以确定在这个区间内的同学的 r a n k i rank_i ranki一定是连续的，以往右跑的同学为例他们跑的距离的总和就是 ( k − 1 + r k l − a l ) + . . . . + ( k − 1 + r k r − a r ) = − ∑ a i + ∑ ( k − 1 + r k i ) (k-1+rk_l-a_l)+....+(k-1+rk_r-a_r)=-{\sum{a_i}}+{\sum{(k-1+rk_i)}} (k−1+rkl−al)+....+(k−1+rkr−ar)=−∑ai+∑(k−1+rki),其中 r k i rk_i rki是差为 1 1 1，且长度为 r − l + 1 r-l+1 r−l+1的等差数列，可以利用等差数列求和的方式求得。另外注意，等差数列的项数应当是这个区间的人数，而不是 r − l + 1 r-l+1 r−l+1。根据上述的推理我们很容易发现想做跑的同学距离和为 ∑ a i − ∑ ( k − 1 + r k i ) {\sum{a_i}}-{\sum{(k-1+rk_i)}} ∑ai−∑(k−1+rki)。
那么我们如何判断一个区间可以用于求解呢？
首先我们判断这个区间的人是往左跑还是往右跑，如果一个区间的人往左跑，那么很容易发现其判定条件是 p o s > = k + ∑ s i z e l s pos>=k+{\sum{size_{ls}}} pos>=k+∑sizels， s i z e l s size_{ls} sizels代表这个区间左边的人的个数，往右跑的稍微难想一点，答案是 p o s < = k + ∑ s i z e l s + ∑ s i z e l e n − 1 pos<=k+{\sum{size_{ls}}}+{\sum{size_{len}}}-1 pos<=k+∑sizels+∑sizelen−1,其中 ∑ s i z e l e n {\sum{size_{len}}} ∑sizelen代表在 [ l , r ] [l,r] [l,r]中的人数。文章来源：https://www.toymoban.com/news/detail-485603.html
对于人数的求取我们可以采取权值线段树存数的个数，对于 ∑ a i {\sum{a_i}} ∑ai我们可以用主席树维护其前缀和，做法和今年ICPC昆明的M题有异曲同工之妙。文章来源地址https://www.toymoban.com/news/detail-485603.html
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
using namespace std;
const int mod=998244353;
const int M=1e8+5;
const int N=1e6+5;//?????????? 4e8
int rt[N];
int tot,n,m;
struct node
{
int l,r;
ll sum,val;
}e[N*80];
void insert(int &p,int pre,int l,int r,int pos)
{
e[++tot]=e[pre];
p=tot;
e[tot].sum+=pos,e[tot].val++;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) insert(e[p].l,e[pre].l,l,mid,pos);
else insert(e[p].r,e[pre].r,mid+1,r,pos);
}
ll ask(int L,int R,int l,int r,int k,int f)
{
ll sum=e[R].sum-e[L].sum;
ll val=e[R].val-e[L].val;
if(val==0) return 0;
if(l>=f+k) return sum-(2*k+2*f+val-1)*val/2;
if(r<=k+f+val-1) return -sum+(2*k+2*f+val-1)*val/2;
int mid=(l+r)>>1;
return ask(e[L].l,e[R].l,l,mid,k,f)+ask(e[L].r,e[R].r,mid+1,r,k,f+e[e[R].l].val-e[e[L].l].val);
}
void solve()
{
cin>>n>>m;
for(re i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
insert(rt[i],rt[i-1],1,N-5,x);
}
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%lld\n",ask(rt[l-1],rt[r],1,N-5,k,0));
}
}
signed main()
{
int T=1;
// cin>>T;
for(int index=1;index<=T;index++)
{
// printf("Case %d:\n",index);
solve();
// puts("");
}
return 0;
}
/*
1
6 5
0 0 0 122 499 8888
*/
到了这里，关于可持久化线段树15（思维+乱搞）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
