8677: BZOJ4677:网络运输

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

今天Nick来到了一个大公司(CCF),这个公司掌控了整个城市的运输系统,这个运输系统在各 种运输线的连接下形成了一个网状结构。 当然,任何系统都会有缺陷,这个系统的缺陷在于所有的运输线都会有一定的延时,一共有n 种运输线,相同种类的运输线延时是相同的。 由于每天会有很多的货物需要通过这个网络进行运输,所以管理员小J需要制订每天的运输计 划,当然,他就需要知道某个货物从生产地运送到某个运输站的最短延时。 为了简化问题,假设所有货物的生产地在0号运输站,所有的运输站形成了一个分层结构,第1 层有n个运输站,第2层有n-1个运输站……第n层有1个运输站,小J用(i,j)表示第i层的第 j个运输站,注意i<=j<n,因为第2层没有第1个运输站,第3层没有第1,2个运输站,以此类 推。这个网络的结构比较奇怪。0号运输站通过一条j类型的单向运输线与(1,j)相连;当i>l时, 运输站(i-l,j-l)和运输站(i-1,j)通过两条j类型的单向运输线与运输站(i,j)相连。对于所 有i>=l,货物只能够从第i-l层向第i层运输。 令天有m个货物需要运输,小T想要知道每个货物到达目的地的最短延时,他找到了Nick帮 忙,由于Nick没带电脑,所以这个光荣而艰巨的任务就交给你啦!


输入格式

第1行2个正整数n,m,表示运输线的种类数和今天运输的货物个数。 第2行共n个非负整数,数与数之间用空格隔开,第i个数Pi表示第i种运输线的延时。 第3~m+2行,每行两个正整数xi,Yi,表示第i个货物需要运送到运输站(xi,Yi)。 注意:为了防止离线算法的出现,本题将对输入文件进行加密。假设第i-l组询问的答案为ans, 则第i组实际询问的xi',yi'为给定的xi,yi对ans进行异或操作得到的结果,即,xi'=xi xor ans yi=yi xor ans,实际的询问为xi',yi'。特别地,对于i=1,ans=0。 N,M<=10^5,0<=Pi<=20000,1<=xi'<=yi'<=N


输出格式

共m行,每行一个非负整数,第i行表示第i个货物的最短延时


样例输入

6 4 
2 2 3 4 3 4 
4 5 
15 8 
10 13
11 10

样例输出

9
9
5
//对于第一组样例,第1组询问的答案为12,第二组询问由于15 xor 12=3
8 xor 12=4,所以实际的询问为(3,4),答案为9

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: