洛谷题目链接
Atcoder题目链接
前言
这道题我赛时想到了正解并打了出来，然后因为把\(l\)打成了\(1\)导致WA\(\times 23\)，然后又没场切六道题（悲。
然后赛后有人说正解是珂朵莉树/线段树，然而我是珂朵莉树\(+\)线段树，呵。
题意
数轴上有\(n\)个人，第\(i\)个人初始在\(X_i\)处，每一次操作可以选择一个人，若目标位置没有其它人则可以将这个人的位置\(+1\)或\(-1\)，现在你需要按顺序满足\(q\)个要求，对于要求\(i\)，你需要让从左往右第\(T_i\)个人在数轴上的\(G_i\)处。求你满足所有要求后的最小操作次数。
\(1\le n,q\le 2\times 10^5\)，\(0\le G_i\le 10^8\)，\(0\le X_1<X_2<...<X_n\le10^8\)。
思路
先看一下这道题感觉是一道数据结构题，然后是在线的（还没想到离线怎么做，好像不好做吧），时间复杂度允许\(O(n\log^2 n)\)或\(O(n\sqrt n)\)什么的，然后先考虑线段树。
我们知道线段树可以维护等差数列（详见洛谷P1438），所以只要我们知道了每一次操作会移动哪些棋子，我们可以进行区间的等差数列赋值，求出任意时刻每一个棋子所在的位置。
然后就是怎么求答案。
设\(sum_{l,r}\)为标号为\([l,r]\)的棋子的位置总和，\(a_i\)为\(i\)所在的位置。
然后我们需要将第\(l\)个棋子挪到\(x\)处（先假设\(x>a_l\)）且第\(r\)个棋子也要动但第\((r+1)\)个棋子不动（即\(a_r<x+r-l\)且\(a_{r+1}\ge x+r-l+1\)），则贡献为操作后位置的和减去操作前位置的和，为\([x+(x+r-l)]\times (r-l+1)\div 2-sum_{l,r}\)。
对于\(x<a_l\)的情况，先找出最左端要动的棋子\(r\)（注意，此处\(r\le l\)），那么，可以转化一下，\(x\gets x-r+l\)，然后\(swap(l,r)\)，此时的贡献为\(|[x+(x+r-l)]\times (r-l+1)\div 2-sum_{l,r}|\) 。
然后找左右边要动的最边上的棋子（即上文的\(r\)）就直接二分，如果\(x>a_l\)，则往右搜，找到\(a_r<x+r-l\)且\(a_{r+1}\ge x+r-l+1\)这样的\(r\)；如果\(x<a_l\)，则往左搜，找到\(a_r>x-r+l\)且\(a_{r-1}\le x-r+l-1\)（此处的\(x\)还是输入的\(x\)，未经过转化）。
所以该怎么维护这个\(sum\)数组呢，可以用线段树维护区间和，但是我赛时没想到。
取而代之，我用了珂朵莉树。因为每一次操作都会将\([l,r]\)的位置变为连续的等差数列，所以考虑维护一段一段，每一段皆为一段等差数列，这样对于每一段我们可以直接\(O(1)\)求出他的位置和。时间复杂度分析：初始有\(n\)段，每一次操作最多新产生\(1\)段，遍历了的段会合成1段，即使就算全部合并遍历加上set也只有\(O((n+q)\log n)\)。
因为二分会用到每一个棋子的实时位置，所以要用线段树维护每一个棋子的实时位置，二分时间复杂度为\(O(q\log^2 n)\)。
则最终时间复杂度为\(O(q\log^2n+(n+q)\log n)\)。随便能过。
代码
真的好长，真不知道赛时是怎么想的。
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define int long long
#define iter set<node>::iterator
const int N=5e5+5;
int n,tmp,a[N];
int ans;
struct seg
{int st;//该区间的首项 bool chg;//是否更新过
}s[N<<2];
struct node
{int l,r;//这个段的左端点 mutable int st;//这个段的首项（公差恒为1所以可以省略） node(int l,int r=0,int st=0): l(l),r(r),st(st){}bool operator<(const node &b)const{return l<b.l;}//以每段左端点从小到大排序
};
set<node> q;
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
iter split(int pos)//珂朵莉树分裂操作
{iter it=q.lower_bound(node(pos));if(it!=q.end()&&it->l==pos) return it;//如果本身就是段头 it--;if(it->r<pos) return q.end(); //如果pos太大 int l=it->l,r=it->r,st=it->st;q.erase(it);//删除原来的块 q.insert(node(l,pos-1,st));//分成两个 return q.insert(node(pos,r,st+pos-l)).first;//右边这个段是含pos的，返回指针
}
void assign(int l,int r,int st)
{iter itr=split(r+1),itl=split(l);//先分后面再分前面，这样itl不会失效 int res=0;for(iter i=itl;i!=itr;i++) {//遍历中间所有段 int l=i->l,r=i->r,st=i->st;res+=(st+st+r-l)*(r-l+1)/2;//对于每一段求和 } ans+=abs(tmp-res);//更新答案 q.erase(itl,itr);//删掉中间的所有段 q.insert(node(l,r,st));//加入一个新的整的段
}
void pushdown(int l,int r,int rt)
{if(s[rt].chg)//是否修改 {int mid=(l+r)>>1;s[rt<<1].chg=1;s[rt<<1|1].chg=1;s[rt<<1].st=s[rt].st;s[rt<<1|1].st=s[rt].st+(mid+1-l);s[rt].chg=0;}
}
void build(int l,int r,int rt)
{if(l==r){s[rt].st=a[l];//初始位置 return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int rt,int L,int R,int st)
{//这里传下的st只针对L的 if(L<=l&&R>=r){s[rt].st=st+l-L;//所以还需转化 s[rt].chg=1;return;}pushdown(l,r,rt);int mid=(l+r)>>1;if(L<=mid) update(l,mid,rt<<1,L,R,st);if(R>mid) update(mid+1,r,rt<<1|1,L,R,st);
}
int query(int l,int r,int rt,int pos)//查询某一位置上的值
{if(l==r) return s[rt].st;pushdown(l,r,rt);int mid=(l+r)>>1;if(pos<=mid) return query(l,mid,rt<<1,pos);return query(mid+1,r,rt<<1|1,pos);
}
bool check(int l,int r,int x,bool f)
{//判断是否会动这颗棋子 if(f==0)//如果x>a[l] {int num=r-l+x;if(num<=query(1,n,1,r)) return false;return true;}else//如果x<a[l] {int num=x-r+l;if(num>=query(1,n,1,l)) return false;return true;}
}
int mids(int u,int x)
{int w=query(1,n,1,u);if(w<=x)//如果x>a[l] {int l=u,r=n,ans=u;while(l<=r){int mid=(l+r)>>1;if(check(u,mid,x,0)) l=mid+1,ans=mid;else r=mid-1;}return ans;}else //如果x<a[l] {int l=1,r=u,ans=u;while(l<=r){int mid=(l+r)>>1;if(check(mid,u,x,1)) r=mid-1,ans=mid;else l=mid+1;}return ans;}
}
void print(int ans)//快输
{if(ans==0) return;print(ans/10);putchar(ans%10+'0');
}
signed main()
{n=read();for(int i=1;i<=n;i++) {a[i]=read();q.insert(node(i,i,a[i]));//起初是n个段 }build(1,n,1);//初始化线段树 int q=read();while(q--){int u=read(),x=read();int pos=mids(u,x);//二分 if(pos<u){x-=u-pos;swap(pos,u);//转化x }tmp=(x+x+pos-u)*(pos-u+1)/2;//计算操作后位置的和 assign(u,pos,x);//求和+推平 update(1,n,1,u,pos,x);//更新线段树 }print(ans);//输出 return 0;
}
