poj 1201 Intervals 线段树+贪心

本文主要是介绍poj 1201 Intervals 线段树+贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1201

题意：给定区间[l,r]和对应的数c，表示该区间内至少有c个点，现问为了使每个区间上均符合条件，整个数轴上

至少要有多少个点。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int n,maxn,minn;
struct Node{
   int f,t,num;
}node2[big+5],node[4*big+500];
bool cmp(Node a,Node b)
{
    return a.t<b.t;
}
int query(int a,int b,int k,int l,int r)
{
    if(r<=a||l>=b)
        return 0;
    else if(a<=l&&r<=b)
        return  node[k].num;
    else if(r>a&&l<b)
    {
        int templ=query(a,b,2*k+1,l,(l+r)>>1);
        int tempr=query(a,b,2*k+2,(l+r)>>1,r);
        return templ+tempr;
    }
}//区间询问模板
void update(int k)
{
    while(k>0)
    {
        int r=(k-1)>>1;
        node[r].num=node[2*r+1].num+node[2*r+2].num;
        k=r;
    }
}//单点更新后，向上更新父节点
void add(int a,int b,int v,int k,int l,int r)
{
   if(query(a,b,0,minn,maxn+1)>=v)
      return ;
   if(r-l==1)
   {
     if(a<=l&&r<=b&&!node[k].num)
      {
       node[k].num=1;
       update(k);
      }
     return ;//一旦扫到单节点，必须退出，否则会re。
   }
   if(r<=a||l>=b)
        return;
   else if(r>a&&l<b)
   {
       add(a,b,v,2*k+2,(l+r)>>1,r);
       add(a,b,v,2*k+1,l,(l+r)>>1);
   }
}//单点更新
void solve()
{
    for(int i=1;i<=n;i++)
        {
            int temp=query(node2[i].f,node2[i].t+1,0,minn,maxn+1);
            if(temp>=node2[i].num)
              continue;
            else
             add(node2[i].f,node2[i].t+1,node2[i].num,0,minn,maxn+1);
        }
    printf("%d\n",node[0].num);
}
void build(int k,int l,int r)
{
    if(r-l==1)
      {
          node[k].num=0;
          return;
      }
    else if(r-l<1) return ;
    build(2*k+1,l,(l+r)>>1);
    build(2*k+2,(l+r)>>1,r);
    node[k].num=0;
}
int main()
{
    while(~scanf("%d",&n))
    {
        maxn=0;minn=big+5;
        for(int i=1;i<=n;i++)
            {
                scanf("%d %d %d",&node2[i].f,&node2[i].t,&node2[i].num);
                if(node2[i].t>maxn)
                    maxn=node2[i].t;
                if(node2[i].f<minn)
                    minn=node2[i].f;
            }
        build(0,minn,maxn+1);
        sort(node2+1,node2+n+1,cmp);
        solve();
    }
    return 0;
}

易错点：1.单点更新，不需要使用懒惰标记，（虽然感觉懒惰标记可以提高效率），

2.sort函数 bool cmp ( Node a , Node b )

{
    return a.t<b.t;
}

中间不能添加等于号，否则传如同一个参数时，会因为相等而出现优先级自己小于自己的情况，

re代码：

   #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int n,maxn,minn;
struct Node{
   int f,t,num;
}node2[big+5],node[4*big+5];
bool cmp(Node a,Node b)
{
    return a.t<=b.t;
}
int query(int a,int b,int k,int l,int r)
{
    if(r<=a||l>=b)
        return 0;
    else if(a<=l&&r<=b)
        return  node[k].num;
    else if(r>a&&l<b)
    {
        int templ=query(a,b,2*k+1,l,(l+r)>>1);
        int tempr=query(a,b,2*k+2,(l+r)>>1,r);
        return templ+tempr;
    }
}
void update(int k)
{
    while(k>0)
    {
        int r=(k-1)>>1;
        node[r].num=node[2*r+1].num+node[2*r+2].num;
        k=r;
    }
}
void add(int a,int b,int v,int k,int l,int r)
{
   if(query(a,b,0,minn,maxn+1)>=v)
      return ;
   if(a<=l&&r<=b)
     if(r-l==1&&!node[k].num)
      {
       node[k].num=1;
       update(k);
       return ;
      }
   if(r<=a||l>=b)
        return;
   else if(r>a&&l<b)
   {
       add(a,b,v,2*k+2,(l+r)>>1,r);
       if(query(a,b,0,minn,maxn+1)>=v)
            return ;
       add(a,b,v,2*k+1,l,(l+r)>>1);
   }
}
void solve()
{
    for(int i=1;i<=n;i++)
        {
            int temp=query(node2[i].f,node2[i].t+1,0,minn,maxn+1);
            if(temp>=node2[i].num)
              continue;
            else
             add(node2[i].f,node2[i].t+1,node2[i].num,0,minn,maxn+1);
        }
    printf("%d\n",node[0].num);
}
void build(int k,int l,int r)
{
    if(r-l==1)
      {
          node[k].num=0;
          return;
      }
    build(2*k+1,l,(l+r)>>1);
    build(2*k+2,(l+r)>>1,r);
    node[k].num=0;
}
int main()
{
    while(~scanf("%d",&n))
    {
        maxn=0;minn=big+5;
        for(int i=1;i<=n;i++)
            {
                scanf("%d %d %d",&node2[i].f,&node2[i].t,&node2[i].num);
                if(node2[i].t>maxn)
                    maxn=node2[i].t;
                if(node2[i].f<minn)
                    minn=node2[i].f;
            }
        build(0,minn,maxn+1);
        sort(node2+1,node2+n+1,cmp);
        solve();
    }
    return 0;
}