CF453E Little Pony and Lord Tirek

(Updated: )
oi

Description

你有 $n$ 只小马（编号从 $1$ 到 $n$）。每只小马有三种属性。

$s_i$：时间为 $0$ 时这只小马拥有的法力值。

$m_i$：这只小马可以拥有的最大法力值。

$r_i$：这只小马单位时间内回复的法力值。

提雷克会给出 $m$​ 条指令，每一条都可以被描述为 $3$ 个整数：$t_i, l_i, r_i$。表示在时间为 $t_i$ 时，提雷克会从区间 $[l_i,r_i]$ 的小马中吸取魔力，指令保证 $t$ 升序，计算每一条指令之后提雷克可以吸取多少点魔力。

$1\leq n,m\leq 10^5$。

Solution

线段树

打一个标记记录是否拥有初始值、上一次修改的时间。

然后如果拥有初始值，直接暴力修改，因为单点查询之后会被清零，所以这部分是 $\mathcal O(n)$ 的。

如果已经被修改过，没有初始值，直接在线段树上按照时间顺序建个 vector，然后二分一下贡献是 $m_i,t_i\times r_i$。显然如果上次修改的时间较早，则是前一种情况，否则是后一种情况，所以直接二分并分别维护前缀、后缀和即可。

单次区间合并直接双指针扫过去即可，所以总时间复杂度是 $\mathcal O(n\log ^2n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,inf=2e9;
int n,q,tim;
struct Pony{int s,m,r,t;}a[N];
class SegmentTree{
    private:
        struct node{
            vector<int> pre,suf;vector<Pony> f;vector<int> t;
            int tg;
            I void Merge(Cn vector<Pony>& a,Cn vector<Pony>& b){
                f.clear();RI p=0,sa=a.size(),sb=b.size(),i=0,j=0;W(i<sa&&j<sb) a[i].t<b[j].t?f.push_back(a[i++]):f.push_back(b[j++]);
                W(i<sa) f.push_back(a[i++]);W(j<sb) f.push_back(b[j++]);
                p=0,pre.clear();for(auto i:f) p+=i.m,pre.push_back(p),t.push_back(i.t);
                p=0,suf.clear();for(i=f.size()-1;~i;i--) p+=f[i].r,suf.push_back(p);reverse(suf.begin(),suf.end());
            }
            I int G(RI x){
                x-=tg;RI p=lower_bound(t.begin(),t.end(),x)-t.begin();
                RI tmp=0;if(p) tmp+=pre[p-1];if(p!=t.size()) tmp+=suf[p]*x;return tmp;
            }
        }T[N<<2];
        I void PU(CI x){
            if(T[x<<1].tg==-2T[x<<11].tg==-2) return void(T[x].tg=-2);
            if(T[x<<1].tg==T[x<<11].tg&&T[x<<1].tg>=0) return void(T[x].tg=T[x<<1].tg);
            T[x].tg=-1;
        }
        I void PD(CI x){T[x].tg>=0&&(T[x<<1].tg=T[x<<11].tg=T[x].tg);}
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
    public:
        I void B(PT){
            if(T[x].tg=-2,l==r) return T[x].f.push_back(a[l]),T[x].pre.push_back(a[l].m),T[x].t.push_back(a[l].t),T[x].suf.push_back(a[l].r),void();
            B(LT),B(RT),T[x].Merge(T[x<<1].f,T[x<<11].f);
        }
        I int Q(CI L,CI R,PT){
            if(l==r&&T[x].tg==-2) return T[x].tg=tim,min(a[l].s+tim*a[l].r,a[l].m);
            if(L<=l&&r<=R&&T[x].tg>=0){int tmp=T[x].G(tim);T[x].tg=tim;return tmp;}
            int S=0;return PD(x),L<=mid&&(S+=Q(L,R,LT)),R>mid&&(S+=Q(L,R,RT)),PU(x),S;
        }
}T;
signed main(){
    RI i,l,r;for(read(n),i=1;i<=n;i++) read(a[i].s,a[i].m,a[i].r),a[i].t=a[i].r?a[i].m/a[i].r:inf;
    for(T.B(),read(q),i=1;i<=q;i++) read(tim,l,r),writeln(T.Q(l,r));return 0;
}