【xsy2155】music

题目 分析 线段树

题意

分析

  可能的 $T$ 只有 $n$ 个，因为只有 $n$ 个变化点 $t_i-t_{i-1}$ ， $变化点-1$ 的值就是 $n$ 个可能的值。
  我们将变化点从大到小排序，枚举变化点，单调地删除被忽略的点，并尝试求答案。

  由于我们知道 $V_2$ 的值，终点的信息比较多，所以我们考虑倒推。
  求出第一次碰到 $0$ 的位置 $tMin$ ，和碰到 $Mx$ 的位置 $tMax$ 。

  当 $tMin<tMax$ 时，我们可以画出这样一幅图。

  若没有经过小于0的部分，则这段有解。
  且所有线下的路径都合法，所以一定有解，此时答案取 $Max$ 。
  若 $tMax=n+1$ ，那么合法区间为 $[0,操作之和]$ ，我们取操作之和。

  同理当 $tMax<tMin$ 时，我们可以画出这样一幅图。

  若没有经过大于 $Mx$ 的部分，则这段有解。
  且所有线上的路径都合法，所以一定有解，此时答案取 $Max$ 。若 $tMax=n+1$ ，则合法区间为 $[操作之和,Max]$ ，所以我们取 $Max$ 。

实现

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (register int i=(a);i<=(b);i++)
#define D(i,a,b) for (register int i=(a);i>=(b);i--)
#define ls (x<<1)
#define rs (x<<1|1)
int n,Max,V2;
int but[100005];
struct OP { int t,id; friend inline int operator < (OP a,OP b) { return a.t>b.t; } }op[100005];
struct Info {
    int sum,mn,mx;
    inline Info(int _sum=0,int _mn=(int)1e9,int _mx=(int)-1e9):sum(_sum),mn(_mn),mx(_mx){}
    friend inline Info operator + (Info a,Info b) {
        Info c; c.sum=a.sum+b.sum;
        c.mn=min(a.mn,a.sum+b.mn);
        c.mx=max(a.mx,a.sum+b.mx);
        return c;
    }
};
struct Seg {
    int l,r; Info val;
}tr[300000];
namespace input {
    const int S=2000000; char s[S]; char *h=s+S; char *t=h;
    inline char getchr(void) { if (h==t) { fread(s,1,S,stdin); h=s; } return *h++; }
    inline int rd(void) {
        int x=0,f=1; char c=getchr();
        for (;!isdigit(c);c=getchr()) if (c=='-') f=-1;
        for (;isdigit(c);c=getchr()) x=x*10+c-'0';
        return x*f;
    }
    inline int rdc(void) { char c=getchr(); while (c!='+'&&c!='-') c=getchr(); return c=='+'?-1:1; }
}
using input::rd;
using input::rdc;
void Build(int x,int l,int r) {
    tr[x].l=l,tr[x].r=r;
    if (l==r) tr[x].val=Info(but[l],but[l],but[l]);
    else {
        int mid=(l+r)>>1;
        Build(ls,l,mid);
        Build(rs,mid+1,r);
        tr[x].val=tr[ls].val+tr[rs].val;
    }
}
void Modify(int x,int loc,int w) {
    if (tr[x].l==tr[x].r) { tr[x].val=Info(w,w,w); return; }
    int mid=(tr[x].l+tr[x].r)>>1;
    loc<=mid?Modify(ls,loc,w):Modify(rs,loc,w);
    tr[x].val=tr[ls].val+tr[rs].val;
}
Info Prefix(int x,int loc) {
    if (tr[x].r<=loc) return tr[x].val;
    int mid=(tr[x].l+tr[x].r)>>1;
    if (loc<=mid) return Prefix(ls,loc);
    else return tr[ls].val+Prefix(rs,loc);
}
int FMin(int x,int sum) {
    if (tr[x].l==tr[x].r) return (tr[x].l-1)+(sum+tr[x].val.sum>0);
    int mid=(tr[x].l+tr[x].r)>>1;
    if (sum+tr[ls].val.mn<=0) return FMin(ls,sum);
    else return FMin(rs,sum+tr[ls].val.sum);
}
int FMax(int x,int sum) {
    if (tr[x].l==tr[x].r) return (tr[x].l-1)+(sum+tr[x].val.sum<Max);
    int mid=(tr[x].l+tr[x].r)>>1;
    if (sum+tr[ls].val.mx>=Max) return FMax(ls,sum);
    else return FMax(rs,sum+tr[ls].val.sum);
}
inline int Sum(int x) { return tr[x].val.sum; }
void Init(void) {
    n=rd(),Max=rd(),V2=rd();
    but[0]=V2;
    D(i,n,1) {
        but[i]=rdc();
        op[i].t=rd(),op[i].id=i;
    }
    Build(1,0,n);
}
int calc(void) {
    int tMin=FMin(1,0)+1;
    int tMax=FMax(1,0)+1;
    if (tMin==n+1&&tMax==n+1) return Sum(1);
    else if (tMin<tMax) {
        Info data=Prefix(1,tMax);
        if (data.mn<0) return -1;
        if (tMax==n+1) return Sum(1);
        return Max;
    }
    else if (tMin>tMax) {
        Info data=Prefix(1,tMin);
        if (data.mx>Max) return -1;
        return Max;
    }
}
void Solve(void) {
    if (calc()!=-1) { printf("infinity\n"); return; }
    F(i,1,n) op[i].t-=op[i+1].t;
    sort(op+1,op+n+1);
    for (int l=1,r=1;l<=n;l=r+1,r=l) {
        while (r+1<=n&&op[l].t==op[r+1].t) r++;
        F(i,l,r) {
            but[op[i].id]=0;
            Modify(1,op[i].id,0);
        }
        int ans=calc(); if (ans!=-1) { printf("%d %d\n",op[l].t-1,ans); return; }
    }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        // freopen("sdchr.out","w",stdout);
    #endif
    Init();
    Solve();
    return 0;
}