一、二维前缀和与差分
一维前缀和:前i项的和
给定长度为n的序列a1,a2...an,则sum[i]=a1+...+ai=sum[i-1]+a[i]
for(i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
一维差分:区间一次修改求和
差分:每个元素与前一个元素的差值
如 A:1 2 3 4 5
则差分为 1 1 1 1 1
若将A[1]+1, A : 1 3 3 4 5
则 1 2 0 1 1 只会改变自己和后一个数
m次操作,每次将区间[L,R]的值加p,最后询问区间[L,R]元素之和。
solution:用一个数组b记录对每一个前缀和总的修改(也可以就在a上操作)。则每次b[L]+=p,b[R]-=p(代表从L及以后的每个元素都要+p,而R及其以后的每个元素-p(所以R之后的元素相当于没操作))
for(i=1; i<=m; i++)
{
int L,R;
cin>>L>>R>>p;
b[L]+=p;
b[R+1]-=p;
}
int add=0;
for(i=1; i<=n; i++)
{
add+=b[i];
a[i]+=a[i-1]+add;
}
//若直接用a表示则为:
for(i=1; i<=m; i++)
{
int L,R;
cin>>L>>R>>p;
a[L]+=p;
a[R+1]-=p;
}
int add=0;
for(i=1; i<=n; i++)
{
add+=a[i];
a[i]+=a[i-1];
}
要求[L,R]的和即a[R]-a[L-1],注意下标从0开始时要特判L=0
二维前缀和
这时操作对象从一维数组变为二维数组,sum[i][j]表示以a[0][0]为左上角,a[i][j]为右下角的矩阵的和,则可推出
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i][j] +a[i][j]//容斥
for(i, 1, n)
for(j, 1, n)
{
scanf("%d", &a[i][j]);
a[i][j] +=a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
二维差分
m次操作,每次将以[x1,y1]为左上角,[x2,y2]为右上角的矩阵的值加p,最后询问区间[L,R]元素之和。
同样地,我们记录下每次操作对区间和的影响。b[i][j]表示以[0][0]为左上角的矩阵,若包含a[i][j]则要+p,所以有4处影响:
b[x1][y1]+=p;
b[x1][y2=1]-=p;(右边区域+、-各一次,抵消使得1号区域不收影响);
b[x2+1][y1]-=p;(下边区域+、-各一次,抵消使得2号区域不收影响);
b[x2+1][y2+1]+=p;(右下边区域+、-各两次,抵消使得3号区域不收影响);
for(i, 1, m)
{
int x1, y1, x2, y2, p;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &p);
a[x1][y1] += p;
a[x1][y2+1] -= p;
a[x2+1][y1] -= p;
a[x2+1][y2+1] += p;
}
//注意这样算的是每一个元素更新之后的值,不是和!要求和的话不仅要加a[i][j]还得加上覆盖矩阵的每一个未更新a[i][j],即累加add
for(i, 1, n)
for(j, 1, n)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
则查询以[x1,y1]为左上角,[x2,y2]为右上角的矩阵的值的和:
ans=a[x2][y2]-a[x2,y2-1]-a[x2-1][y2]+a[x1][y1]
sort+树状数组求大矩阵二位前缀和
A. The beautiful values of the palace
theme:给定一个n*n螺旋矩阵,现从螺旋矩阵中选出m个位置,每个位置的价值由它的元素值的每个数位之和表示,其余位置的元素全部置为0,q次询问,每次询问子矩阵价值。1<=n<=1e6,m,q<=1e5
solution:首先要根据螺旋矩阵的性质推出给定x,y,矩阵中(x,y)的元素值。之后问题转化为求二维矩阵的前缀和。n范围很大,所以借助树状数组辅助。
- 用一个结构体存每个点,包含成员变量flag:标志操作,0表示为将原数插入树状数组,1表示计算询问前缀和。x,y分别记录在矩阵中的横纵坐标。var:记录求子矩阵是时的正负号,即是加上一个前缀和还是减去。
- 将选出的点按y坐标优先,x坐标次之按从小到大排序。
- 排序后边查询边插入(树状数组将横坐标作为下标),按y坐标插入,这样算前缀和时算横坐标<=x的即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(int)1e6+10;
ll bit[N],ans[N];
void Init(int n)
{
for(int i=1;i<=n;++i)
bit[i]=ans[i]=0;
}
/******************树状数组**************/
int lowbit(int x)
{
return x&(-x);
}
void add(int i,ll t)
{
while(i<=N)
{
bit[i]+=t;
i+=lowbit(i);
}
}
ll sum(int i)
{
ll sum=0;
while(i)
{
sum+=bit[i];
i-=lowbit(i);
}
return sum;
}
/******************矩阵**************/
struct node
{
int f;//标志是矩阵原数0插入还是求区间和时的ans+/-,1
int x,y,ans_id;
ll val;//标志求前缀和时是减掉还是加上该矩阵
friend bool operator<(node a,node b)//y,x,f
{
if(a.y==b.y)
{
if(a.x==b.x)
return a.f<b.f;
return a.x<b.x;
}
return a.y<b.y;
}
}p[N];
ll re_val(ll x)
{
ll sum=0;
while(x>0)
{
sum+=x%10;
x/=10;
}
return sum;
}
/************螺旋矩阵*************/
long long index(long long y,long long x,long long n)
{
long long mid=(n+1)/2;
long long p=max(abs(x-mid),abs(y-mid));
long long ans=n*n-(1+p)*p*4;
long long sx=mid+p,sy=mid+p;
if(x==sx&&y==sy)
return ans;
else
{
if(y==sy||x==sx-2*p)
return ans+abs(x-sx)+abs(y-sy);
else
return ans+8*p-abs(x-sx)-abs(y-sy);
}
}
/*************二位前缀和***************/
void solve(int n)
{
for(int i=1;i<=n;++i)
{
if(p[i].f) ans[p[i].ans_id]+=sum(p[i].x)*p[i].val;
else add(p[i].x,p[i].val);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,ask;
scanf("%d%d%d",&n,&m,&ask);
Init(N-3);
int cnt=0;
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
p[++cnt]={0,x,y,-1,re_val(index(x,y,n))};
}
for(int i=1;i<=ask;++i)
{
int xl,yl,xr,yr;
scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
p[++cnt]={1,xl-1,yl-1,i,1};
p[++cnt]={1,xl-1,yr,i,-1};
p[++cnt]={1,xr,yl-1,i,-1};
p[++cnt]={1,xr,yr,i,1};
}
sort(p+1,p+1+cnt);
solve(cnt);
for(int i=1;i<=ask;++i)
printf("%lld\n",ans[i]);
}
return 0;
}
高阶差分
theme:三种操作:
(1):1 x:表示从位置x开始一直到n,每个数+1
(2): 2 x :表示从x到n,依次增加1 2 3 4、、、
(3):3 x:表示从x到n,依次增加1 4 9 16、、、
#include<bits/stdc++.h>
using namespace std;
#define far(i,t,n) for(int i=t;i<n;++i)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int a[100010],b[100010],c[100010];
int mod=1e9+7;
void pre(int p[],int n)
{
p[0]%=mod;
far(i,1,n)
p[i]=(p[i]+p[i-1]%mod)%mod;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
far(i,0,m)
{
int op,pos;
scanf("%d%d",&op,&pos);
--pos;
if(op==1)
a[pos]++;
else if(op==2)
b[pos]++;
else
c[pos]++,c[pos+1]++;
}
pre(a,n);
pre(b,n);pre(b,n);
pre(c,n);pre(c,n);pre(c,n);
far(i,0,n)
printf("%d ",(a[i]+b[i]+c[i])%mod);
printf("\n");
}
}
差分套差分:
theme:两种操作: 1 l r:表示将区间[l,r]的数+1,2 l r :表示将编号[l,r]的操作再执行一遍(保证l,r为已出现的编号)。开始时n个数为0,问最终每个数为多少?
solution:最终我们要算出每个1操作执行了多少次,再对这些区间进行差分,一遍前缀和可得到结果。而对操作次数进行差分的时候,应该逆序进行,从后往前,进行差分,两个差分同步进行。
#include<bits/stdc++.h>
using namespace std;
#define far(i,t,n) for(int i=t;i<n;++i)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
map<int,int>m;
map<int,int>::iterator it;
priority_queue<int>q;
int main()
{
int n;
cin>>n;
far(i,0,n)
{
int x;
scanf("%d",&x);
m[x]++;
}
int ans=0;
for(it=m.begin();it!=m.end();++it)
q.push(it->second);
while(q.size()>=3)
{
++ans;
int x1=q.top()-1;
q.pop();
int x2=q.top()-1;
q.pop();
int x3=q.top()-1;
q.pop();
if(x1)q.push(x1);
if(x2)q.push(x2);
if(x3)q.push(x3);
}
cout<<ans<<"\n";
}
/*
13
1 2 3 3 4 4 4 4 5 5 5 5 5
*/
上一篇: [ACM_HDU_2046]骨牌铺方格
下一篇: HDU 2084 数塔
推荐阅读
-
Monitor 二维差分,前缀和
-
一、二维前缀和与差分
-
【每日一题】和为k的连续子数组——前缀和与滑窗
-
【急】如何快速高效地复制某个网页的一部分?使这一部分的布局与样式和原网站一样_html/css_WEB-ITnose
-
DxOMark发布一加7T Pro评测:总分114分 与P30 Pro仅差2分
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
Tallest Cow POJ - 3263 差分 前缀和
-
POJ - 3263Tallest Cow(前缀和+差分)
-
二维前缀和+差分 HDU6514 Monitor
-
hdu6514 Monitor (二维前缀和*2+二维差分)