[JSOI2018]军训列队
题目大意：
\(n(n\le5\times10^5)\)个学生排成一排，第\(i\)个学生的位置为\(a_i\)。\(m(m\le5\times10^5)\)次命令，每次将编号在\([l,r]\)之间的学生移动到\([k,k+r-l]\)位置上，每个位置站一个人，顺序自定（无需考虑原来在\([k,k+r-l]\)位置上的人）。每次的代价为每个人移动距离之和。求每次操作的最小代价。
思路：
建立主席树，维护每个区间内人数和与坐标和。
考虑所有人都在区间\([k,k+r-l]\)以左/右的情况，答案就是每个人坐标和与区间\([k,k+r-l]\)坐标和之差。
否则将学生按照坐标大小分成两部分考虑，若坐标较小的学生有\(d\)个，统计将两部分人分别放入区间\([l,l+d)\)和\([l+d,r]\)的代价即可。
时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include#include typedef long long int64;inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}const int N=5e5+1,M=1e6,logM=30;class FotileTree { private: struct Node { int64 sum; int cnt,left,right; }; Node node[N*logM]; int sz,new_node(const int &p) { node[++sz]=node[p]; return sz; } int length(const int &b,const int &e) const { return e-b+1; } public: int root[N]; void insert(int &p,const int &b,const int &e,const int &x) { p=new_node(p); node[p].cnt++; node[p].sum+=x; if(b==e) return; const int mid=(b+e)>>1; if(x<=mid) insert(node[p].left,b,mid,x); if(x>mid) insert(node[p].right,mid+1,e,x); } int64 query(const int &q,const int &p,const int &b,const int &e,const int &l,const int &r) const { const int len=length(l,r); const int64 dsum=node[p].sum-node[q].sum; if(l>=e) return (int64)(l+r)*len/2-dsum; if(r<=b) return dsum-(int64)(l+r)*len/2; const int mid=(b+e)>>1,d=node[node[p].left].cnt-node[node[q].left].cnt; int64 ret=0; if(b<=mid&&l<=l+d-1) ret+=query(node[q].left,node[p].left,b,mid,l,l+d-1); if(mid+1<=e&&l+d<=r) ret+=query(node[q].right,node[p].right,mid+1,e,l+d,r); return ret; }};FotileTree t;int main() { const int n=getint(),m=getint(); for(register int i=1;i<=n;i++) { t.insert(t.root[i]=t.root[i-1],1,M,getint()); } for(register int i=0;i