P2086 题解

WaTleZero_pt · 2023-01-01 22:48:46 · 题解

~~作为一个初一蒟蒻居然敢写黑题题解，真是太勇了~~

题目分析

首先，我们从 N \times M \leq 5 \times 10^{5},T \leq 10^{5} 不难看出，这就是一个二维线段树的题目。这里我选用的是四分树来实现二维线段树。

本题最烦的一点是，我们不可能使用线段树直接实现区间修改加和区间查询 \gcd。因为 \gcd 的性质 \gcd(a,b)=\gcd(a,b-a)，所以本题我们可以借助二维差分来帮助我们实现这个操作。

初始化

那我们应该如何初始化这个二维线段树呢？本题查询时的一个特性为我们提供了帮助，那就是查询时一定包含坐标 (X,Y) 的位置。所以我们可以以 (X,Y) 为二维差分数组的中心，然后依次对左上角、右上角、左下角和右下角的区域做一遍二维差分数组即可。如图（1）所示。

\texttt{图（1）}

修改

现在最棘手的问题就是线段树的修改了。通过差分我们已经把线段树的区间修改改为单点修改，但问题是我们的二维差分数组是以坐标 (X,Y) 为中心进行差分的，所以我们在修改时要进行分类讨论。我们可以分为以下几种情况：

查询时包含坐标 (X,Y)，需要修改 9 个单点。（即查询的范围覆盖了左上，右上，左下和右下四片区域）
查询时包含 X 行或 Y 列，需要修改 6 个单点。（即查询的范围覆盖了如上描述的区域中的两个）
其他情况，需要修改 4 个单点。（即查询的范围仅覆盖了如上描述的区域中的一个）

查询

查询时我们只需要直接一个区间查询 \gcd 即可，没什么好说的。

AC CODE

代码对于一道 NOI 的题目来说算是正常的吧。120 行左右。

#include<stdio.h>
#include<cstring>
using namespace std;
typedef long long ll;
ll Abs(ll a){return a>=0?a:-a;}
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):Abs(a);
}
const int MAXA=2000010,MAXB=8000010;
int n,m;
#define pt(x,y) (x-1)*m+y
class Double_Segment_Tree{
    public:
    ll a[MAXB]; int clls[MAXB],clrs[MAXB],crls[MAXB],crrs[MAXB],cnt;
    Double_Segment_Tree(){
        memset(a,0,sizeof(a)); memset(clls,0,sizeof(clls)); cnt=1;
        memset(clrs,0,sizeof(clrs)); memset(crls,0,sizeof(crls)); memset(crrs,0,sizeof(crrs));
    } 
    void Build(int lx,int ly,int rx,int ry,int u,ll *p){
        if(lx==rx&&ly==ry){
            a[u]=p[pt(lx,ly)];
            return;
        }
        int mid1=(lx+rx)/2,mid2=(ly+ry)/2;
        a[u]=0;
        Build(lx,ly,mid1,mid2,clls[u]=++cnt,p),a[u]=gcd(a[u],a[clls[u]]);
        if(mid1+1<=rx) Build(mid1+1,ly,rx,mid2,clrs[u]=++cnt,p),a[u]=gcd(a[u],a[clrs[u]]);
        if(mid2+1<=ry) Build(lx,mid2+1,mid1,ry,crls[u]=++cnt,p),a[u]=gcd(a[u],a[crls[u]]);
        if(mid1+1<=rx&&mid2+1<=ry) Build(mid1+1,mid2+1,rx,ry,crrs[u]=++cnt,p),a[u]=gcd(a[u],a[crrs[u]]);
    }
    void Update(int lx,int ly,int rx,int ry,int u,int chidx,int chidy,ll val){
        if(lx==rx&&ly==ry){
            a[u]+=val;
            return;
        }
        int mid1=(lx+rx)/2,mid2=(ly+ry)/2;
        if(chidx<=mid1&&chidy<=mid2) Update(lx,ly,mid1,mid2,clls[u],chidx,chidy,val);
        if(mid1+1<=rx) if(chidx>mid1&&chidy<=mid2) Update(mid1+1,ly,rx,mid2,clrs[u],chidx,chidy,val);
        if(mid2+1<=ry) if(chidx<=mid1&&chidy>mid2) Update(lx,mid2+1,mid1,ry,crls[u],chidx,chidy,val);
        if(mid1+1<=rx&&mid2+1<=ry) if(chidx>mid1&&chidy>mid2) Update(mid1+1,mid2+1,rx,ry,crrs[u],chidx,chidy,val);
        a[u]=gcd(a[clls[u]],gcd(a[clrs[u]],gcd(a[crls[u]],a[crrs[u]])));
    }
    ll Query(int lx,int ly,int rx,int ry,int u,int chlx,int chly,int chrx,int chry){
        if(lx>=chlx&&ly>=chly&&rx<=chrx&&ry<=chry){
            return a[u];
        }
        ll res=0;
        int mid1=(lx+rx)/2,mid2=(ly+ry)/2;
        if(chlx<=mid1&&chly<=mid2) res=gcd(res,Query(lx,ly,mid1,mid2,clls[u],chlx,chly,chrx,chry));
        if(mid1+1<=rx) if(chrx>mid1&&chly<=mid2) res=gcd(res,Query(mid1+1,ly,rx,mid2,clrs[u],chlx,chly,chrx,chry));
        if(mid2+1<=ry) if(chlx<=mid1&&chry>mid2) res=gcd(res,Query(lx,mid2+1,mid1,ry,crls[u],chlx,chly,chrx,chry));
        if(mid1+1<=rx&&mid2+1<=ry) if(chrx>mid1&&chry>mid2) res=gcd(res,Query(mid1+1,mid2+1,rx,ry,crrs[u],chlx,chly,chrx,chry));
        return res;
    }
}seg;
ll S[MAXA];
int pl[5][4]={{0,0,0,0},{1,2,6,7},{4,5,9,10},{16,17,21,22},{19,20,24,25}};
bool flag[26];
int stx,sty,t,op,a,b,c,d;ll f;
int xpro(int val){
    if(val==1) return a-1;
    if(val==2) return c;
    if(val==3) return stx;
    if(val==4) return a;
    if(val==5) return c+1;
}
int ypro(int val){
    if(val==1) return b-1;
    if(val==2) return d;
    if(val==3) return sty;
    if(val==4) return b;
    if(val==5) return d+1;
}
int jz[26]={0,1,-1,-1,-1,1,-1,1,1,1,-1,-1,1,1,1,-1,-1,1,1,1,-1,1,-1,-1,-1,1};
int main(){
    scanf("%d%d%d%d",&n,&m,&stx,&sty);
    scanf("%d",&t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&S[pt(i,j)]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>sty;j--)
            S[pt(i,j)]-=S[pt(i,j-1)];
    for(int i=1;i<=n;i++)
        for(int j=1;j<sty;j++)
            S[pt(i,j)]-=S[pt(i,j+1)];
    for(int i=1;i<=m;i++)
        for(int j=n;j>stx;j--)
            S[pt(j,i)]-=S[pt(j-1,i)];
    for(int i=1;i<=m;i++)
        for(int j=1;j<stx;j++)
            S[pt(j,i)]-=S[pt(j+1,i)];
    seg.Build(1,1,n,m,1,S);
    while(t--){
        scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);
        if(op){//修改部分不想写一大堆if嵌套，所以压缩了亿下
            scanf("%lld",&f);
            memset(flag,0,sizeof(flag));
            int ssum=0;
            if(a<=stx&&b<=sty) for(int i=0;i<4;i++) flag[pl[1][i]]=1,ssum++;
            if(a<=stx&&d>=sty) for(int i=0;i<4;i++) flag[pl[2][i]]=1,ssum++;
            if(c>=stx&&b<=sty) for(int i=0;i<4;i++) flag[pl[3][i]]=1,ssum++;
            if(c>=stx&&d>=sty) for(int i=0;i<4;i++) flag[pl[4][i]]=1,ssum++;
            if(flag[2]&&flag[4]) flag[2]=flag[4]=0,flag[3]=1;
            if(flag[6]&&flag[16]) flag[6]=flag[16]=0,flag[11]=1;
            if(flag[10]&&flag[20]) flag[10]=flag[20]=0,flag[15]=1;
            if(flag[22]&&flag[24]) flag[22]=flag[24]=0,flag[23]=1;
            if(flag[7]&&flag[9]) flag[7]=flag[9]=0,flag[8]=1;
            if(flag[7]&&flag[17]) flag[7]=flag[17]=0,flag[12]=1;
            if(flag[17]&&flag[19]) flag[17]=flag[19]=0,flag[18]=1;
            if(flag[9]&&flag[19]) flag[9]=flag[19]=0,flag[14]=1;
            if(flag[8]&&flag[18]) flag[8]=flag[18]=0,flag[13]=1;
            for(int i=1;i<=25;i++){
                if(!flag[i]) continue;
                if(xpro((i-1)/5+1)>=1&&xpro((i-1)/5+1)<=n&&ypro((i-1)%5+1)>=1&&ypro((i-1)%5+1)<=m)
                    seg.Update(1,1,n,m,1,xpro((i-1)/5+1),ypro((i-1)%5+1),jz[i]*f);
            }
        }
        else{
            printf("%lld\n",seg.Query(1,1,n,m,1,stx-a,sty-b,stx+c,sty+d));
        }
    }
}

P2086 题解

题目分析

初始化

修改

查询

AC CODE

温馨提示：抄代码一时爽，棕名封号两行泪！