HDU 1556---ツリー配列|セグメントツリー|*

n,n行の直後,各行a,bを入力する
n個の気球,a,bはa番目からb番目の気球に1回の色を塗り,各球の最終的な何回かの色を出力する
暴力タイムアウト、データ構造の最適化
1.ツリー配列

#include
#include
#include
#include
#include
#include
#define F(i,a,b) for (int i=a;i#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=10010,MAX=100100;

int n,c[MAX];

int lowbit(int x) {
    //  2^k
    return x&-x;
}

void update(int x,int val)
{
    //    ，      x        
    while(x<=n) {
        c[x]+=val;
        x+=lowbit(x);
    }
}

int Sum(int x)
{
    //    
    int sum=0;
    while(x>0) {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    while(~scanf("%d",&n),n) {
        mes(c,0);
        int a,b;
        FF(i,1,n) {
            scanf("%d%d",&a,&b);
            update(a,1);
            update(b+1,-1);
        }
        F(i,1,n) printf("%d ",Sum(i));
        printf("%d
",Sum(n));
    }

    return 0;
}

 
2.線分ツリー

#include
#include
#include<string>
#include
#include
#define Lson left,mid,n<<1
#define Rson mid+1,right,n<<1|1
const int MAX=100001;
const int Max=100000<<2;
int s[Max];
int m;
using namespace std;
typedef struct Node
{
    int left;
    int right;
    int value;
};
Node node[Max];
void build_tree(int left,int right,int n)
{
    node[n].left=left;
    node[n].right=right;
    node[n].value=0;
    if(node[n].left==node[n].right)
    return;
    int mid=(node[n].left+node[n].right)>>1;
    build_tree(Lson);
    build_tree(Rson);
}
void query(int left,int right,int n)
{
    if(node[n].left>=left&&node[n].right<=right)///        ，     ，                
    {
        node[n].value+=1;
        return;
    }
    int mid=(node[n].left+node[n].right)>>1;
    if(right<=mid)
    query(left,right,n<<1);
    else if(left>mid)
    query(left,right,n<<1|1);
    else
    {
        query(Lson);
        query(Rson);
    }
}
void sum(int n)
{
    if(node[n].left==node[n].right)
    {
        s[m]=node[n].value;
        m+=1;
        return;
    }
    node[n<<1].value+=node[n].value;
    node[n<<1|1].value+=node[n].value;
    sum(n<<1);
    sum(n<<1|1);
}
int main()
{
    int n,i,j,a,b;
    while(scanf("%d",&n)&&n)
    {
        build_tree(1,n,1);
        for(i=0;i)
        {
            scanf("%d%d",&a,&b);
            query(a,b,1);
        }
        m=0;
        sum(1);
        for(i=0;i)
        {
            if(i==m-1)
            printf("%d
",s[i]);
            else
            printf("%d ",s[i]);
        }
    }
    return 0;
}

 
3.奇技淫巧
この問題discussから見る
各バルーンには2つのアトリビュートがあります
起点となる回数st
終点となる回数ed
共有変数sum_st現在の点に記録されたすべての染色開始点数と
次の点を行う前に、この点を染色の終点とする回数を減算します.

#include 
#include 
#include 
#include 
using namespace std;
#define maxn 100000+5

struct st_ed
{
    int st;
    int ed;
}p[maxn];

int N;

int main()
{
#ifndef ONLINE_JUDGE
   // freopen("in","r",stdin);
#endif
    int a,b;
    while(scanf("%d",&N) && N)
    {
        memset(p,0,sizeof(p));
        for(int i = 1; i <= N; i++)
        {
            scanf("%d%d",&a,&b);
            p[a].st++;
            p[b].ed++;
        }
        int sum_st = 0, sum_ed = 0;
        for(int i = 1; i <= N; i++)
        {
            if(i!=1)
                printf(" ");
            sum_st += p[i].st;
            printf("%d",sum_st);
            sum_st -= p[i].ed;
        }
        printf("
");
    }
}

同理
配列離散化?

#include "stdio.h"
int main()
{
    int j,n,i,a,m,b;
    while(scanf("%d",&n),n)
    {
        int c[100001]={0};
        j=n;
        m=0;
        while(j--)
        {
            scanf("%d %d",&a,&b);
            c[a]++;
            c[b+1]--;
        }
        for(i=1;i)
        {
            m+=c[i];
            printf("%d ",m);
        }
        printf("%d
",m+c[n]);
    }
    return 0;
}

 
転載先:https://www.cnblogs.com/kimsimple/p/6864081.html