[ICPC Northern Eurasia Finals 2018 K]King Kog’s Reception

Link

多年不碰数据结构的老年选手,估计是做麻烦了。

Solution

对所有来的时刻开线段树,记录每个区间来的骑士的开始时间和结束时间,再记录一下这段时间内有多少时间是空白的,那么这些空白时间可以在开始时间延后时起到“缓冲作用”。
合并也好合并,就是一开始写错了没看出来。

Code

#include <bits/stdc++.h>

const int XN=3e5+11;

struct SegTree {
    struct Info {
        long long l,r,blank;
        Info():l(0),r(-1) {}

        operator bool() const {
            return l<=r;
        }

        friend Info Merge(Info const &a,Info const &b) {
            if(!a) return b;
            else if(!b) return a;
            else {
                Info res=a;
                long long rblank=b.blank+std::max(b.l-a.r-1,0ll);
                res.r=b.r+std::max(a.r-b.l+1-rblank,0ll);
                res.blank+=std::max(rblank-std::max(a.r-b.l+1,0ll),0ll);//
                return res;
            }
        }
    };
    struct Node {
        Node *son[2];
        Info v;
        Node() {
            son[0]=son[1]=0;
        }
    }*root;
    int L,R;

    SegTree(int L,int R):root(0),L(L),R(R) {}

    void Modify(int t,int d) {
        std::function<void(Node*&,int,int)> Modify=[&](Node *&pos,int L,int R) {
            if(!pos)
                pos=new Node;
            if(L==R) {
                pos->v.r=(pos->v.l=t)+d-1;
                pos->v.blank=0;
            } else {
                int M=(L+R)/2;
                t<=M?Modify(pos->son[0],L,M)
                    :Modify(pos->son[1],M+1,R);
                pos->v=Merge(pos->son[0]?pos->son[0]->v:Info()
                            ,pos->son[1]?pos->son[1]->v:Info());
            }
        };
        Modify(root,L,R);
    }

    Info Query(int t) {
        std::function<Info(Node*,int,int)> Query=[&](Node *pos,int L,int R) {
            if(!pos)
                return Info();
            if(R<=t)
                return pos->v;
            else {
                int M=(L+R)/2;
                Info res=Query(pos->son[0],L,M);
                if(M<t)
                    res=Merge(res,Query(pos->son[1],M+1,R));
                return res;
            }
        };
        Info res=Query(root,L,R);
        return Query(root,L,R);
    }
};

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SegTree seg(1,1e6);
    int q;std::cin>>q;
    static int vt[XN];
    for(int ks=1;ks<=q;++ks) {
        char op[10];
        std::cin>>op;
        if(op[0]=='+') {
            int t,d;std::cin>>t>>d;
            vt[ks]=t;
            seg.Modify(t,d);
        } else if(op[0]=='-') {
            int id;std::cin>>id;
            seg.Modify(vt[id],0);
        } else {
            int t;std::cin>>t;
            std::cout<<std::max(0ll,seg.Query(t).r+1-t)<<'\n';
        }
    }
    return 0;
}

发表评论

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