【日常小测】传送门

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/438964732567423.png
官方题解:http://paste.ubuntu.com/24129177/

解题报告

这题当然可以用二维线段树做
不过显然KD-Tree更好写

但考场上T了两个点
加上一个如果子树最优解大于已知答案就不进入的剪枝后速度就成Rank 1了 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
 
int n,vout,itr[N];
struct Point{int x,y,a,b,mnx,mny,mxx,mxy,v,ori,ch[2];}p[N];
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline bool cmp(const int a, const int b) {return p[a].x < p[b].x || (p[a].x == p[b].x && p[a].y < p[b].y);}
 
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;
}
 
class KD_Tree{
    int root,ans_tmp;
    public:
        inline void init() {
            n = read();
            for (int i=1;i<=n;i++) {
                p[i].mnx = p[i].mxx = p[i].x = read();
                p[i].mny = p[i].mxy = p[i].y = read();
                p[i].a = read(); p[i].b = read();
            }       
            build(root, 1, n, 0);
        }
        inline void insert(int id, int v) {
            insert(root, 1, n, id, v);
        }
        inline int query(int id) {
            ans_tmp = 0;
            query(root, 1, n, id, judge(id, root));
            return ans_tmp;         
        }
    private:
        void build(int &w, int l, int r, bool t) {
            if (l == r) w = l;
            else if (l < r) {
                int mid = l + r >> 1; w = mid;
                if (t) nth_element(p+l, p+mid, p+r+1, cmpx);
                else nth_element(p+l, p+mid, p+r+1, cmpy);
                build(p[w].ch[0], l, mid-1, t^1);
                build(p[w].ch[1], mid+1, r, t^1);
                for (int i=0,s;i<2;i++) if (s = p[w].ch[i]) {
                    p[w].mnx = min(p[s].mnx, p[w].mnx);
                    p[w].mny = min(p[s].mny, p[w].mny);
                    p[w].mxx = max(p[s].mxx, p[w].mxx);
                    p[w].mxy = max(p[s].mxy, p[w].mxy);
                }
            }
        }
        inline bool Contain(int w, int id) {
            if (!w) return 0;
            else return p[w].mnx <= p[id].x && p[id].x <= p[w].mxx && p[w].mny <= p[id].y && p[id].y <= p[w].mxy;
        }
        void insert(int w, int l, int r, int id, int v) {
            p[w].v = max(p[w].v, v);
            if (l < r) {
                int mid = l + r >> 1;
                if (Contain(p[w].ch[0], id)) insert(p[w].ch[0], l, mid-1, id, v);
                if (Contain(p[w].ch[1], id)) insert(p[w].ch[1], mid+1, r, id, v);
            }
        }
        inline int judge(int i, int j) {
            if (p[i].x <= p[j].mnx && p[i].y <= p[j].mny && p[j].mxx <= p[i].a && p[j].mxy <= p[i].b) return 2;
            else return max(p[i].x, p[j].mnx) <= min(p[i].a, p[j].mxx) && max(p[i].y , p[j].mny) <= min(p[i].b, p[j].mxy);
        }
        void query(int w, int l, int r, int id, int ty) {
            if (ty == 2) ans_tmp = max(ans_tmp, p[w].v);
            else {
                if (p[id].x <= p[w].x && p[w].x <= p[id].a && p[id].y <= p[w].y && p[w].y <= p[id].b) ans_tmp = max(ans_tmp, p[w].ori);
                int mid = l + r >> 1, tmp;
                if (p[w].ch[0] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[0]))) query(p[w].ch[0], l, mid-1, id, tmp);
                if (p[w].ch[1] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[1]))) query(p[w].ch[1], mid+1, r, id, tmp);
            }
        }
}kd;
 
int main() {
    kd.init();
    for (int i=1;i<=n;i++) itr[i] = i;
    sort(itr+1, itr+1+n, cmp);
    for (int j=n,v,i=itr[j];j;i=itr[--j]) {
        v = kd.query(i);
        kd.insert(i, ++v);
        p[i].ori = v;
        vout = max(v, vout);    
    }
    printf("%d\n",vout);
    return 0;
}

26 thoughts to “【日常小测】传送门”

  1. Please let me know if you’re looking for a writer for your weblog.

    You have some really great articles and I believe I would be a good asset.
    If you ever want to take some of the load off, I’d absolutely love to write some articles for your blog in exchange for a link back to mine.

    Please blast me an email if interested. Regards!

  2. Please let me know if you’re looking for a article writer for your blog.
    You have some really good posts and I believe I would be a good asset.
    If you ever want to take some of the load off, I’d love to write some material for your
    blog in exchange for a link back to mine. Please blast me an email if interested.
    Kudos!

  3. I got this website from my pal who informed me concerning this web site and at the moment this time I am visiting this site and reading very
    informative posts at this place.

  4. I was recommended this website by way of my cousin. I’m now not certain whether this put up is written by means of
    him as no one else understand such exact about my trouble.
    You are amazing! Thank you!

  5. I am curious to find out what blog platform you have been working with?
    I’m experiencing some minor security problems with my latest site and I’d like to find something more
    safeguarded. Do you have any suggestions?

  6. Admiring the time and effort you put into your blog and in depth information you present.
    It’s good to come across a blog every once in a while that isn’t the same old rehashed information. Fantastic read!
    I’ve saved your site and I’m including your RSS feeds to my Google account.

  7. hello!,I really like your writing very so much!
    percentage we keep up a correspondence extra approximately your article on AOL?
    I require a specialist on this space to solve my problem. Maybe that is you!
    Having a look forward to see you.

  8. Do you mind if I quote a few of your articles as
    long as I provide credit and sources back to your weblog?
    My blog is in the very same area of interest as yours and my users would definitely benefit
    from a lot of the information you provide here. Please let me know if this okay with you.
    Thank you!

  9. What i do not understood is if truth be told how you’re now not actually much more smartly-liked than you might be right now.
    You’re so intelligent. You realize therefore considerably relating to this subject,
    produced me individually consider it from so many numerous angles.
    Its like women and men aren’t involved unless it’s something to do with Girl gaga!

    Your individual stuffs excellent. At all times deal with it up!

  10. Greetings, I believe your web site could possibly be having web browser compatibility problems.
    Whenever I look at your web site in Safari, it looks fine however,
    if opening in Internet Explorer, it’s got some overlapping issues.
    I merely wanted to provide you with a quick heads
    up! Besides that, wonderful website!

  11. Hi there! I know this is kinda 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 issues with hackers and I’m looking at options for another platform.
    I would be awesome if you could point me in the direction of a good platform.

  12. First off I want to say superb blog! I had a quick question which I’d like to ask if you do not
    mind. I was curious to know how you center yourself and clear your head prior
    to writing. I have had a hard time clearing my thoughts in getting my ideas out.
    I do enjoy writing but it just seems like the first 10
    to 15 minutes tend to be wasted simply just trying to figure out how to begin. Any suggestions or tips?

    Cheers!

  13. This design is incredible! You obviously know how to keep a reader amused.

    Between your wit and your videos, I was almost moved to
    start my own blog (well, almost…HaHa!) Excellent job.
    I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

  14. Greetings! Very helpful advice within this article!
    It is the little changes which will make the most
    significant changes. Many thanks for sharing!

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

  16. Wow, marvelous weblog layout! How long have you ever been running
    a blog for? you made running a blog look easy.
    The overall look of your site is fantastic, as neatly
    as the content!

Leave a Reply

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