Solution - HDU 6638 Snowy Smile (Line Segment Tree)

Solution - HDU 6638 Snowy Smile (Line Segment Tree)

Topic link: http://acm.hdu.edu.cn/showproblem.php?pid=6638

meaning of the title

There are 2,000 points on the two-dimensional plane. The weights of each point are between (109,109)(-10^9,10^9)(109,109). The coordinates of each point are also between (109,109)(-10^9,10^9)(109,109). Now you have to draw a matrix to get some weights in the matrix. The boundary of the matrix must be parallel to the X axis Y axis.

thinking

  1. Line Segment Tree Maintenance Maximum Subsection and Board Title
  2. Line segment tree maintains prefix sum and uses maximum and minimum values to find the maximum subsection sum of the current enumeration.

Code

//Code 1 Maximum Subparagraph and
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(ll i = (ll)j;i <= (ll)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define max(a,b)  (((a)>(b))?(a):(b))
#define min(a,b)  (((a)<(b))?(a):(b))
#define pb push_back
inline void test(){cerr<<"\n";}
template<typename T,typename... Args>inline void  test(T x,Args... args){cerr<<x<<" ";test(args...);}

typedef long long ll;
typedef pair<ll,ll> pi;
const ll MAXN = (ll)1e6+7;

struct Node{
    ll x,y,w;
    Node(ll x = 0,ll y = 0,ll w = 0):x(x),y(y),w(w){}
    bool operator < (const Node&a) const {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
}e[MAXN];

vector<ll> vpx,vpy;
inline ll getX(ll x) {return lower_bound(vpx.begin(),vpx.end(),x)-vpx.begin()+1; }
inline ll getY(ll y) {return lower_bound(vpy.begin(),vpy.end(),y)-vpy.begin()+1; }

ll n,m;

#define lson rt<<1
#define rson rt<<1|1

ll val[2007<<2];
ll sum[2007<<2];
ll lsum[2007<<2];
ll rsum[2007<<2];

inline void Build(ll l,ll r,ll rt) {
    if (l == r) {
        val[rt] = sum[rt] = lsum[rt] = rsum[rt] = 0;
        return ;
    }
    ll m = l+r>>1;
    Build(l,m,lson);
    Build(m+1,r,rson);
    val[rt] = sum[rt] = lsum[rt] = rsum[rt] = 0;
}
inline void PushUp(ll l,ll r,ll rt) {
    val[rt] = val[lson] + val[rson];
    sum[rt] = max(lsum[rson]+rsum[lson],max(sum[lson],sum[rson]));
    lsum[rt] = max(lsum[lson],val[lson]+lsum[rson]);
    rsum[rt] = max(rsum[rson],val[rson]+rsum[lson]);
}
inline void Update(ll L,ll C,ll l,ll r,ll rt) {
    if (l == r) {
        val[rt] += C;
        sum[rt] = max(0LL,val[rt]);
        rsum[rt] = lsum[rt] = sum[rt];
        return ;
    }b   
    ll m = l+r>>1;
    if (L <= m) Update(L,C,l,m,lson);
    else        Update(L,C,m+1,r,rson);
    PushUp(l,r,rt);
}

vector<ll> vxx[5007];
bool mark[5007];

inline void init() {
    vpx.clear();
    vpy.clear();
}

int main()
{
    ll T;
    scanf("%lld",&T);
    while (T --) {
        ll N;
        init();
        scanf("%lld",&N);
        rep(i,1,N) {
            ll x,y,w;
            scanf("%lld %lld %lld",&x,&y,&w);
            e[i] = Node(x,y,w);
            vpx.pb(x);
            vpy.pb(y);
        }
        sort(vpx.begin(),vpx.end()); vpx.erase(unique(vpx.begin(),vpx.end()),vpx.end());
        sort(vpy.begin(),vpy.end()); vpy.erase(unique(vpy.begin(),vpy.end()),vpy.end());
        n = vpx.size();m = vpy.size();
        rep(i,0,n+3) vxx[i].clear();

        rep(i,1,N) {
            e[i].x = getX(e[i].x);
            e[i].y = getY(e[i].y);
        }

        sort(e+1,e+1+N);
        rep(i,1,N) {
            vxx[e[i].x].pb(i);
        }

        ll ans = 0;
        ll u,d;
        rep(i,1,N) {
            Build(1,m,1);
            memset(mark,0,sizeof(bool)*(n+2));
            rep(j,i,N) {
                if (mark[e[j].x] == 0) {
                    mark[e[j].x] = 1;
                    ll now = e[j].x;
                    rep(kk,0,vxx[now].size()-1) {
                        ll id = vxx[now][kk];
                        Update(e[id].y,e[id].w,1,m,1);
                    }
                }
                ans = max(ans,sum[1]);
            }
        }
        printf("%lld\n",ans);
    }
}
//Code Two-Dimensional Protected Prefixes and
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(ll i = (ll)j;i <= (ll)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl

#define pb push_back
void test(){cerr<<"\n";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<x<<" ";test(args...);}

typedef long long ll;
typedef pair<ll,ll> pi;
const ll MAXN = (ll)1e6+7;

struct Node{
    ll x,y,w;
    Node(ll x = 0,ll y = 0,ll w = 0):x(x),y(y),w(w){}
    bool operator < (const Node&a) const {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
}e[MAXN];

vector<ll> vpx,vpy;
inline ll getX(ll x) {return lower_bound(vpx.begin(),vpx.end(),x)-vpx.begin()+1; }
inline ll getY(ll y) {return lower_bound(vpy.begin(),vpy.end(),y)-vpy.begin()+1; }

ll n,m;

inline void cal(ll i,ll j,ll& u,ll& d) {
    u = e[i].y ,d = e[j].y;
    if (u > d) swap(u,d);
}

#define lson rt<<1
#define rson rt<<1|1

ll mn[5007<<2];
ll mx[5007<<2];
ll add[5007<<2];

inline void PushUp(ll rt){
    mx[rt] = max(mx[lson] , mx[rson]);
    mn[rt] = min(mn[lson] , mn[rson]);
}

inline void Build(ll l,ll r,ll rt){
    if (l == r){
        mx[rt] = 0;
        mn[rt] = 0;
        add[rt] = 0;
        return ;
    }
    ll m = (l+r)>>1;
    Build(l,m,lson);
    Build(m+1,r,rson);
    mx[rt] = 0;
    mn[rt] = 0;
    add[rt] = 0;
}

inline void PushDown(ll rt){
    if (add[rt]){
        mx[lson] += add[rt];
        mx[rson] += add[rt];
        mn[lson] += add[rt];
        mn[rson] += add[rt];

        add[lson] += add[rt];
        add[rson] += add[rt];
        add[rt] = 0;
    }
}

inline void Update(ll L,ll R,ll C,ll l,ll r,ll rt){
    if (L <= l && r <= R){
        mx[rt] += C;
        mn[rt] += C;
        add[rt] += C;
        return ;
    }
    ll m = (l+r)>>1;
    PushDown(rt);
    if (L <= m) Update(L,R,C,l,m,lson);
    if (R >  m) Update(L,R,C,m+1,r,rson);
    PushUp(rt);
}

ll ansMx = 0,ansMn = 0;
inline void QueryMaxz(ll L,ll R,ll l,ll r,ll rt){
    if (L <= l && r <= R){
        ansMx = max(ansMx,mx[rt]);
        return ;
    }
    ll m = (l+r)>>1;
    PushDown(rt);
    if (L <= m) QueryMaxz(L,R,l,m,lson);
    if (R >  m) QueryMaxz(L,R,m+1,r,rson);
}
inline void QueryMin(ll L,ll R,ll l,ll r,ll rt){
    if (R < L) return ;
    if (L <= l && r <= R){
        ansMn = min(ansMn,mn[rt]);
        return;
    }
    ll m = (l+r)>>1;
    PushDown(rt);
    if (L <= m) QueryMin(L,R,l,m,lson);
    if (R >  m) QueryMin(L,R,m+1,r,rson);
    return ;
}

vector<ll> vxx[5007];
bool mark[5007];

void init() {
    vpx.clear();
    vpy.clear();
}

int main()
{
    ll T;
    scanf("%lld",&T);
    while (T --) {
        ll N;
        init();
        scanf("%lld",&N);
        rep(i,1,N) {
            ll x,y,w;
            scanf("%lld %lld %lld",&x,&y,&w);
            e[i] = Node(x,y,w);
            vpx.pb(x);
            vpy.pb(y);
        }
        sort(vpx.begin(),vpx.end()); vpx.erase(unique(vpx.begin(),vpx.end()),vpx.end());
        sort(vpy.begin(),vpy.end()); vpy.erase(unique(vpy.begin(),vpy.end()),vpy.end());
        n = vpx.size();m = vpy.size();
        rep(i,0,n+3) vxx[i].clear();

        rep(i,1,N) {
            e[i].x = getX(e[i].x);
            e[i].y = getY(e[i].y);
        }

        sort(e+1,e+1+N);
        rep(i,1,N) {
            vxx[e[i].x].pb(i);
        }

        ll ans = 0;
        ll u,d;
        rep(i,1,N) {
            Build(1,m,1);
            memset(mark,0,sizeof(bool)*(n+2));
            rep(j,i,N) {
                if (mark[e[j].x] == 0) {
                    mark[e[j].x] = 1;
                    ll now = e[j].x;
                    rep(kk,0,vxx[now].size()-1) {
                        ll id = vxx[now][kk];
                        Update(e[id].y,N,e[id].w,1,m,1);
                    }
                }
                cal(i,j,u,d);
                ansMx = -1e18;ansMn = 1e18;
                if (mx[1] - min(mn[1],0LL) <= ans) continue; //Prune
                QueryMaxz(d,N,1,m,1);
                QueryMin(1,u-1,1,m,1);
                ll resMX = ansMx;
                ll resMN = ansMn;
                resMN = min(resMN,0LL);
                ll nowAns = resMX-resMN;
                ans = max(ans,nowAns);
            }
        }
        printf("%lld\n",ans);
    }
}

Tags: PHP

Posted on Mon, 07 Oct 2019 23:39:40 -0700 by Mutley