Problem

https://www.luogu.org/problemnew/show/P3246

Solution

用笛卡尔树水了 40 分...

正解是莫队 +dp 啥的...

Code 40pts

// Code by ajcxsu
// Problem: seg

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

const int N=1e5+10;
int arr[N];
struct Node *nil;
struct Node {
    Node *ch[2];
    int id, val, l, r;
    Node(int id=0, int val=0):id(id), val(val) { ch[0]=ch[1]=nil; }
} *rt, po[N];
void ini() { nil=po, nil->ch[0]=nil->ch[1]=nil, nil->l=0x3f3f3f3f, nil->r=-0x3f3f3f3f; }

Node *stk[N];
int t;
int n, q;
void build() {
    for(int i=1;i<=n;i++) {
        while(t && stk[t]->val>=po[i].val) po[i].ch[0]=stk[t], t--;
        stk[++t]=po+i;
        if(t==1) rt=stk[t];
        else stk[t-1]->ch[1]=stk[t];
    }
}

void dfs(Node *x) {
    if(x==nil) return;
    if(x->ch[0]==nil && x->ch[1]==nil) x->l=x->r=x->id;
    else dfs(x->ch[0]), dfs(x->ch[1]), x->l=min(x->ch[0]->l, x->id), x->r=max(x->id, x->ch[1]->r);
}

typedef long long ll;
ll ans=0;
int query(Node *x, int xl, int xr) {
    int sl=1, sr=1;
    if(xl<=x->ch[0]->r) sl+=query(x->ch[0], xl, xr);
    if(xr>=x->ch[1]->l) sr+=query(x->ch[1], xl, xr);
    if(x->id>=xl && x->id<=xr) ans+=1ll*x->val*sl*sr, sr++;
    return sl+sr-2;
}

void check(Node *x) {
    if(x==nil) return;
    check(x->ch[0]), cout<<x->id<<' '<<x->l<<' '<<x->r<<endl, check(x->ch[1]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), ini();
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i], po[i]=Node(i, arr[i]);
    build();
    dfs(rt);
    int l, r;
    while(q--) {
        cin>>l>>r, ans=0;
        query(rt, l, r), cout<<ans<<endl;
    }
    return 0;
}

Code

// Code by ajcxsu
// Problem: seg_true

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

typedef long long ll;
const int N=1e5+10;
int arr[N], pre[N], pos[N];
ll f[N], f2[N];
struct Query { int l, r, id; } qu[N];
bool cmp(const Query &a, const Query &b) { return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l; }

const int OP=20;
int mi[N][OP], pi[N][OP];
int n, q, na;
void build() {
    for(int i=1;i<=n;i++) mi[i][0]=arr[i], pi[i][0]=i;
    for(int j=1;j<OP;j++)
        for(int i=1;i+(1<<j)-1<=n;i++) {
            if(mi[i][j-1]<mi[i+(1<<j-1)][j-1]) mi[i][j]=mi[i][j-1], pi[i][j]=pi[i][j-1];
            else mi[i][j]=mi[i+(1<<j-1)][j-1], pi[i][j]=pi[i+(1<<j-1)][j-1];
        }
}
int lo[N];
int query(int l, int r) {
    int len=lo[r-l+1];
    // assert(lo[r-l+1]==(int)log2(r-l+1));
    // cout<<l<<' '<<r<<' '<<(mi[l][len]<mi[r-(1<<len)+1][len]?pi[l][len]:pi[r-(1<<len)+1][len])<<endl;
    return mi[l][len]<mi[r-(1<<len)+1][len]?pi[l][len]:pi[r-(1<<len)+1][len];
}

ll ans, tot[N];
int l, r;
void revisel(int x, int d) {
    int p=query(x, r);
    ans+=1ll*d*(1ll*arr[p]*(r-p+1)+f2[x]-f2[p]);
}
void reviser(int x, int d) {
    int p=query(l, x);
    ans+=1ll*d*(1ll*arr[p]*(p-l+1)+f[x]-f[p]);
}

int main() {
    for(int i=2;i<N;i<<=1) lo[i]++;
    for(int i=2;i<N;i++) lo[i]+=lo[i-1];
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++) {
        na=i-1;
        while(na && arr[na]>=arr[i]) na=pre[na];
        pre[i]=na;
    }
    for(int i=1;i<=n;i++) f[i]=f[pre[i]]+1ll*arr[i]*(i-pre[i]);
    reverse(arr+1, arr+1+n);
    for(int i=1;i<=n;i++) {
        na=i-1;
        while(na && arr[na]>=arr[i]) na=pre[na];
        pre[i]=na;
    }
    for(int i=1;i<=n;i++) f2[i]=f2[pre[i]]+1ll*arr[i]*(i-pre[i]);
    reverse(arr+1, arr+1+n), reverse(f2+1, f2+1+n), build();
    int unit=sqrt(n);
    for(int i=1;i<=n;i++) pos[i]=i/unit;
    for(int i=1;i<=q;i++) cin>>qu[i].l>>qu[i].r, qu[i].id=i;
    sort(qu+1, qu+1+q, cmp);
    l=1, r=1, ans=arr[1];
    for(int i=1;i<=q;i++) {
        while(r<qu[i].r) reviser(r+1, 1), r++;
        while(r>qu[i].r) reviser(r, -1), r--;
        while(l<qu[i].l) revisel(l, -1), l++;
        while(l>qu[i].l) revisel(l-1, 1), l--;
        tot[qu[i].id]=ans;
    }
    for(int i=1;i<=q;i++) cout<<tot[i]<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3246.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆