SPOJ 海报中的段树超出内存限制？

Question

给定墙的水平截面，以及从坐标 Xi 到 Yi 应用的 N 层涂料，输出可见层的不同数量。

这里是问题linkhttp://www.spoj.com/problems/POSTERS/

方法：我尝试通过 Segment Tree 延迟更新子节点值来解决问题，最新值在延迟更新中替换旧值。这样只有最近的油漆才被应用到水平横截面上。虽然代码在自定义测试用例上运行良好，但它占用大量内存并被在线法官中止。

#include <iostream>
#include <set>
#include <vector>
#define MAX 10000000+100
typedef long long int ll;
using namespace std;
ll Tree[3*MAX],lazy[MAX*2];


void Update(ll s,ll start,ll end,ll left,ll right,ll value)
{
    if(lazy[s]!=0)
    {
        Tree[s]=(lazy[s]*(end-start+1));
        if(start!=end)lazy[2*s+1]=lazy[s],lazy[s*2+2]=lazy[s];
        lazy[s]=0;
    }
    if(start>end||left>end||right<start)return;
    if(start>=left&&end<=right)
    {
        Tree[s] = (value*(end-start+1));
        if(start!=end)
        {
            lazy[2*s+1]=value;
            lazy[2*s+2]=value;
        }
        return ;
    }
    ll mid=(start+end)/2;
    Update(2*s+1,start,mid,left,right,value);
    Update(2*s+2,mid+1,end,left,right,value);
    Tree[s] = Tree[s*2+1]+Tree[2*s+2];
}

ll Read(ll s,ll start,ll end,ll left,ll right)
{
    if(start>end||start>right||end<left)return 0;
    if(lazy[s]!=0)
    {
        Tree[s]=(lazy[s]*(end-start+1));
        if(start!=end)
        {
            lazy[2*s+1]=lazy[s];
            lazy[2*s+2]=lazy[s];
        }
        lazy[s]=0;
    }
    if(start>=left&&end<=right)return Tree[s];
    else return (Read(2*s+1,start,(start+end)/2,left,right)+Read(2*s+2,1+((start+end)/2),end,left,right));

}
int main() {
    // your code goes here
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,z=1,li=-1;
        cin>>n;
        vector<pair<ll,ll> > b;
        for(ll i=0;i<n;i++)
        {
            ll u,v;
            li = max(li,v);
            cin>>u>>v;
            b.push_back(make_pair(u-1,v-1));
        }
        for(auto v: b)
            Update(0,0,li+2,v.first,v.second,z++);
        set<ll> a;

        for(ll i=0;i<li+2;i++)cout<<Read(0,0,li+2,i,i)<<" ",a.insert(Read(0,0,li+2,i,i));
        cout<<endl;
        cout<<a.size()-1<<endl;
    }
    return 0;
}

Answer 1

这是你应该如何做的：

#include <bits/stdc++.h>
#define mx 400005
using namespace std;

int tr[mx], lz[mx];
int t, n, l, r;

void update(int node, int s, int e, int l, int r, int val)
{
    if(lz[node]!=0)
    {
        tr[node]=lz[node];
        if(s!=e)
        {
            lz[node*2]=lz[node];
            lz[node*2+1]=lz[node];
        }
        lz[node]=0;
    }
    if(s>e || r<s || l>e)
        return;
    if(s>=l && e<=r)
    {
        tr[node]=val;
        if(s!=e)
        {
            lz[2*node]=val;
            lz[2*node+1]=val;
        }
        return;
    }
    int m=s+(e-s)/2;
    update(2*node,s,m,l,r,val);
    update(2*node+1,m+1,e,l,r,val);
    tr[node]=val;
    //tr[node]=max(tr[2*node],tr[2*node+1]);
}

int query(int node, int s, int e, int l, int r)
{
    if(r<s || e<l)
        return 0;
    if(lz[node]!=0)
    {
        tr[node]=lz[node];
        if(s!=e)
        {
            lz[node*2]=lz[node];
            lz[node*2+1]=lz[node];
        }
        lz[node]=0;
    }
    if(l<=s && r>=e)
        return tr[node];
    int m=s+(e-s)/2;
    return query(2*node,s,m,l,r)+query(2*node+1,m+1,e,l,r);
}

int main()
{
    //cout << "Hello world!" << endl;
    cin>>t;
    while(t--)
    {
        for(int i=0; i<mx; i++) tr[i]=0;

        cin>>n;

        int lr[n+1][2];

        map<int,bool> mark;
        vector<int> vec;
        //int c=0;
        for(int i=0; i<n; i++)
        {
            cin>>l>>r;
            lr[i][0]=l;
            lr[i][1]=r;
            if(mark[l]==0)
            {
                vec.push_back(l);
                mark[l]=1;
            }
            if(mark[r]==0)
            {
                vec.push_back(r);
                mark[r]=1;
            }
        }

        sort(vec.begin(), vec.end());
        map<int,int> mp;
        int c=1;
        for(int i=0; i<vec.size(); i++)
            mp[vec[i]]=c++;

        for(int i=0; i<n; i++)
        {
            //cout<<mp[lr[i][0]]<<" "<<mp[lr[i][1]]<<"\n";
            update(1,1,vec.size(),mp[lr[i][0]],mp[lr[i][1]],i+1);
        }

        set<int> ans;
        for(int i=1; i<=vec.size(); i++)
        {
            //cout<<query(1,1,vec.size(),i,i)<<" ";
            ans.insert(query(1,1,vec.size(),i,i));
        }
        int k = ans.size();
        if(ans.find(0) != ans.end())
            k--;
        printf("%d\n",k);
    }
    return 0;
}

SPOJ 海报中的段树超出内存限制？

Memory Limit Exceeded with Segment Tree in SPOJ Posters?

memory-management

out-of-memory

segment-tree

range-query