【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;
}

45 thoughts to “【BZOJ 4826】[HNOI2017] 影魔”

  1. This is really interesting, You are a very skilled blogger.
    I have joined your feed and look forward to seeking more of your excellent post.
    Also, I’ve shared your web site in my social networks!

  2. I have been surfing online more than 2 hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. In my view, if all website owners and bloggers made good content as
    you did, the web will be a lot more useful than ever before.

  3. Hey! I know this is kind of off topic but I was wondering which blog platform
    are you using for this website? I’m getting tired of WordPress because I’ve had problems
    with hackers and I’m looking at alternatives for another platform.
    I would be great if you could point me in the direction of
    a good platform.

  4. Its like you read my mind! You appear to know so much about this, like you wrote the book in it or something.
    I think that you could do with some pics to drive
    the message home a little bit, but instead of that,
    this is magnificent blog. A fantastic read. I will definitely be back.

  5. I’m really enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a
    developer to create your theme? Superb work! natalielise plenty of fish

  6. Greetings! I know this is kinda off topic but I was wondering which
    blog platform are you using for this site?

    I’m getting fed up of WordPress because I’ve had issues with
    hackers and I’m looking at options for another platform.
    I would be great if you could point me in the direction of a good platform.

    plenty of fish natalielise

  7. obviously like your web-site but you need to test the
    spelling on several of your posts. A number of them
    are rife with spelling issues and I in finding
    it very troublesome to inform the reality on the other hand I’ll certainly come
    again again.

  8. Hi, I do think this is a great web site. I stumbledupon it 😉 I’m going to return yet again since i
    have book-marked it. Money and freedom is the best way to change,
    may you be rich and continue to guide others.

  9. Hi! Do you know if they make any plugins to help with
    SEO? I’m trying to get my blog to rank for some targeted keywords
    but I’m not seeing very good gains. If you know of any please share.
    Thanks!

  10. I was curious if you ever thought of changing the page layout of your site?

    Its very well written; I love what youve got to say. But maybe
    you could a little more in the way of content so people could connect with it better.

    Youve got an awful lot of text for only having 1 or 2 pictures.
    Maybe you could space it out better?

  11. Thanks on your marvelous posting! I definitely enjoyed reading
    it, you’re a great author.I will make sure to bookmark your blog and will come back
    very soon. I want to encourage you to continue your great posts, have a nice morning!

  12. Hello would you mind stating which blog platform you’re working with?
    I’m looking to start my own blog soon but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs
    and I’m looking for something completely unique.
    P.S My apologies for getting off-topic but I had to ask!

  13. Thanks for some other informative blog. The place else could I am getting that type of info written in such a perfect
    method? I’ve a undertaking that I am simply now operating on, and I have been at
    the glance out for such information.

  14. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command get bought an edginess over that you wish be
    delivering the following. unwell unquestionably come more
    formerly again since exactly the same nearly a lot often inside case
    you shield this increase.

  15. Great items from you, man. I have be aware your stuff previous to and you’re simply extremely excellent.

    I actually like what you’ve received here, really like what you’re
    stating and the way wherein you are saying it. You
    make it enjoyable and you still take care of to keep
    it sensible. I can not wait to read much more from you. That is really a tremendous
    website.

  16. Hey There. I found your blog using msn. This is
    an extremely well written article. I’ll make sure to bookmark it and come back to read more of your useful info.
    Thanks for the post. I will definitely comeback.

  17. Its like you read my mind! You appear to know so much about this, like you wrote the book in it or
    something. I think that you can do with some pics to drive the message
    home a little bit, but other than that, this is wonderful blog.
    An excellent read. I will definitely be back.

  18. I’m extremely impressed with your writing skills as well as with the layout on your weblog.
    Is this a paid theme or did you modify it yourself?
    Anyway keep up the excellent quality writing, it
    is rare to see a great blog like this one these days.

  19. This design is incredible! You obviously know how to keep a reader entertained.
    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
    I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

playstation 4 best games ever made 2019进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注