二维差分2
给一个n×m的矩阵a1,1,a1,2,…,a1,m,…,an,m修改q个操作。
一开始所有的位置都是0，每次修改给出5个数字x1,y1,x2,y2,d，令所有ai,j(x1≤i≤x2,y1≤j≤y2)加上d。
在所有操作完成后，找出整个矩阵的值。
输入格式
第一行三个整数n,m,q(1≤n,m≤109,q≤2×103)。
接下来q行，每行五个整数x1,y1,x2,y2,d(1≤x1≤x2≤n,1≤y1≤y2≤m,1≤d≤109)。
输出格式
为防止输出过大，输出操作后矩阵中所有数量的异或和。
样例输入
5 5 3 1 1 2 3 5 2 2 4 3 6 4 3 5 5 10 样例输出
28 思路
二维前缀和 差异。因为只需要计算所有数字的差异或a^a=0,a^0=a.所以只要关心数字出现的次数奇偶性就 这题最关键的还是边界条件的设计。
#include <bits/stdc .h> typedef long double ld; typedef long long ll; #define pb push_back #define mk make_pair #define mt make_tuple #define eb emplace_back #define pob pop_back #define rz resize #define mem(a,b) memset(a,b,sizeof(a)) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend()
#define debug(a) cout<<#a<<"="<<a<<endl;
#define xx first
#define yy second
#define qwe(i,a,b) for(int i=a;i<=b;i++)
#define ewq(i,a,b) for(int i=a;i>=b;i--)
inline ll rr(){
ll f=1,x=0;char ch;do{
ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{
x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const ll mod[2]={
int(1e9 + 7), 10007};
const int base[2]={
29,31};
const int maxn=4e3+6;
int n,m,q;
ll a[maxn][maxn];
std::vector<int> nux,nuy;
array<int,5> op[maxn];
#define all(a) (a).begin(),(a).end()
int main(int argc, char const *argv[]) {
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
scanf("%d%d%d",&n,&m,&q);
int x1,y1,x2,y2,d;
for(int i=1;i<=q;i++) {
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&d);
nux.pb(x1-1),nux.pb(x2);
nuy.pb(y1-1),nuy.pb(y2);
op[i]={
x1,y1,x2,y2,d};
}
sort(all(nux)),sort(all(nuy));
// 对有序的数组去重: [1,2,2,3,3,4,4]->[1,2,3,4,?,?,?]->[1,2,3,4]
nux.erase(unique(all(nux)),nux.end());
nuy.erase(unique(all(nuy)),nuy.end());
for(int i=1;i<=q;i++) {
x1=op[i][0],y1=op[i][1],x2=op[i][2],y2=op[i][3],d=op[i][4];
// 注意下标从0开始
x1=lower_bound(all(nux),x1-1)-nux.begin()+1;
x2=lower_bound(all(nux),x2)-nux.begin();
y1=lower_bound(all(nuy),y1-1)-nuy.begin()+1;
y2=lower_bound(all(nuy),y2)-nuy.begin();
a[x1][y1]+=d;
a[x2+1][y1]-=d;
a[x1][y2+1]-=d;
a[x2+1][y2+1]+=d;
}
int nx=nux.size(),ny=nuy.size();
// for(int i=1;i<=nx;i++)
// for(int j=1;j<=ny;j++)
// a[i][j]+=a[i][j-1];
// for(int i=1;i<=nx;i++)
// for(int j=1;j<=ny;j++)
// a[i][j]+=a[i-1][j];
// 上下写法等价
for(int i=1;i<=nx;i++)
for(int j=1;j<=ny;j++)
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
ll ans=0;
for(int i=1;i<nx;i++) {
for(int j=1;j<ny;j++) {
ll sz=(nux[i]-nux[i-1])*(nuy[j]-nuy[j-1]);
if(sz&1) ans^=a[i][j];
}
}
std::cout << ans << '\n';
return 0;
}
运行结果： 
之前的错误代码
没有x1-1,y1-1。如果不减1，那么区间会连在一起，没有划分清晰。这个实际上是选择了区间的两个端点(画画图也会发现只有这样做才行)。然后是对离散化坐标的操作：x1的位置+1而x2没有，举个例子，比如就一个x上区间[3,5]，那么离散化后就是[0,1]，需要+1然后对x上区间[1,1]做操作。为什么要对[1,1]而不是[0,1]？应该是因为x1-1所在的位置是区间的端点，而能修改的部分是[x1,x2]。
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
#define pb push_back
#define mk make_pair
#define mt make_tuple
#define eb emplace_back
#define pob pop_back
#define rz resize
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define debug(a) cout<<#a<<"="<<a<<endl;
#define xx first
#define yy second
#define qwe(i,a,b) for(int i=a;i<=b;i++)
#define ewq(i,a,b) for(int i=a;i>=b;i--)
inline ll rr(){
ll f=1,x=0;char ch;do{
ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do{
x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;}
using namespace std;
const ll INF=0x3f3f3f3f,inf=0x3f3f3f3f3f3f3f;
const ll mod[2]={
int(1e9 + 7), 10007};
const int base[2]={
29,31};
const int maxn=4e3+6;
int n,m,q;
ll a[maxn][maxn];
std::vector<int> nux,nuy;
array<int,5> op[maxn];
#define all(a) (a).begin(),(a).end()
int main(int argc, char const *argv[]) {
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
scanf("%d%d%d",&n,&m,&q);
int x1,y1,x2,y2,d;
for(int i=1;i<=q;i++) {
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&d);
nux.pb(x1),nux.pb(x2);
nuy.pb(y1-1),nuy.pb(y2);
op[i]={
x1,y1,x2,y2,d}; // 记录操作
}
// 离散化
sort(all(nux)),sort(all(nuy));
nux.erase(unique(all(nux)),nux.end());
nuy.erase(unique(all(nuy)),nuy.end());
for(int i=1;i<=q;i++) {
x1=op[i][0],y1=op[i][1],x2=op[i][2],y2=op[i][3],d=op[i][4];
x1=lower_bound(all(nux),x1)-nux.begin()+1;
x2=lower_bound(all(nux),x2)-nux.begin()+1;
y1=lower_bound(all(nuy),y1)-nuy.begin()+1;
y2=lower_bound(all(nuy),y2)-nuy.begin()+1;
debug(x1)debug(x2)debug(y1)debug(y2)
std::cout << '\n';
a[x1][y1]+=d;
a[x2+1][y1]-=d;
a[x1][y2+1]-=d;
a[x2+1][y2+1]+=d;
}
int nx=nux.size(),ny=nuy.size();
int ans=0;
for(int i=1;i<=nx;i++) {
for(int j=1;j<=ny;j++) {
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for(int i=1;i<=nx;i++) {
for(int j=1;j<=ny;j++) {
std::cout << a[i][j] << ' ';
}
std::cout << '\n';
}
debug(nx)debug(ny)
ll sz;
for(int i=0;i<nx;i++) {
for(int j=0;j<ny;j++) {
if(i==0 && j==0) sz=nux[i]*nuy[j];
else if(i==0) sz=(ll)(nux[i])*(nuy[j]-nuy[j-1]