天天看點
傳回

【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼

前言

用老師給的模闆前前後後改了四五天...後來改用别人的模闆...

用别人的模闆在洛谷上過了，結果Vjudge上過不了...

多虧某Tao大佬發現計算y值用的int，改成double才終于過了...

看着别人都是幾天前一遍過...我...說多了都是淚...

【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼

題目

萬事開頭難，經營公司更是如此。開始的收益往往是很低的，不過随着時間的增長會慢慢變好。也就是說，對于一個金融顧問 i，他設計的經營方案中，每天的收益都比前一天高，并且均增長一個相同的量 Pi。

由于金融顧問的工作效率不高，**是以在特定的時間，Blue Mary 隻能根據他已經得到的經營方案來估算某一時間的最大收益。**由于 Blue Mary 是很沒有經濟頭腦的，是以他在估算每天的最佳獲益時完全不會考慮之前的情況，而是直接從所有金融顧問的方案中選擇一個在當天獲益最大的方案的當天的獲益值，例如：

有如下兩個金融顧問分别對前四天的收益方案做了設計：

第一天 第二天 第三天 第四天 Pi
顧問 1 1 5 9 13 4
顧問 2 2 5 8 11 3

在第一天，Blue Mary認為最大收益是 2（使用顧問 2 的方案），而在第三天和第四天，他認為最大收益分别是 9 和 13（使用顧問 1 的方案）。而他認為前四天的最大收益是：

2+5+9+13=29

現在你作為 Blue Mary 公司的副總經理，會不時收到金融顧問的設計方案，也需要随時回答 Blue Mary 對某天的“最大收益”的詢問（這裡的“最大收益”是按照 Blue Mary 的計算方法）。**一開始沒有收到任何方案時，你可以認為每天的最大收益值是 0。**下面是一組收到方案和回答詢問的例子：

詢問 2
回答 0
收到方案：0 1 2 3 4 5 ……
詢問 2
回答 1
收到方案：2 2.1 2.2 2.3 2.4 ……
詢問 2
回答 2.1

輸入格式

第一行 ：一個整數 N ，表示方案和詢問的總數。

接下來 N 行，每行開頭一個單詞

Query

或

Project

。

若單詞為

Query

，則後接一個整數 T，表示 Blue Mary 詢問第 T 天的最大收益。

若單詞為

Project

，則後接兩個實數 S，P，表示該種設計方案第一天的收益 S，以及以後每天比上一天多出的收益 P。

輸出格式

對于每一個

Query

，輸出一個整數，表示詢問的答案，并精确到整百元（以百元為機關，例如：該天最大收益為 210 或 290 時，均應該輸出 2）。沒有方案時回答詢問要輸出 0。

輸入輸出樣例

輸入 #1

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000

輸出 #1

0
0
0
0
0

說明/提示

資料範圍：

1≤N≤10^5,1≤T≤50000,0<P<100,∣S∣≤10^5

提示：

本題讀寫資料量可能相當巨大，請選手注意選擇高效的檔案讀寫方式。

題目大意

給定一些直線，求 x 點上 f(x) 的最大值

分析

參考部落格&特别鳴謝：Blue Mary開公司

【關于“李超樹”】

李超樹是用來維護一些直線的，通常來說，我們需要建立一棵線段樹，線段樹上的節點代表一個區間

Ps.這道題的資料是“直線”型，也就是無限長的，不用考慮兩線之間的覆寫關系，個人覺得很好想，

但“線段”型資料的處理方法有所不同，會更複雜一點

對于每一個線段樹上的節點，我們假設其區間為 [L,R] 且中點為 Mid ，則該節點上儲存的直線為其子樹儲存的直線中 f(Mid)最大的一條直線

對于插入某一條直線，考慮遞歸

（“目前直線”為紅色，“原直線”為藍色，“中線”為Mid的位置）

  • 如果目前直線在 Mid處比原直線在 Mid處更優，則需要替換原直線
    • 若目前直線斜率較大，則将原直線遞歸至左子樹，因為原直線隻可能對左子樹造成貢獻
    • 【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼
    • 若原直線斜率較大，則遞歸右子樹
    • 【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼
  • 否則将目前直線遞歸
    • 若目前直線斜率較大，則遞歸右子樹
    • 【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼
    • 若原直線斜率較大，則遞歸左子樹
    • 【李超線段樹-“直線”型模闆】JSOI2008——Blue Mary開公司前言題目題目大意分析代碼WA的玄學“線段型”模闆代碼

這樣每個節點上儲存的直線都是在其子樹中 f(Mid)最大的一個直線

詢問隻需要從根到某個單點取 f(x)的最大值

（良心畫圖有木有qwq）

代碼 

//上個版本改哭了...換了個版本... 
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5,MAXX=5e4;
struct line{double b,k;};
struct node{line p;bool flag;}tree[MAXN<<2];
char s[100];
int n;
double f(line p,int pos)//計算y值 
{
	return p.k*pos+p.b;
}
void update(int i,int l,int r,line p)
{
	if(!tree[i].flag)
	{
		tree[i].flag=true;
		tree[i].p=p;
		return ;
	}
	if(l==r)
	{
		if(f(tree[i].p,l)<f(p,l))
			tree[i].p=p;
		return ;
	}
	int mid=(l+r)>>1;
	if(p.k>tree[i].p.k)
	{
		if(f(p,mid)>f(tree[i].p,mid))
		{
			update(i*2,l,mid,tree[i].p);
			tree[i].p=p;
		}
		else
			update(i*2+1,mid+1,r,p);		
	}
	else
	{
		if(f(p,mid)>f(tree[i].p,mid))
		{
			update(i*2+1,mid+1,r,tree[i].p);
			tree[i].p=p;
		}
		else
			update(i*2,l,mid,p);
	}
}
int query(int i,int l,int r,int pos)
{
	if(!tree[i].flag)
		return 0;
	if(l==r)
		return f(tree[i].p,pos);
	int mid=(l+r)>>1,ans=f(tree[i].p,pos);
	if(pos<=mid)
		ans=max(ans,query(i*2,l,mid,pos));
	else
		ans=max(ans,query(i*2+1,mid+1,r,pos));
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		if(s[0]=='P')
		{
			line tmp;
			scanf("%lf%lf",&tmp.b,&tmp.k);
			tmp.b-=tmp.k;
			update(1,1,MAXX,tmp);
		}
		else
		{
			int tmp;
			scanf("%d",&tmp);
			printf("%d\n",(int)query(1,1,MAXX,tmp)/100);
		}
	}
	return 0;
}

WA的玄學“線段型”模闆代碼 

//超哥樹qwq...
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e5+5,MAXX=5e4+5;
char task[100];
double k,b;
int n,date,cnt;
struct node//完全二叉樹儲存線段樹 
{
	double k,b;//區間最優勢線段的k,b
	int l,r,flag;//flag為該區間已經記錄最優勢線段标記
	node(){}//構造函數 
	node(int _a,int _b,double _c,double _d)
	{
		l=_a,r=_b,k=_c,b=_d;
	} 
	double get_y(const int x) const//傳回線段在x處的y值
	{
		return k*x+b;
	}
	int get_x(const node rhs) const//求兩線段交點的橫坐标 
	{
		return floor((b-rhs.b)/(rhs.k-k));
	}
}tree[MAXN<<2];//空間不爆炸的話開4倍保險 
void build(int i,int l,int r)//建樹 
{
	tree[i].k=tree[i].b=0;
	tree[i].l=l,tree[i].r=r;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}
void add(int i,int l,int r,node p)
{
	if(p.l<=l&&r<=p.r)//被插入線段完全覆寫了目前區間
	{
		//1.目前無優勢線段
		if(!tree[i].flag)
		{
			tree[i]=p;
			tree[i].flag=true;
		}
		//2.如果插入的線段優于區間最優勢線段，更新
		else if(p.get_y(l)>tree[i].get_y(l)&&p.get_y(r)>tree[i].get_y(r))
			tree[i]=p;
		//3.如果插入的線段隻有一端優于最優勢線段，則檢查
		else if(p.get_y(l)>tree[i].get_y(l)||p.get_y(r)>tree[i].get_y(r))
		{
			int mid=(l+r)>>1;
			if(p.get_y(mid)>tree[i].get_y(mid))//看區間中點哪條線段更優 
			{
				node tmp=p;p=tree[i];tree[i]=tmp;
			}
			if(p.get_x(tree[i])<mid)
				add(i*2,l,mid,p);
			else
				add(i*2,mid+1,r,p);
		}
	}
	//未完全覆寫目前區間，則檢查左右區間
	else
	{
		int mid=(l+r)>>1;
		if(p.l<=mid)
			add(i*2,l,mid,p);
		if(p.r>mid)
			add(i*2+1,mid+1,r,p);
	}
}
double query(int i,int l,int r,int x)//查詢區間最優勢線段在x處取值(正常線段樹操作) 
{
	if(l==r)
		return tree[i].get_y(x);
	int mid=(l+r)>>1;
	double ans=tree[i].get_y(x);
	if(x<=mid)
		return max(ans,query(i*2,l,mid,x));
	else
		return max(ans,query(i*2+1,mid+1,r,x));
}
int main()
{
	build(1,1,MAXX);//要緻富，先建樹 
	int n;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",task);
		if(task[0]=='P')
		{
			scanf("%lf%lf",&b,&k);
			tree[++cnt]=node(1,MAXX,k,b-k);
			add(1,1,MAXX,tree[cnt]);
		}
		else
		{
			scanf("%d",&date);
			printf("%d\n",(int)query(1,1,MAXX,date)/100);
		}
	}
	return 0;
}
李超線段樹 直線處理
上一篇: 樹（四）——線索二叉樹一、線索二叉樹基本概念二、線索二叉樹的線索化三、線索二叉樹的周遊四、線索二叉樹周遊的應用
下一篇: ssl1605 二*蘋果樹

繼續閱讀