题解：P1001 A+B Problem - 洛谷保存站

~~我们不能误导新人~~。

## 思路
我们要算出 $a+b$ 等于几我们肯定首先想到的是线段树，但线段树不够新颖，我们可以把它扩展到二维。一维和二位的区别就在于一个线段求和一个是矩阵求和，修改。
在一个矩阵里我们分别把 $(1,1)$  改为 $a$ 和 $(2,2)$  改为 $b$ 求出 $(1,1)$ 到 $(2,2)$ 的和就行了，十分简单。

## code
拿出我今天刚写的二维线段树。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
    int x_1,y_1,x_2,y_2,s;
} t[114][514];
int n,m;
int build(int lx,int ly,int rx,int ry, int idx,int idy) {
    t[idx][idy]={lx,ly,rx,ry,0};
    if (lx == rx&&ly==ry)return 0;
    int midx = (lx + rx) / 2,midy=(ly+ry)/2;
    return t[idx][idy].s = build(lx,ly,midx,midy,idx*2,idy*2)+ build(lx,midy+1,midx,ry,idx*2,idy*2+1)+ build(midx+1,ly,rx,midy,idx*2+1,idy*2)+ build(midx+1,midy+1,rx,ry,idx*2+1,idy*2+1);
}
void mergee(int idx,int idy,int x,int y, int k) {
    if (t[idx][idy].x_1 == t[idx][idy].x_2&&t[idx][idy].y_1 == t[idx][idy].y_2) {
        t[idx][idy].s +=k;
      //  cout<<idx<<" "<<idy<<"||"<<t[idx][idy].x_1<<" "<<t[idx][idy].x_2<<" |\n"; 
        return;
    }
    if(t[idx*2][idy*2].x_2>=x&&t[idx*2][idy*2].y_2>=y){
    	mergee(idx*2,idy*2,x,y,k);
	}else if(t[idx*2+1][idy*2+1].x_1<=x&&t[idx*2+1][idy*2+1].y_1<=y){
		mergee(idx*2+1,idy*2+1,x,y,k);
	}else if(t[idx*2+1][idy*2].x_1<=x&&t[idx*2+1][idy*2+1].y_2>=y){
		mergee(idx*2+1,idy*2,x,y,k);
	}else{
		mergee(idx*2,idy*2+1,x,y,k);
	} 
    t[idx][idy].s = t[idx*2][idy*2].s+t[idx*2+1][idy*2].s+t[idx*2][idy*2+1].s+t[idx*2+1][idy*2+1].s;
}
long long findd(int idx,int idy, int lx,int ly,int rx,int ry) {
    if (t[idx][idy].x_1 == lx&&t[idx][idy].x_2 == rx&&t[idx][idy].y_1 == ly&&t[idx][idy].y_2 == ry) {
        return t[idx][idy].s;
    }
    if(t[idx*2][idy*2].x_2>=rx&&t[idx*2][idy*2].y_2>=ry){
    	return findd(idx*2,idy*2,lx,ly,rx,ry);
	}else if(t[idx*2+1][idy*2+1].x_1<=lx&&t[idx*2+1][idy*2+1].y_1<=ly){
		return findd(idx*2+1,idy*2+1,lx,ly,rx,ry);
	}else if(t[idx*2+1][idy*2].x_1<=lx&&t[idx*2+1][idy*2].y_2>=ry){
		return findd(idx*2+1,idy*2,lx,ly,rx,ry);
	}else if(t[idx*2][idy*2+1].x_2>=rx&&t[idx*2][idy*2+1].y_1<=ly){
		return findd(idx*2,idy*2+1,lx,ly,rx,ry);
	}else if(t[idx*2][idy*2+1].x_2>=rx&&t[idx*2][idy*2+1].y_1>ly){ 
		return findd(idx*2,idy*2,lx,ly,rx,t[idx*2][idy*2].y_2)+findd(idx*2,idy*2+1,lx,t[idx*2][idy*2+1].y_1,rx,ry);
	}else if(t[idx*2+1][idy*2].y_2>=ry&&t[idx*2+1][idy*2].x_1>lx){ 
		return findd(idx*2,idy*2,lx,ly,t[idx*2][idy*2].x_2,ry)+findd(idx*2+1,idy*2,t[idx*2+1][idy*2].x_1,ly,rx,ry);
	}else if(t[idx*2+1][idy*2+1].x_1<=rx&&t[idx*2+1][idy*2+1].y_1>ry){
		return findd(idx*2+1,idy*2,lx,ly,rx,t[idx*2+1][idy*2].y_2)+findd(idx*2+1,idy*2+1,lx,t[idx*2+1][idy*2+1].y_1,rx,ry);
	}else if(t[idx*2+1][idy*2+1].x_1>lx&&t[idx*2+1][idy*2+1].y_1<=ly){
		return findd(idx*2,idy*2+1,lx,ly,t[idx*2][idy*2+1].x_2,ry)+findd(idx*2+1,idy*2+1,t[idx*2+1][idy*2+1].x_1,ly,rx,ry);
	}else{
		return findd(idx*2,idy*2,lx,ly,t[idx*2][idy*2].x_2,t[idx*2][idy*2].y_2)+findd(idx*2+1,idy*2,t[idx*2+1][idy*2].x_1,ly,rx,t[idx*2][idy*2].y_2)+findd(idx*2,idy*2+1,lx,t[idx*2][idy*2+1].y_1,t[idx*2][idy*2+1].x_2,ry)+findd(idx*2+1,idy*2+1,t[idx*2+1][idy*2+1].x_1,t[idx*2+1][idy*2+1].y_1,rx,ry);
	}
}
signed main() {
    int a,b;
    scanf("%lld %lld",&a,&b);
    build(1,1,100,100,1,1);
    mergee(1,1,1,1,a);
    mergee(1,1,100,100,b);
    printf("%lld\n",findd(1,1,1,1,100,100)); 
    return 0;
}
```

正在渲染内容...