题解

23 条题解

  • 1
    @ 2020-10-12 19:12:12
    #include <cmath>
    #include <ctime>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    namespace dts
    {
        struct inf
        {
            int Y,R;
        };
        
        int cmp_inf(inf a,inf b)
        {
            return a.Y<b.Y;
        }
        
        struct node
        {
            int l,r,mid,num;
        };
        
        int n,m;
        inf a[50000+1];
        node st[(50000<<2)+2];
        
        #define lc(now) ((now)<<1)
        #define rc(now) ((now)<<1|1)
        
        void st_build(int now,int l,int r)
        {
            st[now].l=l,st[now].r=r;
            if (l<r)
            {
                st[now].mid=(l+r)>>1;
                st_build(lc(now),l,st[now].mid);
                st_build(rc(now),st[now].mid+1,r);
                if (a[st[lc(now)].num].R>=a[st[rc(now)].num].R)
                    st[now].num=st[lc(now)].num;
                else
                    st[now].num=st[rc(now)].num;
            }
            else if (l==r)
                st[now].num=l;
        }
        
        int st_ask(int now,int l,int r)
        {
            if (st[now].l==l&&r==st[now].r)
                return st[now].num;
            else if (r<=st[now].mid)
                return st_ask(lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r);
            else
            {
                int lans=st_ask(lc(now),l,st[now].mid);
                int rans=st_ask(rc(now),st[now].mid+1,r);
                if (a[lans].R>=a[rans].R)
                    return lans;
                else
                    return rans;
            }
        }
        
        int search(int Y,int task=0)
        {
            int l,r,mid;
            for (l=1,r=n;r-l>1;)
            {
                mid=(l+r)>>1;
                if (Y<a[mid].Y)
                    r=mid;
                else if (Y>a[mid].Y)
                    l=mid;
                else
                    return mid;
            }
            if (task==0)
            {
                if (Y==a[l].Y)
                    return l;
                else if (Y==a[r].Y)
                    return r;
                else
                    return 0;
            }
            else if (Y<a[l].Y)
                return l;
            else if (Y>a[r].Y)
                return r;
            else if (task==-1)
                return l;
            else if (task==1)
                return r;
        }
        
        void main()
        {
            while (~scanf("%d",&n))
            {
                for (int i=1;i<=n;i++)
                    scanf("%d%d",&a[i].Y,&a[i].R);
                sort(&a[1],&a[n+1],cmp_inf);
                st_build(1,1,n);
                scanf("%d",&m);
                for (int i=1;i<=m;i++)
                {
                    int xv,yv;
                    scanf("%d%d",&xv,&yv);
                    int x=search(xv),y=search(yv);
                    if (x==0||y==0||y-x<yv-xv)
                    {
                        //沒有足夠的數據
                        if (x==0)
                            x=search(xv,1);
                        if (y==0)
                            y=search(yv,-1);
                        if ((xv<a[x].Y&&a[y].Y<yv)||x==y)
                            printf("maybe\n");
                        else if (xv==a[x].Y&&a[y].Y<yv)
                        {
                            int z=st_ask(1,x+1,y);
                            if (a[z].R<a[x].R)
                                printf("maybe\n");
                            else
                                printf("false\n");
                        }
                        else if (xv<a[x].Y&&yv==a[y].Y)
                        {
                            int z=st_ask(1,x,y-1);
                            if (a[z].R<a[y].R)
                                printf("maybe\n");
                            else
                                printf("false\n");
                        }
                        else if (xv==a[x].Y&&yv==a[y].Y)
                        {
                            if (y-x>1)
                            {
                                int z=st_ask(1,x+1,y-1);
                                if (a[z].R<a[y].R&&a[y].R<=a[x].R)
                                    printf("maybe\n");
                                else
                                    printf("false\n");
                            }
                            else
                            {
                                if (a[y].R<=a[x].R)
                                    printf("maybe\n");
                                else
                                    printf("false\n");
                            }
                        }
                    }
                    else if (y-x>1)
                    {
                        int z=st_ask(1,x+1,y-1);
                        if (a[z].R<a[y].R&&a[y].R<=a[x].R)
                            printf("true\n");
                        else
                            printf("false\n");
                    }
                    else
                    {
                        if (a[y].R<=a[x].R)
                            printf("true\n");
                        else
                            printf("false\n");
                    }
                }
            }
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2017-02-02 09:56:54

    mdzz线段树60

    • @ 2017-08-06 17:48:08

      +1
      和降雨量的数据有什么区别?

  • 0
    @ 2017-09-11 12:30:03

    这个代码在bzoj和Vijos上都能A,给各位做参考QAQ

    #include <cctype>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <utility>
    #include <cassert>
    using namespace std;
    #define fi first
    #define sc second
    #define show(x) printf("%s=%d\n",#x,x);
    typedef pair<int*,int*> pip;
    typedef int ll;
    const int MAXSIZE=10000020;
    const int INF=0x3f3f3f3f;
    const int maxn=50001;
    int bufpos;
    char buf[MAXSIZE];
    void init(){
        buf[fread(buf,1,MAXSIZE,stdin)]='\0';
        bufpos=0;
    }
    int readint(){
        bool isneg;
        int val=0;
        for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
        bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
        for(;isdigit(buf[bufpos]);bufpos++)
            val=val*10+buf[bufpos]-'0';
        return isneg?-val:val;
    }
    struct segtree{
        ll maxv[maxn*8];
        int n,p;
        ll v;
        segtree(){
            memset(maxv,0,sizeof(maxv));
        }
        void _update_(int o,int l,int r){
            if (l==r){
                maxv[o]=v;
                assert(l==p);
                return;
            }
            ll m=l+(r-l)/2;
            //puts("line 35");
            if (p<=m)
                _update_(o*2,l,m);
            else _update_(o*2+1,m+1,r);
            maxv[o]=max(maxv[o*2],maxv[o*2+1]);
        }
        void update(int p,ll v){
            this->p=p;
            this->v=v;
            _update_(1,1,n);
            //puts("updated once");
        }
        int ql,qr;
        ll _query_(int o,int l,int r){
            if (ql<=l && r<=qr)
                return maxv[o];
            ll ans=-INF;
            int m=l+(r-l)/2;
            if (ql<=m)
                ans=max(ans,_query_(o*2,l,m));
            if (qr>=m+1)
                ans=max(ans,_query_(o*2+1,m+1,r));
            return ans;
        }
        ll query(int l,int r){
            if (l>r)
                return -INF;
            l=max(l,1);
            r=min(r,n);
            ql=l;
            qr=r;
            return _query_(1,1,n);
        }
    };
    segtree solver;
    int a[maxn],b[maxn];
    int main(){
        init();
        int n=readint();
        solver.n=n;
        for(int i=1;i<=n;i++){
            a[i]=readint();
            b[i]=readint();
            solver.update(i,b[i]);
        }
        int m=readint();
        for(int i=1;i<=m;i++){
            int y=readint(),x=readint();
            pip px=equal_range(a+1,a+n+1,x),py=equal_range(a+1,a+n+1,y);
            bool xknown=px.fi!=px.sc,yknown=py.fi!=py.sc,oknown=xknown && yknown && py.fi-px.fi==*py.fi-*px.fi;
            int mmax=solver.query(py.sc-a,px.fi-a-1);
            //show(mmax);show(xknown);show(yknown);show(oknown);show(py.sc-a);show(px.fi-a-1);
            if (oknown && mmax<b[px.fi-a] && b[px.fi-a]<=b[py.fi-a]){
                puts("true");
                continue;
            }
            if (xknown && yknown){
                if (mmax<b[px.fi-a] && b[px.fi-a]<=b[py.fi-a])
                    puts("maybe");
                else puts("false");
                continue;
            }
            if (!yknown || !xknown){
                if ((!yknown && !xknown) || (xknown && mmax<b[px.fi-a]) || (yknown && mmax<b[py.fi-a]))
                    puts("maybe");
                else puts("false");
                continue;
            }
            assert(false);
        }
    }
    
  • 0
    @ 2009-10-23 10:01:42

    注意这样的数据

    4

    1 10

    2 11

    4 5

    5 6

    2

    1 5

    2 5

    输出:

    false

    maybe

    ~~~~~~~~~~~~~~~~~~~~~~无奈的分割线~~~~~~~~~~~~~~~~~~~~~~~~~

    就因为这个提交了好几次。。

    还有输出用write吧

  • 0
    @ 2009-10-20 15:30:45

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 134ms

    ├ 测试数据 10:答案正确... 166ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:300ms

    离散化线段树

    Orz mike_nzk的1.83K程序

    我的沙茶程序4.77K

  • 0
    @ 2009-10-10 19:59:10

    题解:

    PS:程序还好,75行,1.83KB,并且用writeln秒杀了此题。

  • 0
    @ 2009-07-28 15:11:30

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 306ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:306ms

    离散化OK。。。

    据说把writeln改为write就秒了。

  • 0
    @ 2009-04-17 21:15:58

    这体牛B

  • 0
    @ 2009-02-21 20:26:22

    知道了……

    原来难度为00=无穷大……

  • 0
    @ 2008-10-26 18:15:20

    x=y 的时候应该怎么做啊

    谁能把程序发一下 我做不出来 啊

  • 0
    @ 2008-10-01 11:30:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    我真的很鄙视这个数据,x=y的情况很特殊。。。。。。就这个问题搞了我好几天

  • 0
    @ 2008-01-02 18:13:50

    难度为0???

  • 0
    @ 2007-11-10 18:44:41

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 88ms

  • 0
    @ 2007-10-19 19:15:09

    线段树就可以了啊。。。

    似乎不是很难。。

  • 0
    @ 2007-08-22 23:06:09

    才30分。。。大牛快来解释阿!!!怎么做。。。

  • 0
    @ 2006-10-24 22:22:33

    为什么我的河标准答案输出的一样,他还说我错???

  • 0
    @ 2006-10-24 22:20:50

    原来有这种错误。。

    当X=Y的时候。。

    “·X年和Y年以及这两年间的任意年份的降雨量都是已知的。”

    这是个很重要的条件。。

    如果已知就输出true否则maybe。。

    虽然可以确定。。如果X=Y那么显然符合条件。。但是。。

    唉……不说什么了。。

  • 0
    @ 2006-10-17 18:33:36

    用树做的 考试的时候只得了30分 郁闷 调了接近半个小时

    有谁能明确说一下到低"true""false""maybe"该如何判定啊

  • 0
    @ 2006-10-16 19:12:01

    我怎么搞都只过一个点

  • 0
    @ 2006-10-16 18:59:22

    道歉,这是我的问题,请管理员改一下吧

信息

ID
1265
难度
8
分类
数据结构 | 线段树 点击显示
标签
递交数
426
已通过
33
通过率
8%
被复制
1
上传者