当前位置：首页 > news >正文

制作网页创建站点的步骤推广排名

news 2025/7/28 14:31:11

制作网页创建站点的步骤,推广排名,高端企业网站建设好的公司,为什么要做营销型的网站建设2683: 简单题 Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 1268 Solved: 502[Submit][Status][Discuss]Description 你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：命令参数限制内…

2683: 简单题

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1268 Solved: 502
[Submit][Status][Discuss]

Description

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

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x₁ y₁ x₂ y₂	1<=x₁<= x₂<=N 1<=y₁<= y₂<=N	输出x₁ y₁ x₂ y₂这个矩形内的数字和
3	无	终止程序

Input

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

接下来每行一个操作。

Output

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

Sample Input

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

Source

显然这题不能树套树原因自己看数据范围

那我们怎么做？

cdq分治

不过我还没有看懂到底是怎么个做法

反正肯定是这样的：

对时间分治，像归并排序一样考虑[l,mid]对[mid+1,r]的影响（问题1：如何处理影响？）

由于我们读入的时候肯定是x是连续的，所以我们一次可以处理很多询问（问题2：询问如何处理？）

所以我们最后只用维护一下树状数组就可以得到答案（问题3：为什么？）

这里先放上代码明天我去问一下机房的大神得到这三个问题的答案

/*To The End Of The Galaxy*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#define debug(x) cerr<<#x<<"="<<x<<endl
#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{int now=0,ju=1;char c;bool flag=false;while(1){c=getchar();if(c=='-')ju=-1;else if(c>='0'&&c<='9'){now=now*10+c-'0';flag=true;}else if(flag)return now*ju;}
}
inline long long llinit()
{long long now=0,ju=1;char c;bool flag=false;while(1){c=getchar();if(c=='-')ju=-1;else if(c>='0'&&c<='9'){now=now*10+c-'0';flag=true;}else if(flag)return now*ju;}
}
int n,m;
struct node
{int t,x,y,d,id,v;
}query[2000005],tmpq[2000005];
int ans[2000005],s[2000005];
bool operator < (node a,node b)
{if(a.x!=b.x){return a.x<b.x;}else return a.y<b.y;
}
#define lowbit(x) (x&(-x))
void Add(int now,int v)
{for(int i=now;i<=n;i+=lowbit(i)){s[i]+=v;}
}
int Query(int now)
{int sum=0;for(int i=now;i>=1;i-=lowbit(i)){sum+=s[i];}return sum;
}
#define mid ((l+r)>>1)
void solve(int l,int r)
{if(l==r)return;solve(l,mid);solve(mid+1,r);int i=l,j=mid+1,last=0;while(j<=r){while(i<=mid&&query[i].t==2){i++;}while(j<=r&&query[j].t==1){j++;}if(i<=mid&&query[i].x<=query[j].x){Add(query[i].y,query[i].v);last=i;i++;}else if(j<=r)ans[query[j].id]+=Query(query[j].y),j++;}for(int i=l;i<=last;i++){if(query[i].t==1){Add(query[i].y,-query[i].v);}}merge(query+l,query+1+mid,query+1+mid,query+1+r,tmpq+l);for(int i=l;i<=r;i++){query[i]=tmpq[i];}return;
}
bool cmpid(node a,node b)
{return a.id<b.id;
}
int c[2000005],tot=0;
int main()
{n=init();int xl,xr,yl,yr,v,type;while(type=init(),type!=3){if(type==1){xl=init();yl=init();v=init();++m;query[m].x=xl;query[m].y=yl;query[m].v=v;query[m].t=type;query[m].id=m;}else if(type==2){c[++tot]=m;xl=init();yl=init();xr=init();yr=init();++m;query[m].id=m;query[m].x=xr;query[m].y=yr;query[m].t=type;++m;query[m].id=m;query[m].x=xl-1;query[m].y=yl-1;query[m].t=type;++m;query[m].id=m;query[m].x=xl-1;query[m].y=yr;query[m].t=type;++m;query[m].id=m;query[m].x=xr;query[m].y=yl-1;query[m].t=type;}}int p;solve(1,m);for(int i=1;i<=tot;i++){printf("%d\n",ans[c[i]+1]+ans[c[i]+2]-ans[c[i]+3]-ans[c[i]+4]);}return 0;
}
/*
srO xudyh davidlee1999WTK linkct1999 Orz
compiler TDM-GCC 5.9.2
*/