题目链接:联合省选 2020 B D1T3/Luogu P6619/LibreOJ 3299。
注:本题与 联合省选 2020 A D1T1 一模一样,所以发了两篇一样的博客。
题目
题目描述
一场比赛即将开始。
每位战士有两个属性:温度和能量,有两派战士:冰系战士的技能会对周围造成降温冰冻伤害,因而要求场地温度不低于他的自身温度才能参赛;火系战士的技能会对周围造成升温灼烧伤害,因而要求场地温度不高于他的自身温度才能参赛。
当场地温度确定时,双方能够参赛的战士分别排成一队。冰系战士按自身温度从低到高排序,火系战士按自身温度从高到低排序,温度相同时能量大的战士排在前面。首先,双方的第一位战士之间展开战斗,两位战士消耗相同的能量,能量少的战士将耗尽能量退出比赛,而能量有剩余的战士将继续和对方的下一位战士战斗(能量都耗尽则双方下一位战士之间展开战斗)。如此循环,直至某方战士队列为空,比赛结束。
你需要寻找最佳场地温度:使冰火双方消耗总能量最高的温度的最高值。
现在,比赛还处于报名阶段,目前还没有任何战士报名,接下来你将不断地收到报名信息和撤回信息。其中,报名信息包含报名战士的派系和两个属性,撤回信息包含要撤回的报名信息的序号。每当报名情况发生变化(即收到一条信息)时,你需要立即报出当前局面下的最佳场地温度,以及该场地温度下双方消耗的总能量之和是多少。若当前局面下无论何种温度都无法开展比赛(某一方没有战士能参赛),则只要输出 Peace
。
数据范围
$10\%$ 的数据:$Q\leq 100,x\leq 10^3$。
另有 $20\%$ 的数据:$Q\leq 10^4,x\leq 5000$,不存在撤回信息,且输入的 $x$ 按顺序不降。
$60\%$ 的数据(包含上述 $20\%$,下同):$Q\leq 2\times 10^5,x\leq 2\times 10^5$。
$90\%$ 的数据:$Q\leq 2\times 10^6,x\leq 2\times 10^6$。
$100\%$ 的数据:$Q\leq 2\times 10^6,x\leq 2\times 10^9$,所有 $y$ 之和不超过 $2\times 10^9$,保证不存在 $t,x,y$ 完全相同的两个战士。
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
联合省选 2020 B D1T3 | $3\text{s}$ | $512\text{MiB}$ |
题解
本题有部分分做法,在介绍解法之前,我们可以先得出答案
$$\texttt{ans}=2\min _ {x _ 0}\{\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i\}$$
解法 A(暴力)
对于 $10\%$ 的数据:$Q\leq 100,x\leq 10^3$。
那么我们不妨开一个以时间下标的数组,每个地方用 vector
存放信息,记录当前时间点的战士信息,这需要我们预先处理出报名信息有效的时间范围,再一个一个赋值、插入。
查询时每个节点上的战士信息先按照温度排序,最后枚举温度 $x$,用前缀和快速算出答案即可。
这种做法的复杂度为 $\Theta(Q^2+Q\max\{x\}\log _ 2Q)$,期望得分为 $10$ 分。
解法 B(还是暴力)
另有 $20\%$ 的数据:$Q\leq 10^4,x\leq 5000$,不存在撤回信息,且输入的 $x$ 按顺序不降。
我们可以把解法 A 的暴力优化一下。
那么我们不妨开一个以时间下标的数组,每个地方用
vector
存放信息,记录当前时间点的战士信息,这需要我们预先处理出报名信息有效的时间范围,再一个一个赋值、插入。
因为没有撤回消息,报名第 $i$ 条报名信息的有效时间一定为 $[i,Q]$,这样我们就不用一个一个插入了,每条报名信息直接插到生效的时间节点上,查询时做个前缀和一样的东西即可。
查询时每个节点上的战士信息先按照温度排序,最后枚举温度 $x$,用前缀和快速算出答案即可。
因为输入的 $x$ 按顺序不降。所以不用排序。
这种做法的复杂度为 $\Theta(Q+Q\max\{x\})$,期望得分为 $20$ 分,加上解法 A 的 $10$ 分,总计能拿到 $30$ 分。
解法 C(常用技巧)
$60\%$ 的数据(包含上述 $20\%$,下同):$Q\leq 2\times 10^5,x\leq 2\times 10^5$。
没有了特殊性质,我们只能从暴力的解法 A 出发,对算法进行优化。
开一个以时间下标的数组,每个地方用
vector
存放信息,记录当前时间点的战士信息,这需要我们预先处理出报名信息有效的时间范围,再一个一个赋值、插入。
仔细思考可以发现一个一个赋值、插入信息实在是太慢了,我们不妨把插入报名信息这个过程高度抽象,视作是对以时间为下标的序列的区间修改。
这使得我们想到了线段树,我们可以通过线段树把统计报名信息的这一部分优化到 $\Theta(Q\log _ 2Q)$。
另外,这种把时间抽象为序列的做法被称作 线段树分治。
查询时每个节点上的战士信息先按照温度排序,最后枚举温度 $x$,用前缀和快速算出答案即可。
枚举是查询这一步的瓶颈所在,我们需要找到一种方法,快速确定使得答案最大的温度 $x$。
假设我们确定了当前比赛选手的信息,
解法 D(数学做法)
$60\%$ 的数据(包含上述 $20\%$,下同):$Q\leq 2\times 10^5,x\leq 2\times 10^5$。
首先仔细观察答案
$$\texttt{ans}=2\min _ {x _ 0}\{\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i\}$$
我们可以把括号里的那个式子拿出来观察
$$\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i+\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i$$
不妨把它切成两个部分
$$f(x _ 0)=\sum _ {i\in\texttt{ice}}[x _ i\leq x _ 0]y _ i$$
$$g(x _ 0)=\sum _ {i\in\texttt{fire}}[x _ i\geq x _ 0]y _ i$$
不难发现,随着 $x _ 0$ 的增大,$f(x _ 0)$ 单调不降,$g(x _ 0)$ 单调不增。
分析答案表达式可知
$$\texttt{ans}=2\min _ {x _ 0}\{f(x _ 0)+g(x _ 0)\}$$
这是一个下凸函数。
但是由于本题对输出的位置存在限制,所以三分完了还要套一个二分。
我们可以三分求最大值,时间复杂度为 $\Theta(Q\log^2 _ 2Q+2Q\log _ 2Q\log _ 3\max\{x\})$,期望得分 $60$ 分。
解法 E(正解)
令 $X(T)=F(T)-I(T)$,显然 $X(T)$ 是个不增函数。如果我们能二分出 $X$ 的零点,就能优化到一个 $\log$。
考虑在线段树上维护,每个节点维护一个 $V$ 的最大值(代码中用的是 $\texttt{ice}$)(也就是这段区间左端点的 $V$ 值)。然后能尽量往右走就往右走。
我们还要找到最大的下标。分类讨论即可。时间复杂度 $\Theta(Q\log _ 2Q)$。
但由于常数原因,这种做法在洛谷上过不了,其他 OJ 能过。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXQ=2000000+5; struct Node{ int val,id; inline Node(reg int val=0,reg int id=0):val(val),id(id){ return; } inline bool operator<(const Node& a)const{ return val<a.val; } }; static char wbuf[1000000]; int wp; inline void pc(reg char x){ if(wp>=1000000) fwrite(wbuf,1,1000000,stdout),wp=0; wbuf[wp++]=x; return; } inline void write(reg int x){ int c[12]={0}; if(!x) return pc('0'),void(); while(x) c[++c[0]]=x%10,x/=10; while(c[0]) pc(c[c[0]--]+'0'); return; } Node V[MAXQ]; struct Message{ int opt,t,x,y; }; Message M[MAXQ]; namespace SegmentTree{ #define lson ( (k) << 1 ) #define rson ( (k) << 1 | 1 ) struct Node{ int L,R; int Max,tagM; int fire,tagF; #define L(x) unit[(x)].L #define R(x) unit[(x)].R #define Max(x) unit[(x)].Max #define tagM(x) unit[(x)].tagM #define fire(x) unit[(x)].fire #define tagF(x) unit[(x)].tagF }; Node unit[MAXQ<<2]; inline void Build(reg int k,reg int l,reg int r){ L(k)=l,R(k)=r,Max(k)=tagM(k)=0; if(l==r) return; reg int mid=(l+r)>>1; Build(lson,l,mid); Build(rson,mid+1,r); return; } inline void AddI(reg int k,reg int val){ Max(k)+=val; tagM(k)+=val; return; } inline void AddF(reg int k,reg int val){ fire(k)+=val; tagF(k)+=val; return; } inline void pushdown(reg int k){ if(tagM(k)){ AddI(lson,tagM(k)); AddI(rson,tagM(k)); tagM(k)=0; } if(tagF(k)){ AddF(lson,tagF(k)); AddF(rson,tagF(k)); tagF(k)=0; } return; } inline void UpdateI(reg int k,reg int l,reg int r,reg int val){ if(R(k)<l||r<L(k)) return; if(l<=L(k)&&R(k)<=r){ AddI(k,val); return; } pushdown(k); UpdateI(lson,l,r,val); UpdateI(rson,l,r,val); Max(k)=Max(lson); return; } inline void UpdateF(reg int k,reg int l,reg int r,reg int val){ if(R(k)<l||r<L(k)) return; if(l<=L(k)&&R(k)<=r){ AddF(k,val); return; } pushdown(k); UpdateF(lson,l,r,val); UpdateF(rson,l,r,val); fire(k)=fire(lson); return; } inline int findI(reg int k,reg int val){ if(Max(k)<val) return 0; if(L(k)==R(k)) return L(k); pushdown(k); if(Max(rson)>=val) return findI(rson,val); else return findI(lson,val); } inline int findF(reg int k,reg int val){ if(fire(k)<val) return 0; if(L(k)==R(k)) return L(k); pushdown(k); if(fire(rson)>=val) return findF(rson,val); else return findF(lson,val); } inline int Query(reg int k,reg int pos){ if(L(k)==R(k)) return Max(k); pushdown(k); reg int mid=(L(k)+R(k))>>1; if(pos<=mid) return Query(lson,pos); else return Query(rson,pos); } #undef lson #undef rson } struct TreeArray{ int size,unit[MAXQ]; #define lowbit(x) ( (x) & ( - (x) ) ) inline void add(reg int ID,reg int val){ for(reg int i=ID;i<=size;i+=lowbit(i)) unit[i]+=val; return; } inline int pre(reg int ID){ reg int res=0; for(reg int i=ID;i;i-=lowbit(i)) res+=unit[i]; return res; } inline void Init(reg int S){ size=S; //memset(unit,0,sizeof(unit)); return; } inline int suf(reg int ID){ return pre(size)-pre(ID-1); } #undef lowbit }; TreeArray Max,fire; inline void output(reg int p,reg int x){ if(!x) pc('P'),pc('e'),pc('a'),pc('c'),pc('e'),pc('\n'); else write(V[p].val),pc(' '),write(x<<1),pc('\n'); return; } int main(void){ reg int Q=read(); reg int cnt=0; for(reg int i=1;i<=Q;++i){ M[i].opt=read(); if(M[i].opt==1) M[i].t=read(),M[i].x=read(),M[i].y=read(),V[++cnt]=Node(M[i].x,i); else M[i].x=read(); } sort(V+1,V+cnt+1); for(reg int i=1,val=1;i<=cnt;++i){ if(V[i].val!=V[i-1].val) val=i; M[V[i].id].x=val; } Max.Init(cnt),fire.Init(cnt); using namespace SegmentTree; Build(1,1,cnt); reg int cnt0=0,cnt1=0; for(reg int i=1;i<=Q;++i){ switch(M[i].opt){ case 1:{ if(M[i].t==0){ ++cnt0; Max.add(M[i].x,M[i].y); UpdateI(1,M[i].x,cnt,-M[i].y); } else{ ++cnt1; fire.add(M[i].x,M[i].y); UpdateI(1,1,M[i].x,M[i].y); UpdateF(1,1,M[i].x,M[i].y); } break; } case 2:{ reg int k=M[i].x; if(M[k].t==0){ --cnt0; Max.add(M[k].x,-M[k].y); UpdateI(1,M[k].x,cnt,M[k].y); } else{ --cnt1; fire.add(M[k].x,-M[k].y); UpdateI(1,1,M[k].x,-M[k].y); UpdateF(1,1,M[k].x,-M[k].y); } break; } } if(!cnt0||!cnt1) pc('P'),pc('e'),pc('a'),pc('c'),pc('e'),pc('\n'); else{ reg int p=findI(1,0); if(p==cnt) output(p,Max.pre(cnt)); else if(p==0) output(findF(1,fire.suf(1)),fire.suf(1)); else{ reg int val=fire.suf(p+1); reg int p2=findF(1,val); reg int ans1=min(Max.pre(p),fire.suf(p)),ans2=min(Max.pre(p2),fire.suf(p2)); if(ans1>ans2) output(p,ans1); else output(p2,ans2); } } } fwrite(wbuf,1,wp,stdout); return 0; }
近期评论