首先,DP 肯定是逃不掉的,因为直接贪心其实不好判断在两个人都可以上线的时间段究竟是哪个人上线,需要通过后面的情况来做出判断,但是这题值域比较大直接维护 DP 值肯定不行,因此考虑先设计一个与值域有关的 DP 然后优化。
将时间区间离散化,然后依次考虑每个时间区间。一个很自然的想法是设 \(dp_{i,a,b}\) 表示考虑前 \(i\) 个时间区间,此时 Vasya 经验值为 \(a\),Petya 经验值为 \(b\) 是否有可能,但是这样需要考虑 \(O(V^2)\) 个量,显然比较烂,但是我们发现一个性质:如果 \((a,b)\) 可达,那么 \((a-1,b),(a,b-1)\) 均可达,因此我们考虑维护所有可达的点中处于边界位置(即不存在其他 \((a',b')\) 满足 \(a'\ge a\) 且 \(b'\ge b\))的点,我们称这样的点为关键点,那么考虑新加入长度为 \(len\) 的时间区间后的变化:
- 这个时间区间只有 Vasya 上线,那么所有关键点 \((a,b)\) 均变为 \((a+len,b)\)。
- 这个时间区间只有 Petya 上线,那么所有关键点 \((a,b)\) 均变为 \((a,b+len)\)。
- 这个时间区间两人都上线,那么考虑关键点 \((a,b)\):
- 如果 \(|a-b|\le C\),那么显然两人同时上线更优,变为 \((a+2len,b+2len)\)。
- 如果 \(a-b>C\),那么有两种可能,一是两个人都上线,这样都只能得到 \(len\) 的经验值,变为 \((a+len,b+len)\),还有一种是故意让 \(a\) 的经验值变小一点,变得和 \(b\) 刚好差 \(C\),这样这段时间内两人都可以获得 \(2len\) 的经验值,变为 \((b+C+2len,b+2len)\)。
- 如果 \(b-a>C\),情况类似。
由于关键点随着 \(a\) 的增大,\(b\) 必然不断减小,因此考虑平衡树维护这个东西,加入一个时间区间的变化如下:
- 这个时间区间只有 Vasya 上线,直接全局给 \(a\) 这一维 \(+len\)。
- 这个时间区间只有 Petya 上线,直接全局给 \(b\) 这一维 \(+len\)>
- 都上线,我们将平衡树分成 \(a-b>C,|a-b|\le C,b-a>C\) 三部分,不难发现对于 \(a-b>C\) 中让 \(a\) 经验值变小一点的部分,肯定取这一部分中 \(b\) 最小的那一个最优,因此考虑取出 \(a-b>C\) 中 \(b\) 最小的那一个,尝试将 \((b+C,b)\) 加入第二部分中(之所以说是尝试,是因为如果第二部分中存在二维偏序掉 \((b+C,b)\) 的二元组,那么再将其加入平衡树就会破坏掉“随着 \(a\) 的增大,\(b\) 不断减小”的性质,就不行了),对 \(b-a>C\) 的部分也类似。最后将三部分合并的时候,需要将左右两部分被中间二维偏序的部分扔掉(分别是一段后缀和一段前缀)。
时间复杂度 \(O(n\log n)\),讲得不太清楚的地方可以看代码。
const int MAXN=1e6;
mt19937 rng(time(0));
int n1,n2;ll C;vector<pair<ll,int> >vec;
struct node{ll x,y,lzx,lzy;int key,ch[2];}s[MAXN+5];
int rt,ncnt;
void tag(int k,ll vx,ll vy){s[k].x+=vx;s[k].lzx+=vx;s[k].y+=vy;s[k].lzy+=vy;}
void pushdown(int k){
if(!s[k].lzx&&!s[k].lzy)return;
if(s[k].ch[0])tag(s[k].ch[0],s[k].lzx,s[k].lzy);
if(s[k].ch[1])tag(s[k].ch[1],s[k].lzx,s[k].lzy);
s[k].lzx=s[k].lzy=0;
}
int nwnd(ll x,ll y){++ncnt;s[ncnt].x=x;s[ncnt].y=y;s[ncnt].key=rng();return ncnt;}
int merge(int x,int y){
if(!x||!y)return x+y;pushdown(x);pushdown(y);
if(s[x].key<s[y].key)return s[x].ch[1]=merge(s[x].ch[1],y),x;
else return s[y].ch[0]=merge(x,s[y].ch[0]),y;
}
void split(int k,int &x,int &y,auto cmp){
if(!k)return x=y=0,void();pushdown(k);
if(cmp(s[k]))x=k,split(s[k].ch[1],s[k].ch[1],y,cmp);
else y=k,split(s[k].ch[0],x,s[k].ch[0],cmp);
}
int find_mn(int k){
if(!s[k].ch[0])return k;pushdown(k);
return find_mn(s[k].ch[0]);
}
int find_mx(int k){
if(!s[k].ch[1])return k;pushdown(k);
return find_mx(s[k].ch[1]);
}
int main(){
scanf("%d%d%lld",&n1,&n2,&C);
for(int i=1;i<=n1*2;i++){ll x;scanf("%lld",&x);vec.pb(mp(x,1));}
for(int i=1;i<=n2*2;i++){ll x;scanf("%lld",&x);vec.pb(mp(x,2));}
sort(vec.begin(),vec.end());int cur=0;rt=nwnd(0,0);
for(int i=0;i+1<vec.size();i++){
cur^=vec[i].se;ll len=vec[i+1].fi-vec[i].fi;
if(!cur||!len)continue;
if(cur==1){tag(rt,len,0);continue;}
if(cur==2){tag(rt,0,len);continue;}
int k1,k2,k3,k4,k5;
split(rt,k1,k2,[&](node x){return x.x<x.y-C;});
split(k2,k2,k3,[&](node x){return x.x<=x.y+C;});
ll xl=-C,yl=0,xr=0,yr=-C;
if(k1)xl=s[find_mx(k1)].x,yl=xl+C;
if(k3)yr=s[find_mn(k3)].y,xr=yr+C;
if(xl>xr||yl>yr){
if(!k2)k2=nwnd(xl,yl);
else if(yl>s[find_mn(k2)].y)k2=merge(nwnd(xl,yl),k2);
}
if(!k2)k2=nwnd(xr,yr);
else if(xr>s[find_mx(k2)].x)k2=merge(k2,nwnd(xr,yr));
tag(k2,len,len);
ll mxy=s[find_mn(k2)].y,mxx=s[find_mx(k2)].x;
split(k1,k1,k4,[&](node x){return x.y>mxy;});
split(k3,k5,k3,[&](node x){return x.x<=mxx;});
rt=merge(merge(k1,k2),k3);tag(rt,len,len);
}printf("%lld\n",s[find_mx(rt)].x);
return 0;
}
标签:856F,Play,上线,int,ll,Codeforces,len,k2,经验值
From: https://www.cnblogs.com/tzcwk/p/Codeforces-856F.html