原题链接

题解

注意数据范围

1.我们不知道要在哪些地方建站，所以考虑都遍历一遍
2.如果一个地方 \(i\) 要建站，那么在它前面且离它最近的一个站，一定建在所有右端点大于 \(i\) 的区间中，左端点最大区间里
所以我们令 \(dp[i]\) 表示为在 \(i\) 建立一个站，且和 \([1,i]\) 有交集的区间都覆盖的最小成本

code

#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll a[500005];
ll dp[500005];
struct node
{
    ll l,r;
}qj[500005];

bool cmp(node b,node c)
{
    return b.r<c.r;
}

struct range
{
    ll l,r;
    bool operator<(const range &b) const{return b.l>l;}
};

ll st[500005][25];

inline void read(ll &x) {
	x = 0;
	ll flag = 1;
	char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
	while(c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
    	putchar('-');
		x = -x;
	}
    if(x > 9)
		write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    ll t;
    read(t);
    while(t--)
    {
        ll n;
        read(n);
        for(ll i=1;i<=n;i++) read(a[i]);

        ll m;
        read(m);
        for(ll i=1;i<=m;i++)
        {
            read(qj[i].l);
            read(qj[i].r);
        }

        sort(qj+1,qj+1+m,cmp);

        ll it=1;
        priority_queue<range> Q1;
        for(ll i=1;i<=n;i++)
        {
            while(it<=m&&qj[it].r<i)
            {
                Q1.push({qj[it].l,qj[it].r});
                it++;
            }

            if(!Q1.size())
            {
                dp[i]=a[i];
                st[i][0]=dp[i];
                for(ll k=1;k<=log2(i);k++)
                {
                    st[i][k]=min(st[i][k-1],st[i-(1<<(k-1))][k-1]);
                }
                continue;
            }
            ll l=Q1.top().l,r=Q1.top().r;

            ll add=2e18;
            while(l<=r)
            {
                ll len=log2(r-l+1LL);
                add=min(add,st[r][len]);
                r-=(1<<len);
            }
            dp[i]=add+a[i];

            st[i][0]=dp[i];
            for(ll k=1;k<=log2(i);k++)
            {
                st[i][k]=min(st[i][k-1],st[i-(1<<(k-1))][k-1]);
            }
        }
        while(it<=m&&qj[it].r<=n)
        {
            Q1.push({qj[it].l,qj[it].r});
            it++;
        }
        ll ans=2e18;
        for(ll i=Q1.top().l;i<=Q1.top().r;i++) ans=min(ans,dp[i]);
        write(ans);
        putchar('\n');
    }
    return 0;
}