TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3349
  • 题目
  • P3349【THOI2015】异或运算
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    小Q是一位勤奋的小学生,他的理想是进入自己心仪的大学学习计算机专业。为了实现这一目标,他从小就开始认真学习信息学竞赛的基础知识。
    今天,小Q学习了异或运算。为了检验自己是否熟练掌握了异或运算,小Q决定给自己出一道题。他随机生成了数列X={x1,x2,...,xn}和数列Y={y1,y2,...,yn}。对于数列X和数列Y中的每一对数(xi,yj),小Q都会计算他们按位异或的结果,并将其填写到矩阵A中的第i行第j列,即Aij=xi xor yj
    得到这个n行m列的矩阵A后,小Q需要检验自己的计算结果是否正确,检验所有异或运算的结果过于繁琐,所以小Q想了一个简便的检验方法。他会在矩阵A中选择一个矩形区域,并找到这个矩形区域中第k大的数,若这个数与标准答案一致,即通过了一次检验。小Q一共要进行p次检验,若p次检验全部通过,他就认为计算的矩阵A是基本正确的。
    但是,小Q现在并没有标准答案。所以,他向你求助,希望你编写一个程序,帮他计算出每次检验的标准答案

    输入格式

    第一行包含两个正整数n,m,分别表示两个数列的长度;
    第二行包含n个非负整数xi,含义见题目描述;
    第三行包含m个非负整数yj,含义见题目描述;
    第四行包含一个正整数p,表示检验的次数;
    随后p行,每行均包含五个正整数,用来描述一次检验;
    其中,第i行包含的前四个正整数为Ui,Di,Li,Ri,分别表示第i次检验区域的上、下、左、右边界(检测的矩形区域包含边界);第五个正整数为Ki,表示此次检验的是该矩形区域中的第Ki大数。

    输出格式

    共p行,每行仅包含一个非负整数,表示此次检验的标准答案。

    样例输入

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

    样例输出

    6
    5
    1

    提示

    1≤Ui≤Di≤1000
    1≤Li≤Ri≤300000
    0≤xi,yi<231
    1≤Ki≤(Di-Ui+1)*(Ri-Li+1)
    1≤P≤500