问题描述:
有一个N × N的棋盘，每个格子内有一个整数，初始全部为 0。维护 3 种操作:
1 x y A 1 ≤ x，y ≤ N，A是正整数，把格子（z，y）内的数字加A；
2 x1 y1 x2 y2 1 ≤ x1 ≤ x2 ≤ N，1 ≤ y1 ≤ y2 ≤ N，输出（x1 ，y1 ）和（x2，y2）确定的矩形内的数字和；
3 终止程序
输入:第1行输入正整数N，接下来每行输入代表一个操作，每条操作命令除了第1个数字外,均要异或上一次输出的答案last ans,初始时 last ans-0。
| 输入：第 1 行输入正整数 N，接下来每行输入代表一个操作，每条操作命令除了第 1 个数字外，均要异或上一次输出的答案last_ans，初始时 last_ans = 0 |
| 输出：对每个 2 操作，输出一个对应的答案 |
| 数据范围：1 ≤ N ≤ 5 × 105，操作数 m 不超过 2 × 105个，内存限制为 20MB，保证答案在 int 型数值范围内并且解码之后数据仍合法。 |
| 输入样例 | 输出样例 |
| 4 1 2 3 3 2 1 1 3 3 1 1 1 1 2 1 1 0 7 3 | 3 5 |
区间查询
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
const double alpha = 0.75; //替罪羊树的不平衡率
#define lc t[u].ls
#define rc t[u].rs
struct Point{
int dim[2],val; //dim[0]即x，dim[1]即y
Point(){}; //手动加上只要参数个数和类型不完全相同，就可以定义任意多个构造函数，以适应不同的初始化场合。
Point(int x,int y,int vall){dim[0]=x,dim[1]=y,val=vall;} //初始化参数
};
Point order[N]; int cnt; //替罪羊树：用于拍平后存数据
struct kd_tree{
int ls,rs;
int mi[2],ma[2]; //mi[i]: 第i维上区间的下界; ma[i]:第i维上区间的上界
int sum; //以该点为根的子树权值之和
int size;
Point p;
}t[N];
int tot,root; //节点编号，根节点
int top,tree_stack[N]; //替罪羊树：回收
int now;
bool cmp(Point a,Point b){return a.dim[now]<b.dim[now];} //第now维数的比较：now为0按照y划分，now为1按照y划分
void update(int u){ //向上更新
for(int i=0;i<2;i++){
t[u].mi[i] = t[u].ma[i] = t[u].p.dim[i]; //dim[i]赋值给mi和ma
if(lc){ //左子树非空
t[u].mi[i] = min(t[u].mi[i],t[lc].mi[i]); //和子树比较更新下界
t[u].ma[i] = max(t[u].ma[i],t[lc].ma[i]); //和子树比较更新上界
}
if(rc){ //与左子树相同
t[u].mi[i] = min(t[u].mi[i],t[rc].mi[i]);
t[u].ma[i] = max(t[u].ma[i],t[rc].ma[i]);
}
}
t[u].sum = t[lc].sum + t[u].p.val+t[rc].sum; //更新当前节点子树的的总权值之和
t[u].size = t[lc].size + t[rc].size+1; //更新节点数量
}
void slap(int u) { //替罪羊树：拍平
if(!u) return;
slap(lc); //这里用中序遍历。其实先序、后序也行
order[++cnt] = t[u].p; //存数据
tree_stack[++top] = u; //回收结点
slap(rc);
}
int build(int l,int r,int d) { //替罪羊树：建树
if(l>r) return 0;
int u;
if(top) u = tree_stack[top--]; //把回收的节点释放
else u = ++tot; //新建节点
int mid=(l+r)>>1;
now = d;
nth_element(order+l, order+mid, order+r+1, cmp); //中值放在mid，左区间小于等于mid，右区间大于等于mid
t[u].p = order[mid];
lc = build(l,mid-1,d^1); //奇偶轮转法
rc = build(mid+1,r,d^1);
update(u);
return u;
}
bool notbalance(int u){ //替罪羊树：判断子树u是否平衡
if(t[lc].size>alpha*t[u].size || t[rc].size>alpha*t[u].size)
return true; //不平衡了
return false; //还是平衡的
}
void Insert(int &u,Point now,int d){
if(!u) { //递归到空节点
if(top) u=tree_stack[top--]; //把回收的节点释放
else u = ++tot; //新建节点
lc = rc = 0,t[u].p = now; //左右儿子为0，二维坐标数据和数据写入p
update(u);
return;
}
if(now.dim[d] <= t[u].p.dim[d]) Insert(lc,now,d^1); //按第d维的坐标比较，将数据插入到左子树或者右子树
else Insert(rc,now,d^1);
update(u);
if(notbalance(u)){ //不平衡
cnt = 0;
slap(u); //拍平
u = build(1,t[u].size,d); //重建
}
}
int query(int u,int x1,int y1,int x2,int y2){
if(!u) return 0; //递归到空节点返回0
int X1=t[u].mi[0], Y1=t[u].mi[1], X2=t[u].ma[0], Y2=t[u].ma[1];
if(x1<=X1 && x2>=X2 && y1<=Y1 && y2>=Y2) return t[u].sum; //子树表示的矩形完全在询问矩形范围内
if(x1>X2 || x2<X1 || y1>Y2 || y2<Y1) return 0; //子树表示的矩形完全在询问矩形范围外
int ans=0;
X1=t[u].p.dim[0], Y1=t[u].p.dim[1], X2=t[u].p.dim[0], Y2=t[u].p.dim[1];
if(x1<=X1 && x2>=X2 && y1<=Y1 && y2>=Y2) ans+=t[u].p.val; //根在询问矩形内
ans += query(lc,x1,y1,x2,y2) + query(rc,x1,y1,x2,y2); //递归左右子树
return ans;
}
int main(){
int n; cin >> n; //测试次数
int ans=0;
while(n){
int opt;scanf("%d",&opt); //操作
if(opt==1){
int x,y,val; scanf("%d%d%d",&x,&y,&val); //x y A
x^=ans,y^=ans,val^=ans; //强制在线规则
Insert(root,Point(x,y,val),0);
}
if(opt==2){
int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1^=ans,y1^=ans,x2^=ans,y2^=ans; //强制在线规则
ans = query(root,x1,y1,x2,y2);
printf("%d\n",ans);
}
if(opt==3) break; //结束程序
}
}
笔记：数据是先插入合适的位置，然后再判断树的不平衡率有没有超出，如果超出就直接将不平衡的部分拍平重建树。查询数据先判断范围然后再累加子树里的sum值，递归到最后就是查询结果。注意的是，如果xy相同的节点不会修改树里原有的节点，而是新建节点，这样其实对于数据的操作更精细，可以还原数据的每部操作。