牛客Energy stones

この問題はあまりよく考えられないが、主な難点は私たちの普段の習慣が時間の前後順に答えを統計することであり、この問題は各点を列挙することによって統計を行い、差分方法+setを通じてすべての時間帯の状態を維持することである.

#include 
using namespace std;
typedef long long lint;
const int maxn = 100005;
const int maxm = 100005;
int E[maxn],L[maxn],C[maxn],d[maxn],mx;
vector st[maxn],en[maxn];
set se;
void init( int n ){
    se.clear();
    for( int i = 0; i<= n;i++ ) st[i].clear(),en[i].clear();
}
struct fanwick{
    lint limit,b[200005];
    void init( int mx ){
        limit = mx+1;
        for( int i = 0;i <= limit;i++ ) b[i] = 0;
    }
    int lowbit(int x){
        return x&-x;
    }
    void add( int x,lint v ){
        while(x<=limit){
            b[x] += v;
            x += lowbit(x);
        }
    }
    lint ask( lint x ){
        lint res = 0;
        if( x > limit ) x = limit;
        while(x){
            res += b[x];
            x -= lowbit(x);
        }
        return res;
    }
    lint query( int l,int r ){
        if( l > r ) return 0;
        return ask(r)-ask(l-1);
    }
}g1,g2;
lint ans = 0;
void solve( int x ){
    if( se.size() ){
        auto p = se.begin();
        if( L[x] && *p >= (C[x]-E[x]+L[x]-1)/L[x]  ) ans += C[x];
        else ans += E[x] + L[x]* *p;

        ans += g2.ask( d[x]-1 ) * L[x];
        ans += g1.query( d[x],g1.limit ) * C[x] ;
    }
}
int main(){
    int n,T,l,r;
    scanf("%d",&T);
    for( int tt = 1;tt <= T;tt++ ){
        printf("Case #%d: ",tt);
        ans = mx = 0;
        scanf("%d",&n);init(n);
        for( int i = 1;i <= n;i++ ) {scanf("%d%d%d",&E[i],&L[i],&C[i]);d[i] =  L[i] ?(C[i] + L[i]-1)/L[i] : 1e6+1 ;}
        int m,t;scanf("%d",&m);for(int i = 1;i <= m;i++ ) {scanf("%d%d%d",&t,&l,&r);st[l].push_back( t );en[r+1].push_back(t);mx = max( mx,t );}
        g1.init(mx);g2.init(mx);
        for( int i = 1;i <= n;i++ ){
            for( auto x : st[i] ){
                se.insert(x);
                auto p = se.find(x);
                auto pre = p,suf = p;
                if( p != se.begin() ) --pre;
                if( p != se.end() ) ++suf;
                    if( p != se.begin() ){
                        int dt = *p-*pre;
                        g1.add( dt,1 );g2.add( dt,dt );
                    }
                    if( suf != se.end() ){
                        int dt = *suf-*p;
                        g1.add( dt,1 );g2.add( dt,dt );
                        if(p!=se.begin()){
                            int dt = *suf-*pre;
                            g1.add( dt,-1 );g2.add( dt,-dt );
                        }
                    }
            }
            for( auto x : en[i] ){
                auto p = se.find( x );
                auto suf = p,pre = p;
                if( p != se.begin() )--pre;
                if( p != se.end() ) ++suf;
                if( p != se.begin() ){
                    int dt = *p - *pre;
                    g1.add( dt,-1 );g2.add( dt,-dt );
                }
                if( suf != se.end() ){
                    int dt  = *suf - *p;
                    g1.add( dt,-1 );g2.add( dt,-dt );
                    if( p != se.begin() ){
                        dt = *suf - *pre;
                        g1.add( dt,1 );g2.add( dt,dt );
                    }
                }
                se.erase(p);
            }
            solve(i);
        }
        printf("%lld
",ans);
    }
    return 0;
}