【贪心】【线段树】【数据结构】AGC011 Train Service Planning

分析：

题意理解起来就很恶心的一道题。。。

设A火车在每个站台等的时间为$P_i$
B火车在每个站台等的时间为$Q_i$
那么，如果两个火车在第x个轨道上不相交，那么就只需要满足：
$({\sum }_{i=0}^{i\le x}{P}_i+{\sum }_{i=0}^{i\le x?1}{A}_i,{\sum }_{i=0}^{i\le x}{P}_i+{\sum }_{i=0}^{i\le x}{A}_i)$与区间
$({\sum }_{i=n}^{i\ge x+1}{Q}_i+{\sum }_{i=n}^{i\ge x}{A}_i,{\sum }_{i=n}^{i\ge x+1}{P}_i+{\sum }_{i=n}^{i\ge x?1}{A}_i)$无交点。

可以把第二个反过来表示，变为
$(F?{\sum }_{i=0}^{i\le x}{Q}_i?{\sum }_{i=0}^{i\le x}{A}_i,F?{\sum }_{i=0}^{i\le x}{Q}_i?{\sum }_{i=0}^{i\le x?1}{A}_i)$这里由于反过来后左侧更大，所以翻转了一下。

然后用初中数学知识（不等式），发现只需要${\sum }_{i=0}^{i\le x}(Q_i+P_i)$不在区间$(?2?{\sum }_{i=0}^{i\le x}{A}_i,?2?{\sum }_{i=0}^{i\le x?1})$中。

所以可以想办法表示$P_i+Q_i$的前缀和，然后在一个数轴上走，在某些时间不能处在某个区间中。这样可以用线段树维护枚举的每个开始时间。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define SF scanf
#define PF printf
#define MAXN 200010
#define INF 10000000000000000ll
using namespace std;
int n,k;
typedef long long ll;
ll tree[MAXN*4],f[MAXN],sum;
int a[MAXN],b[MAXN],l[MAXN],r[MAXN];
vector<int> val;
ll min1(ll x,ll y){
    if(x==0)return y;if(y==0)return x;return min(x,y);	
}
ll que(int l,int r,int id,int pos){
    if(l==r)return tree[id];int mid=(l+r)>>1;if(pos<=mid)return min1(tree[id],que(l,mid,id*2,pos));elsereturn min1(tree[id],que(mid+1,r,id*2+1,pos));
}
void change(int l,int r,int id,int pl,int pr,int v){
    if(pl>pr)return ;if(l>=pl&&r<=pr){
    tree[id]=min1(tree[id],v);	return ;}int mid=(l+r)>>1;if(pl<=mid)change(l,mid,id*2,pl,pr,v);if(pr>mid)change(mid+1,r,id*2+1,pl,pr,v);
}
int main(){
    SF("%d%d",&n,&k);for(int i=1;i<=n;i++){
    SF("%d",&a[i]);SF("%d",&b[i]);if(b[i]==1&&2*a[i]>k){
    PF("-1");return 0;}sum+=a[i];a[i]=(a[i]+a[i-1])%k;}for(int i=1;i<=n;i++){
    if(b[i]==1){
    l[i]=2*(k-a[i-1])%k;r[i]=2*(k-a[i])%k;}else{
    l[i]=0;r[i]=k-1;	}val.push_back(l[i]);val.push_back(r[i]);}sort(val.begin(),val.end());int len=unique(val.begin(),val.end())-val.begin()-1;for(int i=1;i<=n;i++){
    //PF("{%d %d}\n",l[i],r[i]);r[i]=lower_bound(val.begin(),val.begin()+len,r[i])-val.begin();l[i]=lower_bound(val.begin(),val.begin()+len,l[i])-val.begin();	//PF("<%d %d>\n",l[i],r[i]);}for(int i=n;i>=1;i--){
    int res=que(0,len,1,l[i]);if(res==0)f[i]=0;	elsef[i]=f[res]+(val[l[res]]-val[l[i]]+k)%k;if(l[i]<=r[i]){
    change(0,len,1,0,l[i]-1,i);change(0,len,1,r[i]+1,len,i);}elsechange(0,len,1,r[i]+1,l[i]-1,i);}ll ans=INF;for(int i=0;i<=len;i++){
    ll res=que(0,len,1,i);if(res)res=f[res]+(val[l[res]]-val[i]+k)%k;ans=min(ans,res);}PF("%lld",ans+2ll*sum);
}