「BZOJ4066」简单题

2015年7月2日8,0053

Description

你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:

命令 参数限制 内容
1 x y A 1<=x,y<=N,A是正整数 将格子x,y里的数字加上A
2 x1 y1 x2 y2 1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和
3 终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。每条命令除第一个数字之外,

均要异或上一次输出的答案last_ans,初始时last_ans=0。

Output

对于每个2操作,输出一个对应的答案。

Sample Input

4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

Sample Output

3
5

HINT

数据规模和约定

1<=N<=500000,操作数不超过200000个,内存限制20M,保证答案在int范围内并且解码之后数据仍合法。

样例解释见OJ2683

新加数据一组,但未重测—-2015.05.24

题解

强制在线就用kdtree来维护T T

常数太丑会T,那就每插入若干次重构整棵树

 

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
OceanEyeBocity出4066的人是sb Recent comment authors
  Subscribe  
提醒
OceanEye

哇……这是某种暴力的思想吗……

Bocity
Bocity

还有这种操作

出4066的人是sb
出4066的人是sb

//求标明题目来源