主题

主题

 
   

Price List Strike Back

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5808

Problem Description

There are n shops numbered with successive integers from 1 to n in Byteland. Every shop sells only one kind of goods, and the price of the i-th shop's goods is vi. The distance between the i-th shop and Byteasar's home is di.

Every day, Byteasar will purchase some goods. On the i-th day, he will choose an interval [li,ri] and an upper limit ci. Then, he will visit each shop with distance at most ci away from home in [li,ri], buy at most one piece of goods from each shop and go back home. Of course, he can also choose to buy nothing. Back home, Byteasar will calculate the total amount of money he has costed that day and write it down on his account book, denoted as sumi.

However, due to Byteasar's poor math, he may calculate it wrong. 

Please write a program to help Byteasar judge whether each number is sure to be calculated wrong.

Input

The first line of the input contains an integer T (1≤T≤10), denoting the number of test cases.

In each test case, the first line of the input contains two integers n,m (1≤n≤20000,1≤m≤100000), denoting the number of shops and the number of records on Byteasar's account book.

The second line of the input contains n integers v1,v2,...,vn (1≤vi≤100), denoting the price of the i-th shop's goods.

The third line of the input contains n integers d1,d2,...,dn (1≤di≤10^9), denoting the distance between the i-th shop and Byteasar's home.

Each of the next m lines contains four integers li,ri,ci,sumi (1≤li≤ri≤n,1≤ci≤10^9,1≤sumi≤100), denoting a record on Byteasar's account book.

Output

For each test case, print a line with m characters. If the i-th number is sure to be calculated wrong, then the i-th character should be '1'. Otherwise, it should be '0'.

Sample Input

2

3 3

3 3 3

2 4 3

3 3 5 3

3 3 3 1

2 3 1 3

5 4

5 1 2 4 2

1 8 9 2 1

1 5 1 3

4 4 1 5

1 5 3 5

1 3 5 1

Sample Output

011

1101


题目大意:

给出一个长度为n的序列,每个元素有两个参数<v,d>。给出m次询问,每一个询问给出<l,r,c,sum>,表示,在[l..r]区间中选出一些元素组成一个集合,满足:

  1. d[i]<=c

  2. sigma(v[i])=sum


个人解法:

看到vi<=100,想必突破口是在此。

开始想了一个背包F[j]=F[j]|F[j-A[i]]。但是瓶颈在于如何满足限制,以及如何使得每个物品拿过来更新F数组的次数均摊O(1)。

后来想不到……

然后找到了官方题解。我自己来瞎逼逼一下:

首先对这个元素序列分治。对于一个[l,r]的分治。如果一个询问的<l,r>均在[l,mid]或者[mid+1,r],就递归出列。现在我们只需要处理掉跨mid的询问。

预处理出F[i][j],表示在[i,mid]选取元素,可以满足sigma(v)=j 的方案中,d[i] 的最大值(针对于一个方案) 最小(针对于多个方案)是多少。

同样处理出G[i][j],表示在[mid+1,r]选取元素,可以满足sigma(v)=j的方案中,d[i]的最大值 最小是多少。

那么对于一个询问,我们考虑给左边分配v,右边分配sum-v。那么这样分配,得到的集合最小的d=max(F[l][v],G[r][sum-v])。

我们枚举这个v,找到所有分配方法中的最小的d,与查询的c比较即可。


代码如下:

https://code.csdn.net/snippets/2310959


我连二分都没有看到,网上的大佬们怎么就钦定这是整体二分了呢?

 
 
评论