HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6039 Gear Up 并查集 dfs序 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6039

Gear Up

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:
1. They share a common edge (i.e. they have equal linear velocity).
2. They share a common shaft (i.e. they have equal angular velocity).
It is guaranteed that no pair of gears meets both of the above conditions.
A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.
Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.
sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

Input

There are multiple test cases (about $30$).
For each test case:
The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$
The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$
Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
$a = 1$ means to replace the $x$-th gear with another one of radius $y$.
$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

Output

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

Sample Input

Sample Output

Source

题意

给n个齿轮,每个齿轮都有各自的半径,再给m对齿轮关系,有共边和共轴两种。有q次操作,每次操作会修改某个齿轮的半径,或者是给以某个齿轮一个角速度,问和他连通的齿轮组内角速度最大齿轮的角速度。保证输入的半径或者角速度都是2的整数次方幂。输出的答案取自然对数。保证齿轮关系构成的图没有环。

思路

使用并查集维护共轴的齿轮关系。在每个齿轮连通块中选取一个参考齿轮,将所有的速度和半径对2取对数后,角速度之间差距就从倍数变成了差值,方便计算。从参考齿轮开始,进行dfs,并维护dfs序,优先dfs和这个齿轮共边的齿轮,并计算每个齿轮对于参考齿轮的角速度差,和这个齿轮u共边的齿轮v,他们的角速度都是都是比u的相对角速度快r[u]-r[v],其中r为半径,并且记每个v齿轮在树上的父亲为u。记录下这个dfs序的起止位置为edgeL[u],edgeR[u]。再dfs和这个齿轮共轴的齿轮,这些齿轮的角速度和u相同,并且记这些齿轮的在树上的父亲为不存在。记录这段dfs序列的起止位置为shaftL[u]和shaftR[u]。

询问的时候,先计算出参考齿轮的角速度,再求整个连通块内的最大值即可,区间应该为edgeL[u]~shaftR[u]。

修改分为两种情况。如果这个齿轮在树上没有父亲,那么修改他的半径,只会影响和他共边的齿轮以及共边齿轮连接的齿轮,区间为edgeL[u]+1~edgeR[u]。如果有父亲,则会影响他自己的角速度以及和他共轴齿轮及他们连接的齿轮,区间为edgeL[u]~edgeL[u],shaftL[u]~shaftR[u]。每次修改,对上述区间进行区间累加,维护最大值即可。

 

HDU5957 Query on a graph 基环树 + BFS序列 + 线段树区间维护

http://acm.hdu.edu.cn/showproblem.php?pid=5957

Query on a graph

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

Output

For each QUERY instruction, output a integer in a line.

Sample Input

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1
2 2
3 3
1 1
4 2
5 3
6 5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

Sample Output

21
14
14
28

Source

题意

给一个n个点n条边的无向联通图(n <=10w),边权都是1。定义集合d(u,k)为距离 u点不超过k的点集合。有q次操作或者询问(q<=10w),每次操作是吧d(u,k)集合内的点点权加上d,询问是询问d(u,k)集合内所有的点权和。(0<=d<=2)

思路

对于上诉的图,名字叫做基环树。存在一个环,环上的每一个点都是一个树的根。先将这个环找到。这样问题就从图上的询问简化到了树上。由于是询问或者操作一个范围,可以考虑使用BFS序。维护每一个节点他的儿子和孙子的BFS序的最大值和最小值,同一个树的所有儿子的BFS序一定是连续的,孙子的BFS也一定是连续的,对于这个范围操作,可以考虑使用线段树来进行维护。当k=0的时候,就是单点操作,k=1的时候,先操作u的所有儿子和u点,如果u点在环上,还要单点操作u在环上的周围的两个点。当k=2的时候,情况就比较复杂的。情况1:u点在环上,先操作单点u点和u的儿子以及u的孙子,在环上距离u点为1的两个点x,对x进行单点操作,并对x的儿子进行操作,在环上距离u点为2的两个点y,对y进行单点操作。但是要注意环大小为3的时候和4的时候,操作会重复,需要减去多余操作。情况2:u不在环上,先操作单点u点和u的儿子以及u的孙子,再单点操作u的父亲fa,操作fa的儿子,这时候,u点背重复操作,所以前面一次对u的操作可以不做。这时,如果fa在环上,单点操作fa在环上周围的两个点,否则单点操作fa的父亲。
 

 

 

Codeforces 750E New Year and Old Subsequence 线段树优化区间DP

E. New Year and Old Subsequence

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is  - 1.

Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index ai and ending at the index bi (inclusive).

Input

The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.

The second line contains a string s of length n. Every character is one of digits '0'–'9'.

The i-th of next q lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n), describing a substring in the i-th query.

Output

For each query print the ugliness of the given substring.

Examples

input

output

input

output

input

output

Note

In the first sample:

  • In the first query, ugliness("20166766") = 4 because all four sixes must be removed.
  • In the second query, ugliness("2016676") = 3 because all three sixes must be removed.
  • In the third query, ugliness("0166766") =  - 1 because it's impossible to remove some digits to get a nice string.

In the second sample:

  • In the second query, ugliness("01201666209167") = 2. It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
  • In the third query, ugliness("016662091670") = 1. It's optimal to remove the last digit '6', what gives a nice string "01666209170".

题意

给定一个长度小于10w的数字序列,每次询问一个区间,删除最少的字符后,能包含2017子序列但是不包含2016子序列。

思路

用线段树维护一个dp[i][j]表示从区间的起点,起始位状态i,到区间的终点,状态为j的时候的所需要删除的字符的最少的个数。其中0表示前面没有包含任何关于“2017”的子序列,1表示包含子序列1,2表示包含子序列12,依次类推,特别注意在3、4状态的时候的花费。不可能的状态标记为-1即可。查询的合并下区下区间的DP值即可。

 

 

Codeforces 272C Dima and Staircase 线段树区间覆盖,最值查询

http://codeforces.com/contest/272/problem/C

C. Dima and Staircase
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dima's got a staircase that consists of n stairs. The first stair is at height a1, the second one is at a2, the last one is at an (1 ≤ a1 ≤ a2 ≤ ... ≤ an).

Dima decided to play with the staircase, so he is throwing rectangular boxes at the staircase from above. The i-th box has width wi and height hi. Dima throws each box vertically down on the first wi stairs of the staircase, that is, the box covers stairs with numbers 1, 2, ..., wi. Each thrown box flies vertically down until at least one of the two following events happen:

  • the bottom of the box touches the top of a stair;
  • the bottom of the box touches the top of a box, thrown earlier.

We only consider touching of the horizontal sides of stairs and boxes, at that touching with the corners isn't taken into consideration. Specifically, that implies that a box with width wi cannot touch the stair number wi + 1.

You are given the description of the staircase and the sequence in which Dima threw the boxes at it. For each box, determine how high the bottom of the box after landing will be. Consider a box to fall after the previous one lands.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of stairs in the staircase. The second line contains a non-decreasing sequence, consisting of n integers, a1, a2, ..., an (1 ≤ ai ≤ 109ai ≤ ai + 1).

The next line contains integer m (1 ≤ m ≤ 105) — the number of boxes. Each of the following m lines contains a pair of integers wi, hi (1 ≤ wi ≤ n; 1 ≤ hi ≤ 109) — the size of the i-th thrown box.

The numbers in the lines are separated by spaces.

Output

Print m integers — for each box the height, where the bottom of the box will be after landing. Print the answers for the boxes in the order, in which the boxes are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Sample test(s)
Input

Output

Input

Output

Input

Output

Note

The first sample are shown on the picture.

题意:从左往右,给出每个位置的楼梯高度,依次垂直第在最左边放上高度为hi,宽度为wi的箱子,如上图,箱子不能进行选择,对于每一个箱子,输出这个箱子所在的高度。

思路:对于每一个箱子,只需要查询[1,Wi]内的最大值,箱子会被这个最大值支撑着,所以输出这个最大值,放上这个箱子之后,这个区间内的所有值都会变成上述的那个最大值加上箱子的高度Hi。用线段树维护即可。