zhangas

字符串匹配函数

Posted on 2022-10-18 Edited on 2023-02-03

头文件<string.h>

1	strcmp(str1,str2);

比较两个字符串,如果两个字符串相等,则返回0.
若str1大于str2(比较第一个不相等的字符的ASCII码)返回一个正数(不一定是1)
若str1小于str2(比较第一个不相等的字符的ASCII码)返回一个负数(不一定是-1)

1	strncmp(str1,str2,n);

比较两个字符串的前n个字符,其他与strcmp同理

1	stricmp(str1,str2);

忽略两个字符串中的大小写,即对大小写不敏感.

向上取整函数

Posted on 2022-10-16 Edited on 2023-02-03

头文件<math.h>

原型

1	double ceil(double x)

调用

1 2	int x; cout<<ceil(x*1.0);

function:返回大于或等于 x 的最小的整数值.
warning:当-1< x < 0 返回值是 -0

图论最短路问题

Posted on 2022-10-13 Edited on 2023-02-03

dijkstra 所有边权都是正数

朴素版 O(n^2)

n:节点个数
m:边的个数

n^2~m (同一数量级)
稠密图: 用邻接矩阵存储d[t][j]表示从t到j的权重

int g[N][N];//权重
int dist[N];//到一号点的距离
bool st[N];//表示哪些点的最短距离已经确定
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;//初始化一号点的距离为0

    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(dist[t]>dist[j||t==-1])){
                t=j;
            }
        }

        st[t]=true;//最短距离已经确定

        for(int j=1;j<=n;j++){
            if(dist[j]>dist[t]+g[t][j]){
                dist[j]=dist[t]+g[t][j];
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));
    //读入的时候 存在重边 和自环
    while(m--){
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);//取长度最短的边
    }
    dijkstra();
    

}

堆优化版O(m*logn)

n~m (同一数量级)
稀疏图: 用邻接表存储

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int h[N],e[N],ne[N],w[N],idx;
int n,m,s;
void add(int a,int b,int c){
    e[idx]=b;
    w[dix]=c;//权重为c
    ne[a]=h[a];
    h[a]=idx++;
}
//拓展 遍历每个节点的出度
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    //PII: distance 序号
    heap.push({0,s});
    dist[s]=0；

    while(heap.size()){
        int t=heap.top();
        heap.pop();

        int distance=t.first,ver=t.second;

        if(st[ver])continue;

        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i],c=w[i];
            if(dist[j]>distance+c){
                dist[j]=distance+c;
                heap.push({dist[j],j});
            }
        }
    }
    
}
int main(){
    //链表初始化
    memset(h,-1,sizeof(-1));
    
    cin>>n>>m>>s;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra();

    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }

    return 0;
}

Bellman_Ford

利用结构体存储 O(n*m)

松弛操作
两层循环

//N为最大节点的个数
int n,m,a,b,w;
int dist[N];//存储到第一节点的距离
int backup[N];
struct Egde{
    int a,int b,int w;
}edges[M];//M为最大边数
void bellman_ford(){
    memset(dist,-1,sizeof(dist));
    for(int i=0;i<k;i++){//题干中最大步数k
        memcpy(backup,dist,sizeof(dist));
        for(int j=1;j<=m;j++){//开始拓展
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);       
        }
    }
}
//主函数
cin>>n>>m>>k;
for(int i=0;i<m;i++){
    cin>>a>>b>>w;
    edges[i]={a,b,w};
}
bellman_ford();
if(dist[n]>0x3f3f3f3f/2){//为什么不是0x3f3f3f3f3f呢
    //存在负权时 (+∞-w)<+∞ dist[]的值可能会被更新为比+∞小一点的数
    cout<<"impossible"<<endl;
}
else{
    cout<<dist[n];
}

目的是实现三角不等式即

1	dist[b]<=dist[a]+w;

SPFA

利用BFS优化松弛操作 O(m)~O(n*m)

const int N=1e5+5;
int e[N],ne[N],w[N],h[N],idx;
int add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa(){
    memset(dist,0x3f,sizeof(dist));
    queue<int>q;
    q.push(1);

    dist[1]=0;
    st[1]=true;

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=ne[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof(h));
    //省略输入...

    if(dist[n]==0x3f3f3f3f){
        cout<<"impossible<<ednl;
    }
    else{
        cout<<dist[n]<<endl;
    }
    return 0;
}

可以用来判断是否存在重环和自环

void spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;
    }
    return false;
}

Floyd

邻接矩阵存储不能出现负权回路 O(n^3)

const int INF=1e9;
int n,m,k;//n是节点的个数 m是边数
int a,b,w;
int g[N][N];
void floyd(){
    for(int k=1;k<=n;k++){//寻找i和j之间的节点 且满足经过k的路径更短
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main(){
    //初始化
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                g[i][j]=0;
            }
            else{
                g[i][j]=INF;
            }
        }
    }
    //输入操作

    while(m--){
        cin>>a>>b>>w;
        //重边保留边权最小的
        g[a][b]=min(g[a][b],w);
    }

    floyd();
    //处理数据
    while(k--){
        cin>>a>>b;
        //出现负权边 可能更新距离后比INF略小
        if(g[a][b]>=INF/2){
            cout<<"impossible"<<endl;
        }
        else{
            cout<<g[a][b]<<endl;
        }
    }
    return 0;
}

数据结构基础

Posted on 2022-10-06 Edited on 2023-02-03

单链表

int e[maxn],ne[maxn];
//e指的是当前节点的值 而ne指的是当前节点的下一个节点的指针
int head,idx;
//head表示头节点的下标 而idx是当前节已经用到了那个点
void init(){
	head=-1;
	idx=0;
}//初始化
void add_to_head(int x){
	e[idx]=x;
	ne[idx]=head;
	head=idx;
	idx++;
}//在头节点插入值为x的节点
void add(int k,int x){
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}//在第k个节点的后面插入值为x的节点
void remove(int k){
	ne[k]=ne[ne[k]];
}//删去第k个节点

双链表

int idx;
int e[maxn],l[maxn],r[maxn];//e是当前节点的值 l是上一节点的指针 r是下一节点的指针
void init(){//初始化
	r[0]=1;//左边界
	l[1]=0;//右边界
	idx=2;//0 1 两个节点已经被使用

}
void add(int k,int x){//在第k个节点后插入值为x的节点
	e[idx]=x;
	r[idx]=r[k];
	l[idx]=k;

	l[r[k]]=idx;
	r[k]=idx;
	idx++;
}//若实现在第k个节点的前面插入 相当于在第k个节点前面的节点后面插入值为x的节点
void del(int k){//删除第k个节点
	r[l[k]]=r[k];
	l[r[k]]=l[k;]
}

调用函数

1 2	add(r[0],x);//在链表的最左端插入值为x的节点 add(l[1],x);//在链表的最右端插入值为x的节点

模拟栈

栈顶插入栈顶弹出判断是否为空查询栈顶元素

int stk[maxn];
int tt=0;
void push(int x){
	stk[++tt]=x;
}
void pop(){
	--tt;
}
bool empty(){
	return tt>0?false:true;
}
int query(){
	return stk[tt];
}

模拟队列

队尾插入队头弹出判断是否为空查询队头元素

int q[maxn];
int tt=-1,hh=0;
void push(int x){
	q[++tt]=x;
}
void pop(){
	hh++;
}
bool empty(){
	return hh>tt?false:true;
}
int query(){
	return q[hh];
}

单调栈

输出左侧第一个比当前数字小的数没有输出-1

const int maxn=1e5+10;
int stk[maxn];
int tt=0;
int n,x;

主函数

for(int i=0;i<n;i++){
		cin>>x;
		while(tt&&stk[tt]>=x){//栈不空且栈顶比不比x小
			tt- -;//栈顶出栈
		}
		if(tt){
			cout<<stk[tt]<<" ";
		}
		else{
			cout<<"-1 ";
		}
		stk[++tt]=x;//x入栈
	}

单调队列

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边且每次向右移动一个位置,分别输出窗口的最大值和最小值.
初始化并读入到a[]中

const int maxn=1e6+10;
int a[maxn],q[maxn];
int tt=-1,hh=0;

for(int i=0;i<n;i++){
    	cin>>a[i];
    }

求最小值

for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]>=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

求最大值

for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]<=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

KMP字符串匹配

初始化并输入

const int N=1e5+10,M=1e6+10;
char p[N],s[M];//p是子串 s是母串 
int ne[N];//next
int n,m;

cin>>n>>p+1>>m>>s+1;

求next[]

ne[1]=0;
for(int i=2,j=0;p[i];i++){
	while(j&&p[i]!=p[j+1]){
		j=ne[j];
	}
	if(p[i]==p[j+1]){
		j++;
	}
	ne[i]=j;
}

KMP算法

for(int i=1,j=0;s[i];i++){
		while(j&&s[i]!=p[j+1]){
			j=ne[j];
		}
		if(s[i]==p[j+1]){
			j++;
		}
		if(j==n){//匹配成功时 i在字符串s上对应串p的末尾 
			cout<<i-n<<" ";//输出的是数组的初位置 不需要+1
			j=ne[j];
		}
	}

Trie字符串统计

I x 向集合中插入一个字符串 x
Q x 询问一个字符串在集合中出现了多少次
初始化

const int maxn=1e5+10;
int son[maxn][26],cnt[maxn];//son[]子节点 cnt[]统计一个串出现了多少次
int idx=0;//表示用到了第几个节点
char op[2];//操作符的读入

插入操作

void insert(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int u=str[i]-'a';
		if(!son[p][u]){//如果该节点不存在
			son[p][u]=++idx;//添加并记录为当前节点
		}
		p=son[p][u];//进入子节点
	}
	cnt[p]++;//计算串的出现次数
}

查找操作

int query(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int u=str[i]-'a';
		if(!son[p][u]){
			return 0;//找不到子节点直接返回0
		}
	}
	return cnt[p];
}

主函数

int n;
cin>>n;
while(n--){
	cin>>op>>str;
	if(op[0]=='I'){
		insert(str);
	}
	if(op[0]=='Q'){
		cout<<query(str)<<endl;
	}
}

并查集

①讲两个集合合并
②询问两个集合是否在一个集合当中

基本原理:每个集合用一棵树来表示.树根的标号就是整个集合的编号.每个节点存储它的父节点.p[x]表示 x 的父节点

//初始化
for(int i=1;i<=n;i++){
	fa[i]=i;//让i的父节点指向i
}
//判断树根
if(p[x]==x){

}
//求x的集合编号
while(p[x]!=x){
	x=p[x];
}
//路程压缩优化
int find(int x){//查询x的属于哪个集合 (返回x的根节点)
	if(p[x]!=x){
		p[x]=find(p[x]);//路径压缩 路径上所有的点都指向树根
	}
	return p[x];
}
//合并两个集合 px是a的集合编号 py是b的集合编号
px=find(x);
py=find(y);
p[px]=py;//让a的根节点的父节点指向b的根节点

模拟堆

① I x 插入一个数 x;
② PM 输出当前集合中的最小值;(输出堆顶 h[1])
③ DM 删除当前集合中的最小值(数据保证此时的最小值唯一);
④ D k 删除第 k 个插入的数;
⑤ C k x 修改第 k 个插入的数,将其变为 x;

预处理

int n;
int siz;//堆的末尾
int m;//记录使用节点个数
int k,x;//输入第k个插入的数字 x存储这个数字
int h[N];//存储节点
int ph[N],hp[N];//ph指向第i个插入的数的下标x 插入序数映射到堆的下标 
//hp指向下标是x的数是第i个插入的数 由堆的下标映射到插入序数

void heap_swap(int a,int b){//堆排列特有的交换方式
	swap(ph[hp[a]],ph[hp[b]]);
	swap(hp[a],hp[b]);
	swap(h[a],h[b]);
}

两个堆的排序函数

void down(int u){//u是节点的序号 寻找三个节点中最小的节点
	int t=u;
	if(u*2<=siz&&h[u*2]>h[t]){//未出界 且满足比子节点大 
		t=u*2;
	}
	if(u*2+1<=siz&&h[u*2+1]>h[t]){
		t=u*2+1;
	}
	if(t!=u){
		heap_swap(u,t);
		down(t);
		
	}
	return;
}
void up(int u){//交换比u大的父节点
	while(u/2>=1&&h[u/2]>h[u]){
		heap_swap(u,u/2);
		u/=2;
	}
	return;
}

操作实现

if(!strcmp(op,"I")){//插入数x
	cin>>x;
	m++;siz++;
	ph[m]=siz;hp[siz]=m;
	h[siz]=x;
	up(siz);
}
else if(!strcmp(op,"DM")){//删除堆顶
	heap_swap(1,siz);
	siz--;
	up(1);
	down(1);
}
else if(!strcmp(op,"D")){//删除第K的插入的数字
	cin>>k;
	k=ph[k];//在交换的过程中ph[k]会变化 预先存储到k上
	heap_swap(k,siz);
	siz--;
	up(k);
	down(k);
}
else if(!strcmp(op,"C")){//将第k个插入的数改变成x
	cin>>k>>x;
	k=ph[k];//同理
	h[k]=x;
	up(k);
	down(k);

}

哈希表

开放寻址法(蹲坑法)

1
2
3

const int null=0x3f3f3f3f;//极大值1061109567与INT_MAX同一数量级 且不会溢出
const int N=2e5+3;
int h[N];

int find(int x){//哈希表特有的搜索函数
	int k=(x%N+N)%N;
	while(h[k]!=null&&h[k]!=x){
		k++;
		if(k==N){//搜到了最后一个槽也是满的 让k回到头节点
			k=0;
		}
	}
	return k;//返回x在哈希表中的位置 若不存在返回null
}

memset(h,0x3f,sizeof(h));
//插入x操作
int k=find(x);
h[k]=x;
//查询x操作
int k=find(x);
if(h[k]!=null){
	puts("Yes");
}
else{
	puts("No");
}

拉链法

1
2
3

const int N=2e5+3;
int h[N];
int e[N],ne[N],idx;

void insert(int x){
	int k=(x%N+N)%N;//负数取模还是负数 会导致数组越界 (+N)%N 避免这一问题
	e[idx]=x;
	ne[idx]=k;
	h[k]=idx;
	idx++;
}
bool find(int x){
	int k=(x%N+N)%N;
	for(int i=h[k];i!=-1;i=ne[i]){
		if(e[k]==x){
			return true;
		}
	}
	return false;
}

memset(h,-1,sizeof(h));//-1表示链表的末尾
if(*op=='I'){
	cin>>x;
	insert(x);
}
else if(*op=='Q'){
	cin>>x;
	if(find(x)){
		puts("Yes");
	}
	else{
		puts("No");
	}
	}
}

字符串哈希

判断一个字符串的两个子区间是否完全相等

typedef unsigned long long ULL;
const int N=1e5+5,Q=133;
char str[N];//存储字符串
ULL p[N];//对Q进行预处理
ULL h[N];
int n,m;//n是字符串的长度 m是操作次数
int l1,r1,l2,r2,

1
2
3

ULL get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];//前缀和计算
}

//预处理
cin>>n>>m;
p[0]=1;
for(int i=1;i<=n;i++){
	p[i]=p[i-1]*Q;
	h[i]=h[i-1]*Q+str[i];
}
while(m--){
	cin>>l1>>r1>>l2>>r2;
	if(get(l1,r1)==get(l2,r2)){
		puts("Yes");
	}
	else{
		puts("No");
	}
}

离散化

Posted on 2022-10-04 Edited on 2023-02-03

利用vector存储映射的一组数据

1 2	typedef pair<int,int> PII; vector<PII> add,query;//add是添加操作 query是查询操作

①先排序再去重

1 2	unique函数的原型: iterator unique(iterator it_1,iterator it_2);

返回值指向去重后容器中不重复序列的最后一个元素的下一元素

1 2	sort(all.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end());

②二分查找

int find(int x){
	int l=0,r=alls.size()-1;
	while(l<r){
		int mid=l+c>>1;
		if(alls[mid]>=x){
			r=mid;
		}
		else{
			l=mid+1;		
		}
	}
	//return l;//映射到0,1,2,3...
	return r+1;//映射到1,2,3,4s... 
        //在计算a的前缀和时 不需要考虑边界问题 s[i]=s[i-1]+a[i];
    
}

遍历add容器和求数组a的前缀和s

for(auto it:add){
		int x=find(it.first);
		a[x]+=it.second;
	} 
for(int i=0;i<=alls.size();i++){
    s[i]=s[i-1]+a[i];
}

遍历query容器输出

for(auto it:query){
    int l=find(it.first);
    int r=find(it,second);
    cout<<s[r]-s[l-1]<<endl;
}

位运算

Posted on 2022-10-03 Edited on 2023-02-03

位运算概览

符号 描述	 运算规则
&	 与	    两个位都为1时，结果才为1
|	 或	    两个位都为0时，结果才为0
^	 异或	两个位相同为0，相异为1
~	 取反	0变1，1变0
<<	 左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	 右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

求n的二进制第k位是多少

1	cout<<(n>>k&1);

这里&1判断n是否为奇数
①n为奇数时,对应的二进制数最低位一定为1,&1的结果就是1.
②n为偶数时,相应的最低位为0,n&1的结果就是0.
这里等价于 (n>>k)%2

统计n的二进制中有多少个1

x&-x
(-x)=~x+1

/*
假设x==42
原码  x  (101010)
反码 ~x  (010101)
补码 ~x+1(010110)
   x&-x  (000010)
*/
int lowbit(int x){
	return x&-x;
} 
int cnt=0;
	while(a){
		a-=lowbit(a);//减去最右侧第一个1到末尾的部分
		cnt++;
	}
	cout<<cnt;

双指针

Posted on 2022-10-03 Edited on 2023-02-03

模板

对于一个序列借助两个指针维护一个区间(i与j有单调关系)

for(int i=0;i<n;i++){
    j=i;
    while(j<n&&check(i,j)){
        j++;
    }
    //每道题的具体逻辑
}

可将暴力两层嵌套循环O(n^2)优化到O(n)

799. 最长连续不重复子序列

找出最长的不包含重复数字的连续子序列[l,c]的长度
input 1 2 2 3 5
output 3

int res=0;
for(int r=0,l=0;r<n;r++){
	cnt[a[r]]++;//计时器的作用
	while(l<r&&s[a[r]]>1){//当出现重复的数字j向前移动一位直到不再重复
		cnt[a[l]]--;
		l++;	
	}
	res=max(res,r-l+1);
}

实现unique函数

vector<int>::iterator unique(vector<int> &a){
	int j=0;
	for(int i=0;i<a.size();i++){
		if(!i||a[i]!=a[i-1]){//第一个或满足不与前一个数相同 
			a[j]=a[i];
			j++;
		}
	}
	return a.begin()+j;//返回值必须是迭代器
}

调用实现去重操作

1 2	sort(a.begin(),a.end()); a.erase(unique(a),a.end());

差分和前缀和

Posted on 2022-10-02 Edited on 2023-02-03

对于一维数组a和数组b
a[i]=b[1]+b[2]+…+b[i];

b[1]=a[1]
b[2]=a[2]-a[1]
··· ···
b[n]=a[n]-a[n-1]
称数组a是数组b的前缀和数组b是数组a的差分

若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)

void insert(int l,int r,int c){//数组b是数组a的差分 b[i]=a[i]-a[i-1] 
	b[l]+=c;
	b[r+1]-=c;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m,n;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(i,i,a[i]);//将数组a转变成它的差分数组b
	}
	while(m--){
		int l,r,c;
		cin>>l>>r>>c;
		insert(l,r,c);
	}
	for(int i=1;i<=n;i++){
		b[i]=b[i]+b[i-1];//将数组b变成数组b的前缀和并输出
		cout<<b[i]<<" ";
	}

对于二维数组a和数组b
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];

b[1][1]=a[1][1]-a[1][0]-a[0][1]+a[0][0]
b[2][2]=a[2][2]-a[2][1]-a[1][2]+a[1][1]
··· ···
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
称数组a是数组b的前缀和数组b是数组a的差分

若将二维数组a的[(x1,y1),(x2,y2)]子矩阵加上c 且时间复杂度为O(n^2)

void insert(int x1,int y1,int x2,int y2,int c){//这样变化后只有含有加上c的子矩阵元素的前缀和才会改变 
	b[x1][y1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=c;
	b[x2+1][y2+1]+=c;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			insert(i,j,i,j,a[i][j]);
			
		}
	}
	while(q--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		
		insert(x1,y1,x2,y2,c);//b[x1][y1]和b[x2+1][y2+1]符号为正 b[x1][y2+1]和b[x2+1][y1]符号为负
	}
	//将数组b化为数组b的前缀和 并输出 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}

加快cin读入速度