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

80 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!

  20. I’m not sure where you are getting your info, but great topic.
    I needs to spend some time learning much more or understanding more.
    Thanks for wonderful information I was looking for this information for my mission.

  21. Thank you a lot for sharing this with all people you really understand what you’re talking about!
    Bookmarked. Kindly also visit my website =). We will have a
    hyperlink trade agreement between us

  22. My developer is trying to convince me to move to .net from PHP.
    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using Movable-type on numerous websites for about a year and am anxious about switching to another
    platform. I have heard fantastic things about blogengine.net.

    Is there a way I can import all my wordpress content into it?
    Any help would be greatly appreciated!

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

  24. Howdy! This post couldn’t be written any better!
    Reading through this post reminds me of my previous room mate!
    He always kept chatting about this. I will forward this write-up to
    him. Pretty sure he will have a good read. Thanks for sharing!

  25. Hello there! I know this is somewhat off topic but I was wondering
    which blog platform are you using for this website?
    I’m getting sick and tired of WordPress because I’ve had
    issues with hackers and I’m looking at options for another
    platform. I would be fantastic if you could point
    me in the direction of a good platform.

  26. Wonderful article! That is the type of information that are meant to
    be shared around the web. Disgrace on the search engines for no longer positioning this
    post upper! Come on over and talk over with my site .
    Thank you =)

  27. Hello there! This article couldn’t be written any better!
    Looking at this article reminds me of my previous roommate!
    He continually kept talking about this. I’ll send
    this post to him. Pretty sure he will have a great read.
    I appreciate you for sharing!

  28. Heya terrific blog! Does running a blog similar to this require
    a large amount of work? I’ve virtually no knowledge of
    coding but I had been hoping to start my own blog in the near future.
    Anyhow, if you have any recommendations or techniques for new blog owners
    please share. I understand this is off topic nevertheless I just
    needed to ask. Many thanks!

  29. Good day! I just would like to offer you a huge thumbs up for your excellent information you have got right
    here on this post. I’ll be coming back to your website for more soon.

  30. Nice blog here! Also your web site loads up
    fast! What web host are you using? Can I get your affiliate link to your host?
    I wish my web site loaded up as quickly as yours lol

  31. You really make it appear so easy together with your
    presentation but I to find this matter to be really one thing which I believe
    I’d never understand. It kind of feels too complex and very huge
    for me. I’m having a look forward in your subsequent submit,
    I will attempt to get the cling of it!

  32. I don’t even know how I ended up here, but I thought this post was
    good. I don’t know who you are but certainly you are going to
    a famous blogger if you aren’t already 😉 Cheers!

  33. Hi there just wanted to give you a quick heads up and let you know
    a few of the images aren’t loading correctly.
    I’m not sure why but I think its a linking issue.
    I’ve tried it in two different browsers and both show the same outcome.

  34. My coder is trying to convince me to move to .net from PHP.
    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using Movable-type on various websites
    for about a year and am nervous about switching to another platform.
    I have heard fantastic things about blogengine.net.
    Is there a way I can transfer all my wordpress
    posts into it? Any kind of help would be really appreciated!

  35. Amazing! This blog looks exactly like my old one!
    It’s on a totally different topic but it has pretty much
    the same layout and design. Excellent choice of colors!

  36. Hi there! Do you know if they make any plugins to protect against hackers?
    I’m kinda paranoid about losing everything I’ve
    worked hard on. Any tips?

  37. Definitely believe that which you said. Your favorite justification appeared to be on the net the easiest thing to be aware of. I say to you, I certainly get annoyed while people consider worries that they plainly do not know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people could take a signal. Will likely be back to get more. Thanks

Leave a Reply to plenty of fish dating site Cancel reply

Your email address will not be published. Required fields are marked *