注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2877][Noi2012]魔幻棋盘  

2015-06-20 17:05:39|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2877: [Noi2012]魔幻棋盘

Time Limit: 50 Sec  Memory Limit: 512 MB
Submit: 544  Solved: 236
[Submit][Status][Discuss]

Description

Input

第一行为两个正整数N,M,表示棋盘的大小。 第二行为两个正整数X,Y,表示棋盘守护者的位置。 第三行仅有一个正整数T,表示棋盘守护者将进行次操作。 接下来N行,每行有M个正整数,用来描述初始时棋盘上每个位置的数。 接下来T行,按操作的时间顺序给出T次操作。每行描述一次操作,以一个数字0或1开头: 若以数字0开头,表示此操作为询问,随后会有四个非负整数x1,y1,x2,y2,表示询问的区域是以棋盘守护者的位置为基础向上扩展x1行,向下扩展y1行,向左扩展x2列,向右扩展y2列得到的矩形区域(详见样例)。 若以数字1开头,表示此操作为修改,随后会有四个正整数x1,y1,x2,y2和一个整数c,表示修改区域的上、下边界分别为第x1,x2行,左、右边界分别为第y1,y2列(详见样例),在此矩形区域内的所有数统一加上c(注意c可能为负数)。

Output


 对于每次询问操作,每行输出一个数,表示该区域内所有数的最大公约数。

Sample Input

2 2 1 1 4 6 12 18 24 0 0 0 1 0 1 1 1 1 2 6 1 2 1 2 2 6 0 0 0 1 1

Sample Output

6 6

Solution

网络上好多。。。然而代码毒瘤。
以(X,Y)为原点差分整个棋盘,于是区间加变成了单点加,询问变成了前缀询问。
感觉拆成4块代码短好多,要不然边界真是蛋疼。而且二维zkw居然比普通线段树套zkw慢也是醉了

Code

/**************************************************************
    Problem: 2877
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:16240 ms
    Memory:50088 kb
****************************************************************/
 
#include<cstdio>
#define rg register
#define rint rg int
#define inc(i,a,b) for(rint i=a,__i=b;i<=__i;i++)
#define dec(i,a,b) for(rint i=a,__i=b;i>=__i;i--)
typedef long long ll;
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int F(){
    while(ch=getc(),!isd(ch));rint aa=ch-'0';
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return aa;
}ll Fl(){
    while(ch=getc(),!isd(ch)&&ch!='-');rint bb;rg ll ab;ch=='-'?ab=bb=0:(ab=ch-'0',bb=1);
    while(ch=getc(),isd(ch))ab=ab*10+ch-'0';return bb?ab:-ab;
}
#define N 1<<19
int n,m,X,Y,q,tot,swp;
ll mem_a[N],*a[10000],mem_b[N],*b[10000],mem_t[1<<22],g0,val;
#define swap(a,b) (swp=a,a=b,b=swp)
ll gcd(rg ll x,rg ll y){return !y?x:gcd(y,x%y);}
struct Tree{
ll *root[N],*now,*ls,*rs,v;int d,n,m,x,y;
void bt(rint o,rint l,rint r){
    now=root[o]=mem_t+tot,tot+=d+d+1;
    if(l==r){
        inc(i,0,m)now[i+d]=b[l][i];
        dec(i,d-1,1)now[i]=gcd(now[i<<1],now[i<<1|1]);
        return;
    }
    rint mid=l+r>>1;
    bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);
    now=root[o],ls=root[o<<1],rs=root[o<<1|1];
    dec(i,d+d-1,1)now[i]=gcd(ls[i],rs[i]);
}
void init(rint _n,rint _m){
    for(n=_n,m=_m,d=1;d<=m+1;d<<=1);bt(1,0,n);
}
void _upd(rint o,rint l,rint r){
    if(l==r){
        now=root[o],now[y+d]+=v;
        for(rint i=y+d;i>>=1;now[i]=gcd(now[i<<1],now[i<<1|1]));
        return;
    }
    rint mid=l+r>>1;
    if(x<=mid)_upd(o<<1,l,mid);else _upd(o<<1|1,mid+1,r);
    now=root[o],ls=root[o<<1],rs=root[o<<1|1];
    for(rint i=y+d;i;now[i]=gcd(ls[i],rs[i]),i>>=1);
}
#define work(_x,_y,_v) if(x=_x,y=_y,v=_v,x<=n&&y<=m)_upd(1,0,n)
void upd(rint x0,rint y0,rint x1,rint y1){
    if(x0>x1)swap(x0,x1);if(y0>y1)swap(y0,y1);
    if(x1<0||y1<0)return;
    if(x0<0)x0=0;if(y0<0)y0=0;x1++,y1++;
    work(x0,y0,val);work(x0,y1,-val);
    work(x1,y0,-val);work(x1,y1,val);
}
void _query(rint o,rint l,rint r){/*0~x,0~y*/
    if(r<=x){
        for(now=root[o],l=d-1,r=y+d+1;l^r^1;l>>=1,r>>=1)
        ~l&1?v=gcd(v,now[l^1]):1,
         r&1?v=gcd(v,now[r^1]):1;
        return;
    }
    rint mid=l+r>>1;_query(o<<1,l,mid);
    if(mid<x)_query(o<<1|1,mid+1,r);
}
ll query(rint _x,rint _y){return x=_x,y=_y,v=0,_query(1,0,n),v;}
}t0,t1,t2,t3;
int main(){
    n=F(),m=F(),X=F()-1,Y=F()-1,q=F(),a[0]=mem_a,b[0]=mem_b;
    inc(i,1,n)a[i]=a[i-1]+m,b[i]=b[i-1]+m;
    inc(i,0,n-1)inc(j,0,m-1)a[i][j]=Fl();
    inc(i,0,X-1){
        inc(j,0,Y-1)a[i][j]-=a[i+1][j]+a[i][j+1]-a[i+1][j+1];
        dec(j,m-1,Y+1)a[i][j]-=a[i+1][j]+a[i][j-1]-a[i+1][j-1];a[i][Y]-=a[i+1][Y];
    }
    dec(i,n-1,X+1){
        inc(j,0,Y-1)a[i][j]-=a[i-1][j]+a[i][j+1]-a[i-1][j+1];
        dec(j,m-1,Y+1)a[i][j]-=a[i-1][j]+a[i][j-1]-a[i-1][j-1];a[i][Y]-=a[i-1][Y];
    }
    inc(j,0,Y-1)a[X][j]-=a[X][j+1];
    dec(j,m-1,Y+1)a[X][j]-=a[X][j-1];
    inc(i,0,X)inc(j,0,Y)b[X-i][Y-j]=a[i][j];t0.init(X,Y);
    inc(i,X,n-1)inc(j,0,Y)b[i-X][Y-j]=a[i][j];t1.init(n-X-1,Y);
    inc(i,0,X)inc(j,Y,m-1)b[X-i][j-Y]=a[i][j];t2.init(X,m-Y-1);
    inc(i,X,n-1)inc(j,Y,m-1)b[i-X][j-Y]=a[i][j];t3.init(n-X-1,m-Y-1);
    for(rint x1,x2,y1,y2;q--;)
    if(!F()){
        x1=F(),y1=F(),x2=F(),y2=F(),
        g0=gcd(gcd(t0.query(x1,y1),t1.query(x2,y1)),gcd(t2.query(x1,y2),t3.query(x2,y2)));
        if(g0<0)g0=-g0;printf("%lld\n",g0);
    }else
        x1=F()-1,y1=F()-1,x2=F()-1,y2=F()-1,val=Fl(),
        t0.upd(X-x1,Y-y1,X-x2,Y-y2),
        t1.upd(x1-X,Y-y1,x2-X,Y-y2),
        t2.upd(X-x1,y1-Y,X-x2,y2-Y),
        t3.upd(x1-X,y1-Y,x2-X,y2-Y);
}
  评论这张
 
阅读(472)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018