【日常小测】摩尔庄园

Qizy 其他, 图论, 杂项, 网络流, 解题报告, 费用流

题目大意

给定一棵$n(n \le 10^5)$个节点的以$1$为根的有根树，第$i$个结点上有$c_i$个食物，其父亲为$\lfloor \frac{i}{2} \rfloor$
现在依次给出$m$个拉姆，依次询问前$i$个拉姆都有东西吃的最短移动距离和
依次输出这$m$次询问的答案

解题报告

如果点数很小的话，我们显然可以跑个费用流就可以了！
但这题点这么多怎么办 QwQ

那我们就手动增广！
考虑维护一个$val_i$表示以$i$为根的子树中最近的有食物的点到$i$的距离
于是我们可以花$O(\log n)$的时间暴力在树上爬一爬就可以代替费用流的SPFA
然后考虑修改沿途边的边权，因为树高是$\log n$级别的，于是我们也是暴力修改就好
最后再用更新一下受影响的$val_i$来方便下次增广就可以辣！

以前听说过手动增广的题目，不过一次都还没有写过
这次写一写感觉这货非常好玩啊！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const int INF = 1e9;
 
int  n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[N]; 
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    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;
}
 
inline int LCA(int u, int v) {
    for (;u!=v;u>>=1) 
        if (u < v) swap(u, v);
    return u;
}
 
inline void update(int w) {
    static int ls, rs, cl, cr;
    if (cnt[w]) sur[w] = w, val[w] = 0;
    else sur[w] = 0, val[w] = INF;
    if ((ls=w<<1) <= n) {
        cl = cost[ls] > 0? -1: 1;
        if(val[ls] + cl < val[w]) {
            val[w] = val[ls] + cl;
            sur[w] = sur[ls];
        }
    }
    if ((rs=ls|1) <= n) {
        int cr = cost[rs] > 0? -1: 1;
        if(val[rs] + cr < val[w]) {
            val[w] = val[rs] + cr;
            sur[w] = sur[rs];
        }
    }
}
 
inline void modify(int w, int p, int delta) {
    while (w != p) {
        cost[w] += delta;
        update(w); w >>= 1;  
    }
}
 
inline int query(int w, int &ans) {
    static int ret, delta; delta = 0;
    for (;w;w>>=1) {
        if (val[w] + delta < ans) {
            ans = val[w] + delta;
            ret = sur[w];
        }
        delta += cost[w] >= 0? 1: -1;
    } return ret;
}
 
int main() {
    n = read(); m = read();
    for (int i=1;i<=n;i++) cnt[i] = read();
    for (int i=1;i<=m;i++) pos[i] = read();
    for (int i=n;i;i--) update(i);
    for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
        cnt[v=query(u=pos[i], ans)]--; 
        printf("%d\n",vout+=ans);
        int lca = LCA(u, v);
        modify(u, lca, 1); modify(v, lca, -1);
        for (;lca;lca>>=1) update(lca);
    }
    return 0;
}

323 thoughts to “【日常小测】摩尔庄园”

  3. You really make it appear so easy with your presentation however I in finding this topic to be really
    something that I think I would never understand. It sort of feels too complex and
    extremely vast for me. I’m looking forward for your subsequent submit, I will try to
    get the hold of it!

    Reply

  5. Howdy! I could have sworn I’ve been to this blog before but after reading through some of the post I realized
    it’s new to me. Anyways, I’m definitely delighted I found it and I’ll be bookmarking and checking back often!

    Reply

  7. Hey there! I know this is somewhat 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 options for another platform.
    I would be fantastic if you could point me in the
    direction of a good platform.

    Reply

  11. you’re really a excellent webmaster. The site loading velocity is amazing.
    It seems that you are doing any distinctive trick.
    Moreover, The contents are masterpiece. you’ve done a magnificent
    job on this subject!

    Reply

  12. Pretty section of content. I just stumbled upon your
    site and in accession capital to assert that I acquire actually enjoyed account your blog posts.
    Anyway I’ll be subscribing to your feeds and even I achievement you access consistently
    rapidly.

    Reply

  18. Just desire to say your article is as astounding.
    The clarity to your post is just spectacular and that i can think you’re a professional on this subject.
    Fine with your permission allow me to take hold of your RSS feed to stay up to date with imminent post.
    Thank you one million and please keep up the rewarding work.

    Reply

  21. I’m curious to find out what blog system you have been working with?
    I’m experiencing some minor security issues with my latest website and I would like
    to find something more safe. Do you have any recommendations?
    pof natalielise

    Reply

  23. Have you ever thought about creating an ebook or guest authoring on other blogs?
    I have a blog based upon on the same ideas you discuss and would really like
    to have you share some stories/information. I know my visitors
    would enjoy your work. If you are even remotely interested, feel free to send me an e-mail.

    pof natalielise

    Reply

  27. My brother recommended I would possibly like this web site.
    He was once entirely right. This post actually made my day.
    You can not imagine just how a lot time I had spent for
    this info! Thank you!

    Reply

  28. Hi, I do believe this is a great web site. I stumbledupon it 😉 I am going to return once again since
    i have book-marked it. Money and freedom is the best way to change,
    may you be rich and continue to help other people.

    Reply

  31. Hey, I think your site might be having browser compatibility issues.

    When I look at your website in Safari, it looks fine but
    when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, great blog!

    Reply

  32. Admiring the hard work you put into your site and detailed information you present.
    It’s great to come across a blog every once in a
    while that isn’t the same out of date rehashed material.
    Wonderful read! I’ve saved your site and I’m including your RSS feeds
    to my Google account.

    Reply

  35. I don’t even understand how I finished up here,
    but I thought this submit used to be good. I do not know
    who you’re but definitely you are going to a famous blogger
    in case you are not already. Cheers!

    Reply

  38. I like the helpful info you provide in your articles.

    I’ll bookmark your blog and check again here frequently.
    I’m quite sure I will learn lots of new stuff right here!
    Good luck for the next!

    Reply

  39. Link exchange is nothing else however it is simply placing the other person’s website link on your page
    at proper place and other person will also do similar in favor of you.

    Reply

  40. I’ve been browsing 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 website owners and bloggers made good content as you did, the web
    will be much more useful than ever before.

    Reply

  41. Hmm is anyone else experiencing problems with the images on this blog
    loading? I’m trying to determine if its a problem on my end or if it’s the blog.
    Any feedback would be greatly appreciated.

    Reply

  42. Having read this I thought it was very informative. I appreciate
    you spending some time and effort to put this informative article together.
    I once again find myself spending a lot of time both reading and commenting.
    But so what, it was still worth it!

    Reply

  43. Write more, thats all I have to say. Literally, it
    seems as though you relied on the video to make your point.

    You obviously know what youre talking about, why throw away your intelligence on just posting videos to your weblog
    when you could be giving us something enlightening to read?

    Reply

  44. Hey There. I found your blog using msn. This is a really well written article.
    I’ll make sure to bookmark it and come back to read more of your useful information. Thanks for the post.
    I’ll definitely comeback.

    Reply

  46. Today, I went to the beach with my kids. I found a sea shell and gave
    it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.

    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is entirely off topic
    but I had to tell someone!

    Reply

  50. Wow, fantastic blog structure! How lengthy have you ever been running a blog for?
    you made running a blog glance easy. The overall look of your web site is excellent,
    as smartly as the content material!

    Reply

  68. I do not even know the way I ended up right here, however
    I thought this publish was great. I do not recognize who you are but definitely you are going to a well-known blogger if you
    happen to aren’t already. Cheers!

    Reply

  91. you’re really a just right webmaster. The website loading speed
    is amazing. It seems that you are doing any unique trick.
    Moreover, The contents are masterpiece. you have performed a excellent task on this topic!

    Reply

  95. Having read this I believed it was really informative. I appreciate you spending some time and energy to put this content together.

    I once again find myself spending a lot of time both reading and commenting.
    But so what, it was still worthwhile!

    Reply

  105. Good post. I learn something totally new and challenging on websites I stumbleupon on a daily
    basis. It will always be helpful to read content from other writers and use
    a little something from their websites.

    Reply

  155. I got this site from my friend who shared with me concerning this website and now this time
    I am visiting this website and reading very informative articles at this time.

    Reply

  189. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored material stylish.
    nonetheless, you command get bought an edginess over that you
    wish be delivering the following. unwell unquestionably come further formerly again as exactly the same nearly a lot often inside
    case you shield this increase.

    Reply

  203. This is very interesting, You’re a very skilled blogger.
    I have joined your rss feed and look forward to in the hunt for extra
    of your fantastic post. Additionally, I have shared your website in my
    social networks

    Reply

  233. continuously i used to read smaller posts which also clear their
    motive, and that is also happening with this piece of writing which I am reading at this place.

    Reply

  235. Hello! I could have sworn I’ve been to this blog before but after checking through
    some of the post I realized it’s new to me. Anyways, I’m definitely glad
    I found it and I’ll be book-marking and checking back frequently!

    Reply

  261. I really like your writing style, superb information, thanks for putting up :D. “Kennedy cooked the soup that Johnson had to eat.” by Konrad Adenauer.

    Reply

  279. Wonderful blog! I found it while browsing on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Thank you|

    Reply

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

    Reply

  286. Heya are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and create my own. Do you require any html coding knowledge to make your own blog? Any help would be really appreciated!|

    Reply

  299. hey there and thank you for your info – I’ve definitely picked up something new from right here. I did however expertise some technical issues using this website, since I experienced to reload the site lots of times previous to I could get it to load correctly. I had been wondering if your web hosting is OK? Not that I’m complaining, but sluggish loading instances times will very frequently affect your placement in google and can damage your high-quality score if ads and marketing with Adwords. Well I’m adding this RSS to my email and could look out for much more of your respective intriguing content. Make sure you update this again very soon.|

    Reply

  304. I am not positive where you’re getting your information, but great topic. I needs to spend some time studying more or figuring out more. Thank you for wonderful info I was looking for this info for my mission.|

    Reply

  313. Have you ever thought about publishing an e-book or guest authoring on other sites? I have a blog based on the same ideas you discuss and would love to have you share some stories/information. I know my readers would value your work. If you are even remotely interested, feel free to shoot me an e-mail.|

    Reply

  323. I believe what you posted made a ton of sense. But, what about this? suppose you wrote a catchier post title? I mean, I don’t want to tell you how to run your blog, however suppose you added a post title that grabbed people’s attention? I mean BLOG_TITLE is a little boring. You ought to look at Yahoo’s front page and watch how they create article titles to grab viewers interested. You might try adding a video or a related picture or two to get people excited about what you’ve got to say. In my opinion, it might bring your posts a little livelier.|

    Reply

Leave a Reply

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