P4501 [ZJOI2018]胖

题目

P4501 [ZJOI2018]胖

官方口中的送分题

做法

我们通过手玩(脑补)，\(a_i\)所作的贡献(能更新的点)为：在\(a_i\)更新\(\forall x\)更新前前没有其他点能把\(x\)更新到更优

我们预处理出数组\(dis[i]\)为\(1\)号点走到\(i\)号点的未包含计划前的距离

对于\(x≤a[i]\Longrightarrow edge[x]=-dis[x]+(l[i]+dis[a[i]])\)，对于\(x≥a[i]\Longrightarrow dis[x]+(l[i]-dis[a[i]])\)

能更新的范围显然是有单调性的，二分左右端点(\(st\)表维护区间最小值判断)，时间复杂度\(O(nlogn^2)\)

My complete code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL maxn=1e6,inf=1e17;

inline LL Read(){

	LL x(0),f(1);char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

LL n,q,K; LL dis[maxn];

struct node{

	LL p,l;

	bool operator < (const node &b)const{

		return p<b.p;

	}

}a[maxn];

struct ST{

	LL st1[maxn][20],st2[maxn][20];

	inline void Init(){

		for(LL i=1;i<=K;++i)

		    st1[i][0]=a[i].l-dis[a[i].p],st2[i][0]=a[i].l+dis[a[i].p];

		for(LL j=1;j<=18;++j)

		    for(LL i=1;i<=K;++i)

		        st1[i][j]=min(st1[i][j-1],st1[i+(1<<j-1)][j-1]),

		        st2[i][j]=min(st2[i][j-1],st2[i+(1<<j-1)][j-1]);

	}

	inline LL Getl(LL x){

		node tmp; tmp.p=x;

		return lower_bound(a+1,a+1+K,tmp)-a;

	}

	inline LL Getr(LL x){

		node tmp; tmp.p=x;

		return upper_bound(a+1,a+1+K,tmp)-a-1;

	}

	inline LL Query1(LL l,LL r){

		if(l>r) swap(l,r); l=max(1ll,l),r=min(n,r);

		l=Getl(l),r=Getr(r);

		if(l>r) return inf;

		LL lg=log2(r-l+1);

		return min(st1[l][lg],st1[r-(1<<lg)+1][lg]);

	}

	inline LL Query2(LL l,LL r){

		if(l>r) swap(l,r); l=max(1ll,l),r=min(n,r);

		l=Getl(l),r=Getr(r);

		if(l>r) return inf;

		LL lg=log2(r-l+1);

		return min(st2[l][lg],st2[r-(1<<lg)+1][lg]);

	}

}ST;

inline bool Check1(LL p,LL x){

	if(!(p^x)) return true;

	LL lt=ST.Query1(2*x-p+1,x)+dis[x];

	LL rt=ST.Query2(x,p-1)-dis[x];

	LL now=ST.Query2(p,p)-dis[x];

	if(lt<=now||rt<=now) return false;

	if(2*x-p>=1) return ST.Query1(2*x-p,2*x-p)+dis[x]>=now;

	return true;

}

inline bool Check2(LL p,LL x){

	if(!(p^x)) return true;

	LL lt=ST.Query1(p+1,x)+dis[x];

	LL rt=ST.Query2(x,2*x-p-1)-dis[x];

	LL now=ST.Query1(p,p)+dis[x];

	if(lt<=now||rt<=now) return false;

	if(2*x-p<=n) return ST.Query2(2*x-p,2*x-p)-dis[x]>now;

	return true;

}

inline LL Solve1(LL p){

	LL l(1),r(p),ret(p);

	while(l<=r){

		LL mid(l+r>>1);

		if(Check1(p,mid)) r=mid-1,ret=mid;

		else l=mid+1;

	}return ret;

}

inline LL Solve2(LL p){

	LL l(p),r(n),ret(p);

	while(l<=r){

		LL mid(l+r>>1);

		if(Check2(p,mid)) l=mid+1,ret=mid;

		else r=mid-1;

	}return ret;

}

int main(){

	n=Read(),q=Read();

	for(LL i=2;i<=n;++i)

	    dis[i]=dis[i-1]+Read();

	while(q--){

		K=Read();

		for(LL i=1;i<=K;++i) a[i]=(node){Read(),Read()};

		sort(a+1,a+1+K);

		ST.Init();

		LL ret(0);

		for(LL i=1;i<=K;++i) ret+=(Solve2(a[i].p)-Solve1(a[i].p)+1);

		printf("%lld\n",ret);

	}return 0;

}

巴特西

P4501 [ZJOI2018]胖

题目

做法

My complete code

最新文章

热门文章