2018ICPC 沈阳 E

左手的ㄟ右手 2023-10-11 13:27 63阅读 0赞

> https://cn.vjudge.net/problem/2057332/origin

题目的询问为L - R之间的两人曼哈顿距离最长

将曼哈顿距离转切比雪夫距离，线段树维护区间内的最(次)大x和最(次)小x，并且最大次大，最小次小的种族不同

y轴同理，建两颗线段树即可，询问的时候查询区间最大小值的差就好了

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLI pair<long long,int>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
        int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
        if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const LL INF = 1e18;
    const int mod = 1e9 + 7; 
    int N,M,K;
    struct Node{
        LL x,y;
        LL c;
    }node[maxn];
    struct Tree{
        int l,r;
        PLI Max,Mmax,Min,Mmin;
    }tree[2][maxn << 2];
    void Pushup(Tree &t,Tree a,Tree b){  
        if(a.Max.fi < b.Max.fi) swap(a,b);
        if(b.Max.fi > a.Mmax.fi && b.Max.se != a.Max.se) a.Mmax = b.Max;
        if(b.Mmax.fi > a.Mmax.fi && b.Mmax.se != a.Max.se) a.Mmax = b.Mmax;
        t.Max = a.Max; t.Mmax = a.Mmax;
        
        if(a.Min.fi > b.Min.fi) swap(a,b);
        if(b.Min.fi < a.Mmin.fi && b.Min.se != a.Min.se) a.Mmin = b.Min;
        if(b.Mmin.fi < a.Mmin.fi && b.Mmin.se != a.Min.se) a.Mmin = b.Mmin; 
        t.Min = a.Min; t.Mmin = a.Mmin;
    }
    void Build(Tree * tree,int t,int l,int r,bool flag){
        tree[t].l = l; tree[t].r = r;
        tree[t].Max = tree[t].Mmax = mp(-INF,0);
        tree[t].Min = tree[t].Mmin = mp(INF,0);
        if(l == r){
            if(flag) tree[t].Max = tree[t].Min = mp(node[l].x,node[l].c);
            else tree[t].Max = tree[t].Min = mp(node[l].y,node[l].c);
            return;
        }
        int m = l + r >> 1;
        Build(tree,t << 1,l,m,flag); Build(tree,t << 1 | 1,m + 1,r,flag);
        Pushup(tree[t],tree[t << 1],tree[t << 1 | 1]);
    }
    void update(Tree* tree,int t,int k,int x){
        if(tree[t].l == tree[t].r){
            tree[t].Max.fi += x;
            tree[t].Min.fi += x;
            return;
        }
        int m = tree[t].l + tree[t].r >> 1;
        if(k <= m) update(tree,t << 1,k,x);
        else update(tree,t << 1 | 1,k,x);
        Pushup(tree[t],tree[t << 1],tree[t << 1 | 1]);
    }
    void update2(Tree* tree,int t,int k,int c){
        if(tree[t].l == tree[t].r){
            tree[t].Max.se = tree[t].Min.se = c;
            return;
        }
        int m = tree[t].l + tree[t].r >> 1;
        if(k <= m) update2(tree,t << 1,k,c);
        else update2(tree,t << 1 | 1,k,c);
        Pushup(tree[t],tree[t << 1],tree[t << 1 | 1]);
    }
    Tree query(Tree *tree,int t,int l,int r){
        if(l <= tree[t].l && tree[t].r <= r) return tree[t];
        int m = tree[t].l + tree[t].r >> 1;
        if(r <= m) return query(tree,t << 1,l,r);
        else if(l > m) return query(tree,t << 1 | 1,l,r);
        else{
            Tree ans;
            Pushup(ans,query(tree,t << 1,l,m),query(tree,t << 1 | 1,m + 1,r));
            return ans;
        }
    }
    int main(){
        int T = read(); int CASE = 1;
        while(T--){
            Sca2(N,M);
            printf("Case #%d:\n",CASE++);
            for(int i = 1; i <= N ; i ++){
                LL x = read(),y = read();
                Sca(node[i].c);
                node[i].x = x + y; node[i].y = x - y;
            }
            Build(tree[0],1,1,N,1);
            Build(tree[1],1,1,N,0);
            while(M--){
                 int op = read();
                 if(op == 1){
                     int k = read(),x = read(),y = read();  
                     update(tree[0],1,k,x + y);
                     update(tree[1],1,k,x - y);
                 }else if(op == 2){
                     int k,c; Sca2(k,c);
                     update2(tree[0],1,k,c);
                     update2(tree[1],1,k,c);
                 }else{
                     int l,r; Sca2(l,r);
                     LL ans = 0;
                    Tree tmp = query(tree[0],1,l,r);
                    if(tmp.Max.se != tmp.Min.se) ans = max(ans,tmp.Max.fi - tmp.Min.fi);
                    else ans = max(ans,max(tmp.Max.fi - tmp.Mmin.fi,tmp.Mmax.fi - tmp.Min.fi));
                    tmp = query(tree[1],1,l,r);
                    if(tmp.Max.se != tmp.Min.se) ans = max(ans,tmp.Max.fi - tmp.Min.fi);
                    else ans = max(ans,max(tmp.Max.fi - tmp.Mmin.fi,tmp.Mmax.fi - tmp.Min.fi));
                     Prl(ans);
                 }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11342318.html