标签 - 分治

分治 dp 斜率优化 凸包    2017-02-20 20:35:45    203    1    2
并查集 分治 好题    2016-11-14 13:58:22    318    0    0
 
 
 

题目大意

给定一棵有n个点的树,每条边有承受区间[li;ri]。
m次询问,每次给定一个值speed,求一条最长的链,使得上面所有边的承受区间都包括speed。
n,m≤70000


单调栈 二分 分治    2016-10-19 23:34:03    190    0    5

4237: 稻草人

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 456  Solved: 191
[Submit][Status][Discuss]

Description

JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数

 

Input

第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标

 

Output

输出一行一个正整数,代表遵从启示的田地的个数

 

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3

HINT

 

所有满足要求的田地由下图所示:

 

1<=N<=2*10^5

0<=Xi<=10^9(1<=i<=N)

0<=Yi<=10^9(1<=i<=N)

Xi(1<=i<=N)互不相同。

Yi(1<=i<=N)互不相同。
 

Source

JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ

 

Solution

先将点按y轴排序,然后分治。

首先分治求出上下两块的答案,然后考虑左下角在下半部分,右上角在上半部分的答案

设左下角为(x1,y1),右上角为(x2,y2)

显然对于上部分有:对于所有横坐标在(x1,x2)的点,纵坐标≥y2

显然对于下部分有:对于所有横坐标在(x1,x2)的点,纵坐标≤y1

维护两个单调栈,枚举右上角,在单调栈上二分找符合条件的左下角即可

 

/*{{{*/
#include <bits/stdc++.h>

#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

st
分治 MST 好题    2016-10-14 21:35:16    229    -1    0

2001: [Hnoi2010]City 城市建设

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1094  Solved: 536
[Submit][Status][Discuss]

Description

PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。

Input

文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000),表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行,每行包含两个数k,d,表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。

Output

输出包含Q行,第i行输出得知前i条消息后使城市连通的最小花费总和。

Sample Input

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

Sample Output

14
10
9

HINT

 

【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据,n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。

 

Solution

题意就是维护动态最小生成树。。

考虑分治,但是看起来并不满足分治的条件

我们想办法缩小点集和边集的大小。

对于q个询问里修改的边,我们设这个边集为Q,全集为E,那么对于E-Q中的边,做一遍MST,MST中的边集设为G,那么对于E-Q-G中的边,不论询问怎么改变,这些边都不会在MST中,所以我们可以删除这些边。

这样边集大小变成n - 1 + q,  点集大小仍为n

之后将Q中的边的边权都赋值为-INF,这时做一遍MST,如果E-Q的边在MST中,这时代表就算修改的边