前言
这道题我赛时想到了正解并打了出来,然后因为把\(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;
}
标签:rt,return,int,题解,mid,st,ABC371F,ans,Narrow
From: https://www.cnblogs.com/hard-plan/p/18426075