[CF 453E] Little Pony and Lord Tirek

作法：

我們先處理每個$s[i]$都是$0$的情形（也就是初始值都是$0$）。考慮用線段樹，把詢問的區間拆成好幾個小區間，分別求出答案再加起來。對於某個線段樹節點代表的區間$[L,R]$而言，我們想要快速求出這個區間中的答案總和。如果這個區間擁有良好的性質：在$t_0$秒的時候這個區間全部都被設成$0$，並且之後不再動到他（因此一開始所有節點都有這個良好性質，並且$t_0$值都是$0$），那麼假設當前詢問時間是$t$秒，就可以把$[L,R]$中的小馬們分成兩類，一類是「經過了$t-t_0$秒沒辦法長到最大值」的，另一類則是長不到的，那麼對於前者，他所貢獻的答案就會是$r[i]\cdot (t-t_0)$，後者貢獻的答案則為$m[i]$。因此我們可以考慮先對每隻馬算出他「要長幾天才會長到最大值」（之後記為$t[i]$），並且在每個線段樹的節點$[L,R]$中，把「這區間中的所有馬按照$t$值排序後的結果」記錄下來，並且算出這些馬的$r$值和$m$值的前綴和陣列，這樣就能快速查詢答案了。但上述算法的前提是這個節點擁有前面所講的好性質（以下簡稱這個節點是好的），如果沒有的話就只好再把詢問區間拆開遞迴下去，直到遇到的節點是好的為止。並且我們也容易維護有哪些是好的：當遇到一個詢問時，如果詢問區間遞迴下去經過的節點被詢問區間完全覆蓋了，那麼在詢問過後他就會變成好的。並且當詢問時如果走到了一個好的節點，但是詢問區間沒有完整覆蓋這個節點的區間的話，就要把這個好的標記往下 push ，並且自己在詢問過後就不再是好節點了。總結以上算法，對於每個節點要記錄的東西有：這個區間中按$t$值排序的馬們，排完序後的馬們的$r$值、$m$值前綴和，還有在詢問時需要維護的$ok$值（代表他是否是好的）和$t_0$值，其中$t_0$代表如果$ok=1$，則$t_0$是最近一次將整個區間設成$0$的時間。以上算法解決了$s[i]$全部都是$0$的情形，但實際上一般情形也可以這樣做，因為這樣一開始時所有區間都是不好的，一次詢問下來會遞迴到底，也就是把詢問區間拆成長度均為$1$的區間暴力處理，顯然長度為$1$可以直接算出答案。不難發現暴力算的次數加起來不會超過$n$次，因此這部份複雜度會是好的。但整個算法我還證不太出他的複雜度是多少，可能是$O(qlog^2n)$之類的......

另外我還有在別人的 comment 中看到另一種作法，詳細見這裡，寫的還蠻清楚的。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 2000000000
using namespace std;
const int maxn=100000+10 ;
 
struct P
{
    int m,ra,t ;
    inline void get(){t=(ra ? (m-1)/ra+1 : INF) ;}
    bool operator < (const P &rhs) const
    {
        return t<rhs.t ;
    }
};
 
struct node
{
    node *l,*r ;
    bool ok ;
    int last,s ;
    vector<int> t ;
    vector<LL> ms,ras ;
    node(int _s=0)
    {
        s=_s ; last=ok=0 ;
        l=r=NULL ;
    }
};
 
void push(node *u)
{
    if(!u->ok) return ;
    u->l->last=u->last , u->l->ok=1 ;
    u->r->last=u->last , u->r->ok=1 ;
    u->ok=0 ;
}
 
int s[maxn],ra[maxn],m[maxn] ;
P p[maxn] ;
node *build(int l,int r)
{
    int sz=r-l+2 ;
    node *u ;
    if(l==r) u=new node(s[l]) ;
    else
    {
        int mid=(l+r)/2 ;
        u=new node() ;
        u->l=build(l,mid) ;
        u->r=build(mid+1,r) ;
        sort(p+l,p+r+1) ;
    }
    u->ms.push_back(0) ;
    u->ras.push_back(0) ;
    for(int i=l;i<=r;i++)
        u->t.push_back(p[i].t) ,
        u->ms.push_back(u->ms.back()+p[i].m) ,
        u->ras.push_back(u->ras.back()+p[i].ra) ;
    return u ;
}
 
LL query(int l,int r,int L,int R,node *u,int t)
{
    if(L==R)
    {
        LL ret=min((LL)m[L],s[L]+(LL)(t-u->last)*ra[L]) ;
        u->ok=1 ; u->last=t ; s[L]=0 ;
        return ret ;
    }
    if(l==L && r==R && u->ok)
    {
        const vector<int> &v=u->t ;
        int id=upper_bound(v.begin(),v.end(),t-u->last)-v.begin()-1 ;
        LL ret=u->ms[id+1]+(u->ras.back()-u->ras[id+1])*(t-u->last) ;
        u->last=t ;
        return ret ;
    }
    push(u) ;
    int mid=(L+R)/2 ; LL ret ;
    if(r<=mid) ret=query(l,r,L,mid,u->l,t) ;
    else if(l>mid) ret=query(l,r,mid+1,R,u->r,t) ;
    else ret=query(l,mid,L,mid,u->l,t)+query(mid+1,r,mid+1,R,u->r,t) ;
    if(l==L && r==R) u->ok=1 , u->last=t ;
    return ret ;
}
 
main()
{
    srand(time(NULL)) ;
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&s[i],&m[i],&ra[i]) ,
        p[i].m=m[i] , p[i].ra=ra[i] , p[i].get() ;
    node *root=build(1,n) ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int t,l,r ; scanf("%d%d%d",&t,&l,&r) ;
        printf("%lld\n",query(l,r,1,n,root,t)) ;
    }
}