[BZOJ5254] [Fjwc2018]红绿灯

题目简明易懂此处就不在赘述了 需要注意的是题目中需要输出的答案是到达学校的最小时刻而不是最短耗时，也就是说出发时间是$t$，耗时是$P$的时候你应该输出$t+P$ 先做一步转化，就是中间的$\sum d_{i}$的时间是必须消耗的，所以我们考虑计算每一个询问等红灯的时间 那么我们会发现两个比较有趣的性质 第一个性质是对于出发时间$t1,t2$如果$t1 \equiv t2 \mod (g+r)$的话,这两个询问的耗时是相等的证明,应该十分显然，根据这个性质我们可以把询问的时间控制在$g+r$这个值域范围内 而另一个性质就是，如果在不同时间出发的两个人等了同一个红灯，那么在这个红灯之后两个人的行为将会变的** 完 全 一 致** 那么第二个性质有什么用呢？ 我们可以推出这样一个性质:所有人的行动路线构成一张类似于森林一样的东西 这个“森林”具体指什么呢？ 如果一堆人等了同一个红灯，那么我们知道他们的行动将会在这个红灯之后等价于一个红灯恰好熄灭时通过路口的人 那么我们就可以新建一个虚拟的人，这个人的出发时间经过了恰当的调整使得这个人恰好在这个红灯熄灭之后通过路口，然后将等这个红灯的所有人都作为这个人的儿子 如此这般操作我们就可以建出一张森林来，容易看出一个人只要等了一次红灯他就会被挂在另一个节点下面作为儿子，如果我们把每个点的点权记为这个人等红灯的时间，那么每一个询问的答案就等于这个询问一开始的点到根路径的点权之和(因为从这个点不断向根上跳的过程相当于不断等红灯的过程) 那么问题来了我们怎么建出这个树来呢？ 首先我们需要注意的是，只要两个人出发的时间膜$g+r$同余那么这两个人等红灯的时间就没有任何差别 那么根据这个条件,所有人的出发时间全部在\[0,g+r)时间范围内 因此我们采取增量法来构造这个树，假设我们有了第i个路口之后的森林，希望构造出第i+1个时刻的森林来，此时不妨设 $\sum_{j=1}^{i+1}d_{j} \equiv T \mod (g+r)$ 那么我们会发现此时所有人可以分为三类，第一种是到达这个路口的时候这个路口是绿灯的人，第二种是出发时间在\[r-T,g+r-T)的人，这种人会一起等同一个红灯，另一个种人是出发时间在\[2g+r-T,2g+2r-T)的人，这种人一起等另外一个红灯 没法理解上面的式子的话自己画个图就明白了 那么我们发现这些人最多等两个不同的红灯，那么我们可以用一个set来维护所有的人，每次暴力的删掉区间中所有的人，然后插入两个虚拟的人(插入的时候时间记得膜g+r)同时给森林进行加边，当我们处理完最后的路口之后对着set中还存在的点每个点dfs一遍就行了 一个小trick是一开始把每个人膜$g+r$之后插入set的时候可以将这个人对应的点的点权设为$\sum_{i}d_{i}+time$这样到最后我们dfs出来的数字就是答案了 上代码~ ```C /************************************************************** Problem: 5254 User: shadowice1984 Language: C++ Result: Accepted Time:712 ms Memory:10000 kb ****************************************************************/ #include<cstdio> #include<algorithm> #include<set> using namespace std;const int N=1e5+10;typedef long long ll; ll dis[3*N];int v[3*N];int x[3*N];int al[3*N];int ct;int n;int m; ll G;ll R;int tot;int d[N];int tim;ll ans; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} struct data { int u;ll tim; friend bool operator <(data a,data b){return (a.tim==b.tim)?a.u<b.u:a.tim<b.tim;} };set <data> s;data q[N];int hd; inline void mg(ll l,ll r) { set <data> :: iterator it=s.lower_bound((data){-0x3f3f3f3f,l}); if(it==s.end()||it->tim>=r)return;++tot;hd=0; for(;it!=s.end()&&it->tim<r;++it) dis[it->u]+=r-it->tim,add(tot,it->u),q[++hd]=*it; for(int i=1;i<=hd;i++)s.erase(q[i]);s.insert((data){tot,r%(G+R)}); } inline void dfs(int u){for(int i=al[u];i;i=x[i])dis[v[i]]+=dis[u],dfs(v[i]);} int main() { //freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout); scanf("%d%lld%lld",&n,&G,&R); for(int i=1;i<=n+1;i++)scanf("%d",&d[i]),ans+=d[i];scanf("%d",&m);tot=m; for(int i=1,t;i<=m;i++) scanf("%d",&t),dis[i]=t+ans,s.insert((data){i,t%(G+R)}); for(int i=1,tim=d[1]%(G+R);i<=n;i++,(tim+=d[i])%=(G+R)) mg(G-tim,G+R-tim),mg((G<<1)+R-tim,(G+R)*2-tim); set <data> :: iterator it; for(it=s.begin();it!=s.end();++it)dfs(it->u); for(int i=1;i<=m;i++)printf("%lld\n",dis[i]);return 0; } ```