题目描述
Aqours铁路公司旗下有N个站，编号1,2,..,N。
有各停（各站停车）电车特急电车两种。特急车会在，一共M个车站停车。
相邻的两站(即编号为i的车站和编号为的车站，而不是特急电车停车的相邻的两站)之间，各停电车要运行A分钟，特急需要B分钟。我们认为列车一直匀速运行，不考虑停车和加减速。
现在要加一种快速电车，要求其停站覆盖所有的特急电车的停站，而相邻的两站要运行C分钟。为了要快，决定刚好停K个站（，包括特急的所有车站）。如果一个站可以停多种电车，那么旅客可以在这一站换乘。不过只能向前坐车，不能往回坐。
你需要设计一种快速列车的设站方案，要求旅客在T分钟乘车时间（等车和换乘时间不计）内，可以从1号站到尽可能多数量的站。你只需要告知能有几站可以达到。
输入输出格式
输入格式： 第一行3个整数，N，M，K，其意义已经在描述中给出。
第二行3个整数，A，B，C，其意义也已经在描述中给出。
第三行1个整数T，表示乘车时间。
接下来M行，每行一个整数。其中第i个整数为
输出格式： 一个整数，表示限定时间内能够达到的最多站的数量。
输入输出样例
输入样例#1： 10 3 5 10 3 5 30 1 6 10 输出样例#1： 8 说明
【样例解释】
可以设快速列车站为1/5/6/8/10。
2,3,4可以直接乘坐各停慢车，5可以乘坐快速列车，6,10可以乘坐特急列车，7可以到6转慢车，8可以到6传快速列车。9没办法在30分钟的乘车时间内到达
【数据范围】
对于20%的数据，
对于50%的数据，
对于100%的数据，
题解 M,K只有3000，从这找突破口，根据特急列车停靠点，把站分为M个块，计算每个块内增加一个快速列车站能增加的到达个数，放入堆中，每次取出堆顶并维护，取K-M个就可以了。详见代码。
代码
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #define ll long long struct seg{ll st,ed,m,t;}tr[100005]; ll n,m,k,a,b,c,T,len; ll s[3005]; using namespace std; inline ll read() { ll x=0LL;char ch=getchar(); while (ch<'0'||ch>'9'){ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll query_s(ll t,ll l,ll r) { if (l>r) return l; if ((ll)t+(ll)(r-l)*a<=T) return r+1; else return (T-t)/a+l+1; } ll query_m(ll t,ll l,ll r) { if (l>r) return 0; if (t>T) return 0; if ((ll)t+(ll)(r-l)*a<=T) return r-l+1; else return (T-t)/a+(t<=T); } void shift_up(ll st,ll ed,ll t,ll m) { len++; int p=len; tr[p].t=t; tr[p].m=m; tr[p].st=st; tr[p].ed=ed; while (p/2>0) { if (tr[p].m<=tr[p/2].m) break; swap(tr[p],tr[p/2]); p=p/2; } } void shift_down() { tr[1]=tr[len]; len--; int p=1; while (p*2<=len) { if (p*2+1>len||tr[p*2].m>tr[p*2+1].m) p=p*2;else p=p*2+1; if (tr[p].m<=tr[p/2].m) break; swap(tr[p],tr[p/2]); } } int main()//错了一万遍。。 { n=read();m=read();k=read(); a=read();b=read();c=read(); T=read(); for (int i=1;i<=m;i++) { s[i]=read(); } ll ans=(ll)((ll)s[m]*b-b<=T); for (int i=1;i<=m-1;i++) { ll tim=(ll)s[i]*b-b; ans+=query_m(tim,s[i],s[i+1]-1); ll p=query_s(tim,s[i],s[i+1]-1); tim+=(ll)(p-s[i])*c; ll num=query_m(tim,p,s[i+1]-1); if (p<=s[i+1]-1&&tim<=T) shift_up(p,s[i+1]-1,tim,num); } k-=m; while (k--&&len) { ans+=tr[1].m; ll tim=(ll)tr[1].t; ll s=query_s(tim,tr[1].st,tr[1].ed); tim+=(ll)(s-tr[1].st)*c; ll num=query_m(tim,s,tr[1].ed); ll e=tr[1].ed; shift_down(); if (s<=e&&tim<=T) shift_up(s,e,tim,num); } printf("%lld",ans-1); return 0; }