月度归档:2017年10月

BZOJ 4321: queue2(dp)


Description

n 个沙茶,被编号 1~n。排完队之后,每个沙茶希望,自己的相邻的两
人只要无一个人的编号和自己的编号相差为 1(+1 或-1)就行;
现在想知道,存在多少方案满足沙茶们如此不苛刻的条件。
Input

只有一行且为用空格隔开的一个正整数 N,其中 100%的数据满足 1≤N ≤ 1000;
Output

一个非负整数,表示方案数对 7777777 取模。
Sample Input

4
Sample Output

2

样例解释:有两种方案 2 4 1 3 和 3 1 4 2

很神的一个dp题。。
其实貌似oeis一发可以得到一个公式:\(f_n=(n+1)f_{n-1}-(n-2)f_{n-2}-(n-5)f_{n-3}+(n-3)f_{n-4}\),所以其实可以递推求解。
dp做法:
设dp[i][j][0/1]为前i个数有j对相邻数之差小于等于1,且i和i-1是否相邻的方案数。
那么假如第i个人要和第i-1个人相邻,也就是dp[i][j][1]。假如第i-2个人和第i-1个人相邻,那么可以第i个人可以放在第i-1个人的另一侧,也就是从dp[i-1][j-1][1]转移过来,也可以放在第i-1个人和第i-2个人中间,也就是从dp[i-1][j][1]转移过来。
同样假如第i-2个人根本就没有第i-1个人相连,那么就可以放到左右两侧了。这就是dp[i][j][1]的状态转移了。
同理可以分析出来dp[i][j][0]的状态转移。

Codeforces 877F. Ann and Books(莫队)

In Ann’s favorite book shop are as many as n books on math and economics. Books are numbered from 1 to n. Each of them contains non-negative number of problems.

Today there is a sale: any subsegment of a segment from l to r can be bought at a fixed price.

Ann decided that she wants to buy such non-empty subsegment that the sale operates on it and the number of math problems is greater than the number of economics problems exactly by k. Note that k may be positive, negative or zero.

Unfortunately, Ann is not sure on which segment the sale operates, but she has q assumptions. For each of them she wants to know the number of options to buy a subsegment satisfying the condition (because the time she spends on choosing depends on that).

Currently Ann is too busy solving other problems, she asks you for help. For each her assumption determine the number of subsegments of the given segment such that the number of math problems is greaten than the number of economics problems on that subsegment exactly by k.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100 000 - 109 ≤ k ≤ 109) — the number of books and the needed difference between the number of math problems and the number of economics problems.

The second line contains n integers t1, t2, …, tn (1 ≤ ti ≤ 2), where ti is 1 if the i-th book is on math or 2 if the i-th is on economics.

The third line contains n integers a1, a2, …, an (0 ≤ ai ≤ 109), where ai is the number of problems in the i-th book.

The fourth line contains a single integer q (1 ≤ q ≤ 100 000) — the number of assumptions.

Each of the next q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) describing the i-th Ann’s assumption.

Output

Print q lines, in the i-th of them print the number of subsegments for the i-th Ann’s assumption.

Examples
input

output

input

output

Note

In the first sample Ann can buy subsegments [1;1], [2;2], [3;3], [2;4] if they fall into the sales segment, because the number of math problems is greater by 1 on them that the number of economics problems. So we should count for each assumption the number of these subsegments that are subsegments of the given segment.

Segments [1;1] and [2;2] are subsegments of [1;2].

Segments [1;1], [2;2] and [3;3] are subsegments of [1;3].

Segments [1;1], [2;2], [3;3], [2;4] are subsegments of [1;4].

Segment [3;3] is subsegment of [3;4].

 

求一段区间中有多少子段满足和为k。

首先求一遍前缀和,那么问题转换成给一个区间,求多少对数差值为k。把所有值和所有值加减k得到的值离散化一遍。然后跑莫队。

 

BZOJ 2588: Spoj 10628. Count on a tree(主席树)

Description

给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。

Input

第一行两个整数N,M。
第二行有N个整数,其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y),表示点x到点y有一条边。
最后M行每行两个整数(u,v,k),表示一组询问。

Output

M行,表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT

HINT:
N,M<=100000
每个点维护他到根的的路径上的权值线段树,查询的时候我们发现某一段权值区间的个数其实是sum[u]+sum[v]-sum[lca]-sum[lca_father]。所以带着这四个参数一起递归query即可。离散化后lower_bound边界写错了,查了好久。。。