[ICPC 2018 Shenyang Onsite E][Gym101955E]The Kouga Ninja Scrolls

Link

Solution

曼哈顿转切比雪夫之后x,y独立了。
问题变成从区间中选取两个颜色不同的数字使得差值最大。
维护区间最大次大、最小次小值,满足最大次大、最小次小值分别是不同的颜色,最大差值一定来源于这四个数字。枚举合法情况判一判就好了。

Code

const int XN=1e5+11;
const long long INF=1e18;

struct SegTree {

    struct Data {
        std::pair<long long,int> mn[2],mx[2];

        Data() {
            mn[0]=mn[1]=std::pair<long long,int>(INF,-1);
            mx[0]=mx[1]=std::pair<long long,int>(-INF,-1);
        }

        long long Solve() {
            long long res=0;
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    if(mn[i].second!=mx[j].second)
                        Enlarge(res,mx[j].first-mn[i].first);
            return res;
        }

        friend Data Merge(Data const &a,Data const &b) {
            Data res;
            auto Update=[&](Data const &x) {
                for(int i=0;i<2;++i) {
                    if(x.mn[i].first<res.mn[0].first) {
                        if(x.mn[i].second!=res.mn[0].second)
                            res.mn[1]=res.mn[0];
                        res.mn[0]=x.mn[i];
                    } else if(x.mn[i].first<res.mn[1].first && x.mn[i].second!=res.mn[0].second)
                        res.mn[1]=x.mn[i];

                    if(x.mx[i].first>res.mx[0].first) {
                        if(x.mx[i].second!=res.mx[0].second)
                            res.mx[1]=res.mx[0];
                        res.mx[0]=x.mx[i];
                    } else if(x.mx[i].first>res.mx[1].first && x.mx[i].second!=res.mx[0].second)
                        res.mx[1]=x.mx[i];

                }
            };
            Update(a);Update(b);
            return res;
        }
    };

    struct Node {
        Node *son[2];
        Data v;
        Node(std::pair<long long,int> const &x) {
            v.mn[0]=v.mx[0]=x;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc(XN*10*sizeof(Node)),*mem=0;
            return flag?mem++:mem=pool;
        }

        void Up() {
            v=Merge(son[0]->v,son[1]->v);
        }
    }*root;

    int L,R;

    SegTree(std::pair<long long,int> a[],int n):L(1),R(n) {
        std::function<void(Node*&,int,int)> Build=
            [&](Node *&pos,int L,int R) {
                pos=new Node(a[L]);
                if(L==R)
                    return;
                else {
                    int M=(L+R)/2;
                    Build(pos->son[0],L,M);
                    Build(pos->son[1],M+1,R);
                    pos->Up();
                }

            };
        Build(root,1,n);
    }

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

    template <class T>
    void Modify(int goal,T F) {
        std::function<void(Node*,int,int)> Modify=
            [&](Node *pos,int L,int R) {
                if(L==R) {
                    F(pos->v.mn[0]);
                    F(pos->v.mx[0]);
                } else {
                    int M=(L+R)/2;
                    goal<=M?Modify(pos->son[0],L,M):Modify(pos->son[1],M+1,R);
                    pos->Up();
                }
            };
        Modify(root,L,R);
    }
};

void Work() {
    SegTree::Node::operator new(0);

    auto Convert=[](int x,int y)->std::pair<int,int> { return std::pair<int,int>(x+y,x-y); };

    int n,m;fin>>n>>m;
    static std::pair<long long,int> cx[XN],cy[XN];
    for(int i=1;i<=n;++i) {
        int x,y,c;fin>>x>>y>>c;
        std::tie(cx[i].first,cy[i].first)=Convert(x,y);
        cx[i].second=cy[i].second=c;
    }

    SegTree segX(cx,n),segY(cy,n);

    for(int q=1;q<=m;++q) {
        int op;fin>>op;
        switch(op) {
            case 1 : {
                int id,x,y;fin>>id>>x>>y;
                std::tie(x,y)=Convert(x,y);
                segX.Modify(id,[&](std::pair<long long,int> &a) { a.first+=x; });
                segY.Modify(id,[&](std::pair<long long,int> &a) { a.first+=y; });
            } break;
            case 2 : {
                int id,c;fin>>id>>c;
                auto Change=[&](std::pair<long long,int> &a) { a.second=c; };
                segX.Modify(id,Change);
                segY.Modify(id,Change);
            } break;
            case 3 : {
                int l,r;fin>>l>>r;
                fout<<std::max(segX.Query(l,r),segY.Query(l,r))<<'\n';
            } break;
        }
    }
}

int main() {
    int T;fin>>T;

    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        Work();
    }
    return 0;
}