【BZOJ 4826】[HNOI2017] 影魔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html

解题报告

这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$

至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
   
const int N = 200009;
const int NN = N << 1;
const int M = 18;
   
int n,m,p1,p2,val[N];
LL ans[N];
vector<int> q1[N];
vector<pair<int,int> > q2[N],q3[N];
struct Query{int l,r,id;}q[N];
   
inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;}
inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;}
   
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
   
class Sparse_Table{
    int mx[M][N],pos[M][N],lg[N];
    public:
        inline void init(int *arr) {
            for (int i=1;i<=n;i++) {
                mx[0][i] = arr[i];
                pos[0][i] = i;
            }
            for (int l=1,j=1;l*2<=n;j++,l<<=1) {
                for (int i=1;i<=n-l;i++) {
                    if (mx[j-1][i] >= mx[j-1][i+l]) {
                        pos[j][i] = pos[j-1][i];
                        mx[j][i] = mx[j-1][i];
                    } else {
                        pos[j][i] = pos[j-1][i+l];
                        mx[j][i] = mx[j-1][i+l];
                    }
                }
            }
            for (int i=2;i<=n;i++) {
                lg[i] = lg[i>>1] + 1;
            }
        }
        inline int query(int l, int r) {
            int t = lg[r-l+1], j = 1 << t;
            if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l];
            else return pos[t][r-j+1]; 
        }
}ST;
   
void solve(int l, int r) {
    if (l == r - 1) {
        return;
    } else {
        int pos = ST.query(l+1, r-1);
        if (l) q1[pos].push_back(l);
        if (r <= n) q1[r].push_back(pos);
           
        if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1));
        if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1));
           
        solve(l, pos);
        solve(pos, r);
    }
}
   
class Segment_Tree{
    int cnt; LL AnsTmp;
    struct Node{
        Node *ch[2];
        int len;
        LL sum,tag;
    }p[NN],*root; 
    public:
        inline void init() {
            cnt = 0;
            build(root, 1, n);
        }
        inline void modify(int pos, int delta) {
            Node *w = root;
            int  l = 1, r = n, mid;
            while (l <= r) {
                w->sum += delta;
                if (l == r) break;
                mid = l + r + 1 >> 1;
                if (pos < mid) w = w->ch[0], r = mid - 1;
                else w = w->ch[1], l = mid;
            }
        }
        inline void modify(int l, int r, int delta) {
            modify(root, 1, n, l, r, delta);
        }
        inline LL query(int l, int r) {
            AnsTmp = 0;
            query(root, 1, n, l, r);
            return AnsTmp;
        }
    private:
        inline void pushdown(Node *w) {
            w->ch[0]->sum += w->ch[0]->len * w->tag;
            w->ch[1]->sum += w->ch[1]->len * w->tag;
            w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag;
            w->tag = 0;
        }
        void query(Node *w, int l, int r, int L, int R) {
            if (L <= l && r <= R) {
                AnsTmp += w->sum;
            } else {
                if (w->tag) pushdown(w);
                int mid = l + r + 1 >> 1;
                if (L < mid) query(w->ch[0], l, mid-1, L, R);
                if (mid <= R) query(w->ch[1], mid, r, L, R);
            }
        }
        void modify(Node *w, int l, int r, int L, int R, int delta) {
            if (L <= l && r <= R) {
                w->sum += (LL)delta * w->len;
                w->tag += delta;
            } else {
                if (w->tag) pushdown(w);
                int mid = r + l + 1 >> 1;
                if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta);
                if (mid <= R) modify(w->ch[1], mid, r, L, R, delta);
                w->sum = w->ch[0]->sum + w->ch[1]->sum;
            }
        }
        void build(Node *&w, int l, int r) {
            w = &p[++cnt];
            w->len = r - l + 1;
            w->sum = w->tag = 0; 
            w->ch[0] = w->ch[1] = 0;
            if (l < r) {
                int mid = l + r + 1 >> 1;
                build(w->ch[0], l, mid-1);
                build(w->ch[1], mid, r);
            }
        }
}SEG;
   
int main() {
    n = read(); m = read();
    p1 = read(); p2 = read();
    for (int i=1;i<=n;i++) {
        val[i] = read();
    }
    ST.init(val); 
    solve(0, n+1); 
    for (int i=1;i<=m;i++) {
        q[i].l = read(); 
        q[i].r = read();
        q[i].id = i;
    }
    sort(q+1, q+1+m, cmp1);
    SEG.init();
    for (int i=1,pos=0;i<=m;i++) {
        while (pos < q[i].r) {
            pos++;
            for (int j=0;j<q1[pos].size();j++) {
                SEG.modify(q1[pos][j], p1);
            }
            for (int j=0;j<q2[pos].size();j++) {
                SEG.modify(q2[pos][j].first, q2[pos][j].second, p2);
            }
        }
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    sort(q+1, q+1+m, cmp2);
    SEG.init(); 
    for (int i=1,pos=n+1;i<=m;i++) {
        while (pos > q[i].l) {
            pos--;
            for (int j=0;j<q3[pos].size();j++) {
                SEG.modify(q3[pos][j].first, q3[pos][j].second, p2);
            }
        } 
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    for (int i=1;i<=m;i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}