Hdu 1542
线段树离散化以后进行扫描线求面积并。
具体就是用一条平行于$y$轴的直线自左向右地扫过去，然后每次扫到一个整块长方形记录面积。
记录方法是，一个矩形分成左右两个边，左边在线段树中增加，右边在线段树中减少。则当前线段树中的所有大于0的数的个数即为当前长方形的一边。另一边为当前边横坐标减去前一条边的横坐标。
需要离散化。
这里维护的线段树很特殊，只需要查询根节点的和，则在线段树直接维护离散前的数据长度，记录一下区间覆盖次数，大于0则有值，否则没有。注意线段树里面每个点维护的是第几段的覆盖次数。
http://www.cnblogs.com/scau20110726/archive/2013/03/21/2972808.html
Hdu 2087
KMP即可。注意不可重叠，用一个$last$记录上一个不重复匹配成功的位置，之后如果匹配成功，记当前位置为$i$，如果$i-last>模式串长度$，即匹配成功，更新$last$
BZOJ 1593
luogu免权限地址
线段树记录4个信息：
lm: 左端点开始最长连续空区间
rm: 右端点开始最长连续空区间
sum:整个区间最长连续空区间
lazy:lazy标记 (-1:没有标记 0:空区间 1:满区间)
具体请看代码
(BZOJ 2060)[http://www.lydsy.com/JudgeOnline/problem.php?id=2060]
luogu免权限地址
设状态$f[i][0]$为$i$点不访问，$f[i][1]$为$i$点访问
$f[u][1] += f[v][0] $ u点要访问，(u,v)有连边
$f[u][0] += max(f[v][0], f[v][1]) $ u点不访问，(u,v)有连边
like/love = be fond of
例句1：I like the book. = I’ m fond of the book.
例句2：I like to coding. = I’m fond of coding.
be in = be located in
例句：Guangdong is in China. = Guangdong is located in China.
want to do sth. = desire to do sth.
want sth. = desire (for) sth.
例句1：I want to swim. = I desire to swim.
例句2：I want some fish. = I desire (for) some fish.
sb. spend time/money (in) doing sth. = sb. devote time/money to doing sth.
sb. spend time/money on sth. = sb. devote time/money to sth.
例句1：I spent two hours (in) coding. = I devoted two hours to coding.
例句2：I spent two hours on the movie called Your Name. = I devoted two hours to the movie called Your Name.
because of = due to
例句：The sports meeting was put off because of the rain. = The sports meeting was put off due to the rain.
on …(从句的动名词复合结构), (主句) = as soon as (从句), (主句)
例句：As soon as I look for my bag, he comes in. = On my looking for my bag, he comes in.
be adj. = be of n.
例句：The book is useful to me. = The book is of great use to me.
have to do = can’ t but do/ can’ t help but do
例句1：I have to do my homework. = I can’t but do my homework.
例句2：I have to do my homework. = I can’ t help but do my homework.
usually = more often than not(句首)
例句：I usually do my homework first. = More often than not, I do my homework.
most of = the majority of
例句：Most of the students are good. = The majority of the students are good.
help = do sb. a favor to do
例句：Can you help me? = Can you do me a favor?
as a result = as a consequence
例句：As a result, it is a joke. = As a consequence, it is a joke.
variety->diversity
range from … to ..
树链剖分解决树上的修改问题。
将树剖成一条条链，再用线段树、树状数组等维护
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define fo(i, j, k) for (i=(j);i<=(k);i++)
#define fd(i, k, j) for (i=(k);i>=(j);i--)
#define rd(a) scanf("%d", &a)
#define rd2(a, b) scanf("%d%d", &a, &b)
#define rd3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "bzoj1036"
using namespace std;
const int MAXN = 30000 + 5;
int dep[MAXN], son[MAXN], fa[MAXN], siz[MAXN]; //深度，重儿子，父亲，子树大小
int p[MAXN], top[MAXN], pre; //在线段树中的位置，所在重链顶部，线段树当前标号
int n, wi[MAXN];
vector<int> G[MAXN];
void dfs1(int u, int f)//第一次dfs记录值
{
int i;
dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1;
fo (i, 0, G[u].size()-1) {
int v = G[u][i];
if (v!=f) {
dfs1(v, u);
siz[u] += siz[v];
if (son[u]==-1||siz[son[u]]<siz[v]) son[u] = v;
}
}
}
void dfs2(int u, int chain) {//第二次dfs连重儿子成重链
int i;
p[u] = ++pre, top[u] = chain;
if (son[u]!=-1) {
dfs2(son[u], chain);
fo (i, 0, G[u].size()-1) {
int v = G[u][i];
if (v!=son[u]&&v!=fa[u]) dfs2(v, v);
}
}
}
int maxv[MAXN*4], sumv[MAXN*4];
void pushup(int o) {
int lc = o*2, rc = o*2+1;
maxv[o] = max(maxv[lc], maxv[rc]);
sumv[o] = sumv[lc] + sumv[rc];
}
void update(int o, int l, int r, int p, int v) {
int lc = o*2, rc = o*2+1, M = (l+r)/2;
if (l==r) {
sumv[o] = maxv[o] = v; return ;
}
if (p<=M) update(lc, l, M, p, v); else if (M<p) update(rc, M+1, r, p, v);
pushup(o);
}
int getMax(int o, int l, int r, int x, int y) {
int lc = o*2, rc = o*2+1, M = (l+r)/2, ret = -200000000;
if (x<=l&&r<=y) {
return maxv[o];
}
if (x<=M) ret = max(ret, getMax(lc, l, M, x, y));
if (M<y) ret = max(ret, getMax(rc, M+1, r, x, y));
return ret;
}
int getSum(int o, int l, int r, int x, int y) {
int lc = o*2, rc = o*2+1, M = (l+r)/2, ret = 0;
if (x<=l&&r<=y) {
return sumv[o];
}
if (x<=M) ret += getSum(lc, l, M, x, y);
if (M<y) ret += getSum(rc, M+1, r, x, y);
return ret;
}
int findMax(int u, int v)
{
int f1 = top[u], f2 = top[v];
int ret = -200000000;
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
ret = max(ret, getMax(1, 1, n, p[f1], p[u]));
u = fa[f1], f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
return max(ret, getMax(1, 1, n, p[v], p[u]));
}
int findSum(int u, int v)
{
int f1 = top[u], f2 = top[v];
int ret = 0;
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
ret += getSum(1, 1, n, p[f1], p[u]);
u = fa[f1], f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
return ret+getSum(1, 1, n, p[v], p[u]);
}
void init() {
int i; pre = 0;
fo (i, 1, n) dep[i] = fa[i] = siz[i] = p[i] = top[i] = 0, son[i] = -1, G[i].clear();
fo (i, 1, n*4) maxv[i] = -200000000, sumv[i] = 0;
fo (i, 1, n-1) {
int a, b; rd2(a, b);
G[a].push_back(b), G[b].push_back(a);
}
}
void solve() {
int q, i;
dfs1(1, 0);
dfs2(1, 1);
fo (i, 1, n) rd(wi[i]), update(1, 1, n, p[i], wi[i]);
rd(q);
fo (i, 1, q) {
char ch[10]; scanf("%s", ch);
if (ch[0]=='C') {
int u, t; rd2(u, t), update(1, 1, n, p[u], t);
} else if (ch[1]=='M') {
int u, v; rd2(u, v), printf("%d\n", findMax(u, v));
} else if (ch[1]=='S') {
int u, v; rd2(u, v), printf("%d\n", findSum(u, v));
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen(FN2".out","w",stdout);
#endif
while (rd(n)==1) init(), solve();
return 0;
}
见 做题针对题目
1、点权问题
Q：修改某些点的权进行询问。
解：直接树剖进行线段树/树状数组维护
例题：bzoj1036
2、边权问题
Q：修改某些边的权进行询问。
解：树剖后维护点权，每个点的点权为这个点到他父亲之间边权，询问时删除lca的点权即可
例题：poj2763
3、子树问题
Q：修改结点u为根的子树的点权。
解：由树剖的性质可得，树剖后结点u为根的子树在线段树上的区间是连续的一段，那么记录一个左端点和右端点即可(时间戳思想)
例题：bzoj4034