博文

线段树的应用PKU2761(2008-08-22 16:41:00)

摘要:题目链接:
http://acm.pku.cn/JudgeOnline/problem?id=2761

Feed the dogs


DescriptionWind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs every day for Wind. Jiajia loves Wind, but not the dogs, so Jiajia use a special way to feed the dogs. At lunchtime, the dogs will stand on one line, numbered from 1 to n, the leftmost one is 1, the second one is 2, and so on. In each feeding, Jiajia choose an inteval[i,j], select the k-th pretty dog to feed. Of course Jiajia has his own way of deciding the pretty value of each dog. It should be noted that Jiajia do not want to feed any position too much, because it may cause some death of dogs. If so, Wind will be angry and the aftereffect will be serious. Hence any feeding inteval will not contain another completely, though the intervals may intersect with each other.

Your task is to help Jiajia calculate which dog ate the food after each feeding.
InputThe first line cont......

阅读全文(3272) | 评论:1

线段树的应用PKU2985(2008-08-21 13:00:00)

摘要://///////////////////////////////////////
//作品名称:并查集及线段树应用
//作者姓名:满天飞
//作品时间:2008-8-18
//最后修改:2008-8-18
//Q Q 号码:280282813
//版权所有,翻版必究
////////////////////////////////////////
//写得要死终于过了
#include<iostream>
using namespace std;
typedef struct
{
    int lbound;   //左界
    int rbound;   //右界
    int left;   //左子树
    int right;   //右子树
    int ct;    //覆盖次数
}TreeNode;
class SegmentTree
{
    private:
        int nodenum;
        TreeNode* tree;
    public:
        SegmentTree(int);
        virtual ~SegmentTree(){delete[]tree;}
 //构建树
        void build(int, int);
 //插入一个数
 &n......

阅读全文(2774) | 评论:2

线段树的应用PKU3264(2008-08-21 12:31:00)

摘要:#include <iostream>

using namespace std;

typedef struct
{
    int lbound, rbound;
    int left, right;
    int minnum, maxnum;
}TreeNode;

class SegmentTree
{
    public:
        int nodenum;
        TreeNode* tree;
    public:
        SegmentTree ( int );
        void build ( int, int );
        void insert ( int, int );
        void search ( int, int, int);
        virtual ~SegmentTree() {delete[]tree;}
};

//当区间长度小于128时采用顺序查找,以减少递归带来的开销
const int len = 128;
//存储区间权重
int ary[50010];
//最大最小值
int Max;
int Min;

SegmentTree::SegmentTree ( int a )
{
    tree = new TreeNode[2*a+10];
......

阅读全文(2305) | 评论:0