欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一、二维前缀和与差分

程序员文章站 2024-03-24 16:10:52
...

一维前缀和:前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范围很大,所以借助树状数组辅助。

  1. 用一个结构体存每个点,包含成员变量flag:标志操作,0表示为将原数插入树状数组,1表示计算询问前缀和。x,y分别记录在矩阵中的横纵坐标。var:记录求子矩阵是时的正负号,即是加上一个前缀和还是减去。
  2. 将选出的点按y坐标优先,x坐标次之按从小到大排序。
  3. 排序后边查询边插入(树状数组将横坐标作为下标),按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
*/