【BZOJ 2402】陶陶的难题II

Qizy Segment Tree, 几何, 凸包, 数据结构, 树链剖分, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2402

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度：$O(n \log^3 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

int n, head[N], nxt[N], to[N];
struct Point{
	double x, y;
	inline Point() {
	}
	inline Point(double a, double b):x(a), y(b) {
	}
	inline bool operator < (const Point &PP) const {
		return x < PP.x || (x == PP.x && y < PP.y);
	}
	inline bool operator == (const Point &PP) const {
		return x == PP.x && y == PP.y;
	}
 	inline Point operator - (const Point &PP) const {
		return Point(x - PP.x, y - PP.y);
	}
	inline double operator * (const Point &PP) {
		return x * PP.y - y * PP.x;
	}
	inline double slope() {
		return y / x;
	}
}d[N][2];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
	int num[N], root, ch[N][2];
	inline void init() {
		build(root, 1, n);	
	}
	inline void update(int l, int r, double a, double *mx) {
		query(root, 1, n, l, r, a, mx);
	}
private:
	inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
		if (L <= l && r <= R) {
			mx[0] = max(mx[0], cal(cvx[w][0], a));
			mx[1] = max(mx[1], cal(cvx[w][1], a));
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				query(ch[w][0], l, mid - 1, L, R, a, mx);
			}
			if (R >= mid) {
				query(ch[w][1], mid, r, L, R, a, mx);
			}
		}
	}
	inline double cal(const vector<Point> &que, double a) {
		int l = 0, r = que.size() - 1, mid, ret = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
				ret = mid; 
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -a * que[ret].x + que[ret].y;
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			cvx[w][0].push_back(d[num[l]][0]);
			cvx[w][1].push_back(d[num[l]][1]);
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			int ls = ch[w][0], rs = ch[w][1];
			cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
			cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
		}
	}
	inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
		vector<Point> cur, ret;
		for (int i = 0; i < (int)c1.size(); i++) {
			cur.push_back(c1[i]);
		}
		for (int i = 0; i < (int)c2.size(); i++) {
			cur.push_back(c2[i]);
		}
		sort(cur.begin(), cur.end());
		cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
		for (int i = 0; i < (int)cur.size(); i++) {
			while ((int)ret.size() > 1) {
				int idx = ret.size() - 1;
				if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
					ret.pop_back();
				} else {
					break;
				}
			}
			ret.push_back(cur[i]);
		}
		return ret;
	}
}SGT;
public:
	inline void init() {
		DFS1(1, 1);
		DFS2(1, 1);
		SGT.init();
	}	
	inline double query(int u, int v) {
		double l = 0, r = INF, ret = 0, mid;
		while (r - l > EPS) {
			mid = (l + r) * 0.5;
			if (judge(u, v, mid)) {
				ret = mid;
				l = mid;
			} else {
				r = mid;
			}
		}	
		return ret;
	}
private:
	inline bool judge(int u, int v, double a) {
		double mx[] = {-INF, -INF};
		while (top[u] != top[v]) {
			if (dep[top[u]] > dep[top[v]]) {
				SGT.update(idx[top[u]], idx[u], a, mx);
				u = fa[top[u]];
			} else {
				SGT.update(idx[top[v]], idx[v], a, mx);
				v = fa[top[v]];
			}
		}
		if (dep[u] > dep[v]) {
			SGT.update(idx[v], idx[u], a, mx);
		} else {
			SGT.update(idx[u], idx[v], a, mx);
		}
		return mx[0] + mx[1] > 0;
	}
	inline void DFS1(int w, int f) {
		fa[w] = f;
		sz[w] = 1;
		dep[w] = dep[f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != f) {
				DFS1(to[i], w);
				sz[w] += sz[to[i]];
				if (sz[to[i]] > sz[hvy[w]]) {
					hvy[w] = to[i];
				}
			}
		}
	}
	inline void DFS2(int w, int t) {
		static int dcnt = 0;
		SGT.num[idx[w] = ++dcnt] = w;
		top[w] = t;
		if (hvy[w]) {
			DFS2(hvy[w], t);
		}
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != fa[w] && to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			}
		}
	}
}HLD;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].y);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].y);
	}
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}

328 thoughts to “【BZOJ 2402】陶陶的难题II”

  1. You really make it seem really easy with your presentation however I find this topic to be actually one thing which I feel
    I’d by no means understand. It sort of feels too complex and extremely vast for me.

    I’m taking a look ahead on your subsequent put up, I will attempt to get the dangle of it!

    Reply

  2. Hey would you mind sharing which blog platform you’re working with?
    I’m planning to start my own blog in the near future but I’m having a tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design and style seems different then most blogs and I’m looking for something unique.
    P.S Sorry for being off-topic but I had to ask!

    Reply

  4. This is very interesting, You are a very skilled blogger. I’ve joined your
    rss feed and look forward to seeking more of your fantastic post.
    Also, I have shared your site in my social networks!

    Reply

  6. Thank you for every other informative website. The place else may
    just I get that kind of information written in such a perfect means?
    I have a venture that I’m simply now running on, and
    I’ve been at the look out for such info.

    Reply

  7. hello there and thank you for your info – I have certainly picked up anything new from right here.
    I did however expertise some technical points using this web site, as I experienced to reload the site a lot of times previous to I could get it to load properly.
    I had been wondering if your web hosting is OK? Not that
    I’m complaining, but sluggish loading instances times will very frequently affect your placement in google and can damage your high quality
    score if advertising and marketing with Adwords.

    Well I’m adding this RSS to my e-mail and could look
    out for much more of your respective fascinating content.
    Ensure that you update this again soon.

    Reply

  8. My programmer is trying to convince me to move to .net from PHP.

    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using WordPress on numerous websites for
    about a year and am worried about switching to another
    platform. I have heard good things about blogengine.net.
    Is there a way I can import all my wordpress posts into
    it? Any kind of help would be greatly appreciated!

    Reply

  12. Excellent article. Keep writing such kind of info on your page.
    Im really impressed by your blog.
    Hello there, You’ve performed an excellent job. I will certainly
    digg it and for my part recommend to my friends. I am confident they’ll be benefited from this web
    site.

    Reply

  13. Nice post. I was checking constantly this blog and I am impressed!

    Extremely helpful info particularly the last part 🙂 I care for such information much.
    I was seeking this certain info for a long time. Thank you
    and best of luck.

    Reply

  16. Hi, i read your blog occasionally and i own a similar one and
    i was just wondering if you get a lot of spam comments?

    If so how do you prevent it, any plugin or anything you can recommend?
    I get so much lately it’s driving me mad so any help is very much appreciated.

    Reply

  17. It’s a shame you don’t have a donate button! I’d without
    a doubt donate to this excellent blog! I guess
    for now i’ll settle for bookmarking and adding your RSS feed
    to my Google account. I look forward to new updates and will share this
    website with my Facebook group. Talk soon!

    Reply

  18. Asking questions are genuinely pleasant thing if you are not
    understanding anything totally, except this article gives
    nice understanding yet. plenty of fish natalielise

    Reply

  20. Hello there I am so thrilled I found your blog page, I really found
    you by accident, while I was looking on Bing for something
    else, Anyhow I am here now and would just like to say thanks a lot for a fantastic post and a all round entertaining blog (I also love the theme/design),
    I don’t have time to read through it all at the minute but I have
    saved it and also added in your RSS feeds, so when I have time I will be back to read more,
    Please do keep up the awesome b.

    Reply

  21. Somebody necessarily help to make seriously posts I’d state.
    That is the first time I frequented your web page and so far?

    I surprised with the research you made to create this actual put up incredible.
    Great activity! pof natalielise

    Reply

  22. Good way of explaining, and good paragraph to take
    data regarding my presentation subject, which i am going to deliver in institution of higher education.

    Reply

  31. Hey there! This is my first comment here so I just wanted to give
    a quick shout out and tell you I really enjoy reading
    your posts. Can you recommend any other blogs/websites/forums that cover the same topics?
    Thank you!

    Reply

  32. Today, while I was at work, my cousin stole my iPad and tested to see if it can survive a twenty five foot drop, just so she can be
    a youtube sensation. My apple ipad is now broken and she has 83 views.
    I know this is completely off topic but I had to share
    it with someone!

    Reply

  33. This is very interesting, You are a very skilled blogger.

    I have joined your feed and look forward to seeking more of your fantastic post.

    Also, I’ve shared your site in my social networks!

    Reply

  35. I’ve been browsing online more than three hours nowadays, yet I by no means discovered any attention-grabbing article like yours.
    It’s pretty price enough for me. In my view, if
    all webmasters and bloggers made just right content as you did, the internet can be much more helpful than ever
    before.

    Reply

  36. You actually make it seem so easy with your presentation but I
    find this topic to be actually something that
    I think I would never understand. It seems too complicated and
    very broad for me. I am looking forward for your next post,
    I’ll try to get the hang of it!

    Reply

  38. Thank you a bunch for sharing this with all of us you actually understand what you are speaking about!
    Bookmarked. Please additionally seek advice from my web site =).
    We could have a link exchange arrangement between us

    Reply

  41. Great weblog right here! Additionally your web site rather a lot up very fast!
    What host are you using? Can I am getting your associate link on your host?

    I want my web site loaded up as fast as yours lol

    Reply

  43. It’s perfect time to make some plans for the future and it is
    time to be happy. I have read this post and if I could I want to suggest you few interesting things or advice.
    Maybe you could write next articles referring to this article.
    I want to read more things about it!

    Reply

  48. Does your blog have a contact page? I’m having trouble locating it but, I’d
    like to shoot you an e-mail. I’ve got some creative ideas for your blog you might be interested in hearing.
    Either way, great site and I look forward to seeing it develop over time.

    Reply

  49. Write more, thats all I have to say. Literally,
    it seems as though you relied on the video to make your
    point. You obviously know what youre talking about, why waste your
    intelligence on just posting videos to your site when you could be giving us
    something enlightening to read?

    Reply

  52. Unquestionably consider that which you stated. Your favourite reason appeared to be at the web the simplest thing to have in mind of.
    I say to you, I definitely get irked whilst folks consider worries that they just don’t understand about.

    You controlled to hit the nail upon the highest and outlined out the entire thing with no need side effect ,
    other folks could take a signal. Will likely be back to get more.
    Thanks

    Reply

  53. I’m not sure exactly why but this weblog is
    loading incredibly slow for me. Is anyone else having this issue or is it a issue on my end?
    I’ll check back later and see if the problem still exists.

    Reply

  66. Have you ever considered about adding a little
    bit more than just your articles? I mean, what you say is valuable and all.
    But imagine if you added some great visuals
    or video clips to give your posts more, “pop”!
    Your content is excellent but with images and video clips,
    this blog could certainly be one of the very best in its niche.
    Terrific blog!

    Reply

  113. Wonderful blog! Do you have any suggestions for aspiring writers?
    I’m planning to start my own blog soon but I’m a little lost on everything.
    Would you recommend starting with a free platform like WordPress or go for a paid option? There
    are so many choices out there that I’m totally confused ..

    Any ideas? Bless you!

    Reply

  127. I just could not leave your site before suggesting that I really enjoyed the usual information a person provide for your visitors?
    Is going to be back often to inspect new posts

    Reply

  137. I think what you posted made a bunch of sense.
    But, think on this, what if you composed a catchier post title?
    I mean, I don’t wish to tell you how to run your website,
    but suppose you added a title to maybe grab people’s attention? I mean 【BZOJ 2402】陶陶的难题II –
    Qizy's Database is a little vanilla.
    You might look at Yahoo’s front page and see how they create article headlines to get viewers to click.

    You might add a video or a picture or two to grab people excited about everything’ve written. Just my opinion,
    it might make your posts a little bit more interesting.

    Reply

  140. I was suggested this blog via my cousin. I am not positive whether this submit is written by him as no one else recognize such unique about my trouble.
    You are amazing! Thank you!

    Reply

  147. I was very pleased to discover this great site. I wanted
    to thank you for your time just for this fantastic
    read!! I definitely appreciated every little bit of it and i also have you
    book marked to look at new things on your blog.

    Reply

  151. I was suggested this web site by my cousin. I am not sure whether this
    post is written by him as nobody else know such
    detailed about my trouble. You are amazing!
    Thanks!

    Reply

  153. I do not even know the way I ended up here, but I assumed
    this publish was great. I don’t know who you’re but
    certainly you are going to a well-known blogger in case you
    aren’t already. Cheers!

    Reply

  161. Hmm is anyone else encountering problems with the
    images on this blog loading? I’m trying to find out if
    its a problem on my end or if it’s the blog.

    Any feedback would be greatly appreciated.

    Reply

  186. I will immediately grasp your rss feed as I can’t in finding your e-mail subscription link or newsletter
    service. Do you have any? Kindly let me recognize in order
    that I may subscribe. Thanks.

    Reply

  211. Someone essentially help to make significantly posts I might state.

    That is the very first time I frequented your web page and to this point?
    I surprised with the research you made to make this actual
    post amazing. Excellent activity!

    Reply

  224. Hmm is anyone else having problems with the pictures on this blog loading?
    I’m trying to figure out if its a problem
    on my end or if it’s the blog. Any responses would
    be greatly appreciated.

    Reply

  228. I’m pretty pleased to discover this page. I wanted to
    thank you for ones time due to this wonderful read!!
    I definitely savored every part of it and i also have you book-marked
    to see new information in your blog.

    Reply

  238. It’s actually a cool and helpful piece of info. I am happy that you just shared
    this useful information with us. Please stay us informed like this.
    Thanks for sharing.

    Reply

  268. You are so interesting! I don’t believe I’ve read through a single thing like this before.
    So nice to discover another person with some original thoughts on this issue.
    Seriously.. thanks for starting this up. This website is one thing that is required on the web, someone with some originality!

    Reply

  269. Good site! I truly love how it is simple on my eyes and the data are well written. I’m wondering how I could be notified whenever a new post has been made. I’ve subscribed to your RSS which must do the trick! Have a nice day!

    Reply

  289. I have been exploring for a little bit for any high quality articles or blog posts on this sort of house . Exploring in Yahoo I eventually stumbled upon this web site. Studying this information So i’m glad to express that I’ve an incredibly good uncanny feeling I found out exactly what I needed. I most indubitably will make certain to do not omit this site and give it a look on a constant basis.|

    Reply

  301. May I just say what a comfort to discover someone who really understands what they’re talking about on the web. You actually understand how to bring an issue to light and make it important. More and more people must check this out and understand this side of your story. I can’t believe you aren’t more popular given that you definitely have the gift.|

    Reply

  306. hi!,I love your writing very so much! percentage we keep up a correspondence extra about your article on AOL? I need an expert on this space to unravel my problem. Maybe that’s you! Taking a look ahead to look you. |

    Reply

  307. whoah this weblog is magnificent i like reading your posts. Keep up the good work! You know, a lot of people are looking round for this information, you could help them greatly. |

    Reply

  312. I do not even know how I ended up here, but I thought this post was great. I don’t know who you are but certainly you’re going to a famous blogger if you are not already 😉 Cheers!|

    Reply

  315. Good post. I learn something new and challenging on websites I stumbleupon every day. It’s always helpful to read content from other authors and practice a little something from their websites. |

    Reply

  322. I really like your blog.. very nice colors & theme. Did you create this website yourself or did you hire someone to do it for you? Plz answer back as I’m looking to create my own blog and would like to find out where u got this from. kudos|

    Reply

  327. We’re a group of volunteers and opening a new scheme in our community. Your website offered us with valuable information to work on. You’ve done a formidable job and our whole community will be thankful to you.|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *