首页 > 其他分享 >[ABC371F] Takahashi in Narrow Road 题解

[ABC371F] Takahashi in Narrow Road 题解

时间:2024-09-22 23:01:25浏览次数:7  
标签:rt return int 题解 mid st ABC371F ans Narrow

洛谷题目链接

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;
}

标签:rt,return,int,题解,mid,st,ABC371F,ans,Narrow
From: https://www.cnblogs.com/hard-plan/p/18426075

相关文章

  • CF1239E Turtle 题解
    Description一只乌龟从\(2\timesn\)的棋盘的左上角走到右下角,只能往下或往右,需要给出一种方案来分配\(2n\)个数字使得乌龟走过的路径上的数之和的最大值最小。\(2\leqn\leq25,0\leqa_{1,i},a_{2,i}\leq5\times10^4\)。Solution设\(pre_{i}=\sum_{j=1}^{i}{a_{1,i}......
  • P5975 photo 题解
    Solution先离散化,记\(f(l,r,p)\)为覆盖了\([l,r]\)区间内纵坐标\(\gep\)的点最少矩形个数。则:\[f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p))\]\[f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1)\]令\(h\)为用面积为\(S\)的矩形去覆盖\([l,r]\)区间的高度,即\(S/(r......
  • P9192 Pareidolia 题解
    Statement给串\(t\),定义\(B(s)\)为\(s\)删一些字符后能出现最多多少个bessie,\(A(t)\)表示对\(t\)的所有子串\(s\)求\(B(s)\)的和,有\(q\)次单点修改,每次改完输出\(B(s)\).Solution动态dp,但是带矩乘\(6^3\)常数,不好.还是考虑分治咋做.现在有区间\([l,mid],......
  • P3703 树点涂色 题解
    Statement树,每个点有一个颜色,初始每个点颜色互不相同到根链涂上新颜色链颜色数\(u\)子树内点\(v\)到根路径的最多颜色数Solution首先,相同颜色的点一定构成一条从下往上的链考虑LCT,维护一个性质:一条实链的点的颜色相同.于是\(u\)到根的颜色数\(=\)\(u\)到根的虚......
  • 最长公共子串 题解
    StatementQ7.1.2.4,时限4s给一个串,定义\(\mathrm{LCS}\)为最长公共子串长度,\(q\)次询问,每次给出\(l,r\),求\[\operatorname{xor}_{i=1}^{r-l+1}\{i+\mathrm{LCS}(S[l,l+i-1],S[l+i-1,r])\}\]\(n\le10^5,q\le30\)Solutiontag:SA,线段树维护分治结构,orzhunction题目就是......
  • BZOJ 2555 = P5212 SubString 题解
    Statement给你一个字符串 \(\text{init}\),要求你支持两个操作:在当前字符串的后面插入一个字符串;询问字符串 \(s\) 在当前字符串中出现了几次?(作为连续子串)你必须在线支持这些操作。Solutionextend中link[cur]=q,相当于link,链加新建copy那里,相当于link,cut,链加询......
  • 2024 秋季模拟赛题解
    2024秋季模拟赛题解CSP-S模拟赛2024.9.8CSP-S模拟赛28T1签到题。对\(b\)分解质因数后便容易求解。T2考虑枚举\(\gcd(S)\)的取值\(x\),则\(\operatorname{lcm}(S)=m-x\)。那么同时变形\(\gcd\)和\(\operatorname{lcm}\)变为\(\gcd(S)=1,\operatorname{lcm}......
  • BZOJ 3277 串 题解
    Statement给 \(n\) 个串,问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。Solution1%%注意到\(\text{LCP}\)在后缀排序后一定是连续的一段,包含一个串的区间是连续的先预处理出对于所有左端点\(l\),最左的\(r\)满足\([l..r]\)中出现了至少\(k\)个......
  • BZOJ 4310 跳蚤 题解
    Statement把\(S\)分成不超过\(k\)段,使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串,check中从右往左贪心地划分,需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<......
  • BZOJ 4545 DQS 的 trie 题解
    Statement维护一棵树,边权\(\in\{\texttta,\textttb,\textttc\}\),根为\(1\),定义这棵树的子串为从\(1\)走到所有点构成的字符串的所有后缀,需要支持以下操作:问当前树的本质不同子串数给一个点添加一棵子树问一个串在当前树中作为子串的出现次数Solution直接广义SAM+......