LibreOJ 2018 「AHOI / HNOI2017」单旋

容易发现 Splay 最小值 / 最大值对树的影响很小且有规律可循。

然后 LCT 模拟即可（雾

亦可离散化权值后用线段树维护深度，另用一个 set 维护前驱后继。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 2e5;
const int M = 2e5;
int n,m,p1,p2;
int st[N + 5],top;
int a[N + 5],left[N + 5],right[N + 5];
vector<int> le[N + 5],ri[N + 5];
struct s_query
{
    int l,r,id;
    inline bool operator<(const s_query &o) const
    {
        return l < o.l;
    }
    inline bool operator>(const s_query &o) const
    {
        return r < o.r;
    }
} qry[M + 5];
long long ans[M + 5];
struct node
{
    long long sum,tag;
    int ls,rs;
} seg[(N << 6) + 10];
int rt[3];
void update(int l,int r,long long k,int &p,int tl,int tr)
{
    if(l > r)
        return ;
    static int tot = 0;
    if(!p)
        p = ++tot;
    seg[p].sum += k * (min(r,tr) - max(l,tl) + 1);
    if(l <= tl && tr <= r)
    {
        seg[p].tag += k;
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
}
long long query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    long long ret = seg[p].tag * (min(r,tr) - max(l,tl) + 1);
    l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
    r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
    return ret;
}
int main()
{
    //freopen("sf.in","r",stdin),freopen("sf.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&p1,&p2);
    a[0] = a[n + 1] = 0x3f3f3f3f,top = 1;
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d",a + i);
        for(;top && a[st[top]] < a[i];--top);
        le[left[i] = st[top]].push_back(i),st[++top] = i;
    }
    st[top = 1] = n + 1;
    for(register int i = n;i;--i)
    {
        for(;top && a[st[top]] < a[i];--top);
        ri[right[i] = st[top]].push_back(i),st[++top] = i;
    }
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
    sort(qry + 1,qry + m + 1,greater<s_query>());
    for(register int i = 1,j = 1;i <= m;++i)
    {
        for(;j <= qry[i].r;++j)
            for(register int k = 0;k < ri[j].size();++k)
                update(left[ri[j][k]],left[ri[j][k]],p1,rt[0],0,n + 1);
        ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[0],0,n + 1) + (long long)(qry[i].r - qry[i].l) * p1;
    }
    sort(qry + 1,qry + m + 1);
    for(register int i = m,j = n;i;--i)
    {
        for(;j >= qry[i].l;--j)
            for(register int k = 0;k < le[j].size();++k)
                update(le[j][k] + 1,right[le[j][k]] - 1,p2,rt[1],0,n + 1);
        ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[1],0,n + 1);
    }
    sort(qry + 1,qry + m + 1,greater<s_query>());
    for(register int i = 1,j = 1;i <= m;++i)
    {
        for(;j >= qry[i].l;--j)
            for(register int k = 0;k < ri[j].size();++k)
                update(left[ri[j][k]] + 1,ri[j][k] - 1,p2,rt[2],0,n + 1);
        ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[2],0,n + 1);
    }
    for(register int i = 1;i <= m;++i)
        printf("%lld\n",ans[i]);
}