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

n+e

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

 
 
 

日志

 
 

[BZOJ4066]简单题  

2015-05-13 20:48:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4066: 简单题

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 67  Solved: 38
[Submit][Status][Discuss]

Description

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

命令

参数限制

内容

1 x y A

1<=x,y<=NA是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

3

终止程序

Input

输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外,
均要异或上一次输出的答案last_ans,初始时last_ans=0。

Output

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

Sample Input

4 1 2 3 3 2 1 1 3 3 1 1 1 1 2 1 1 0 7 3

Sample Output

3 5

HINT

数据规模和约定
1<=N<=500000,操作数不超过200000个,内存限制128M,保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683

Solution

如果不强制在线的话,这题可以离线cdq分治解决。
某天当我又看到BZOJ2683的时候,猛然间发现,这不是kdtree可以直接维护嘛?
于是就有了这道题。
不知道我写的kdtree是不太优美还是什么,加了重构还是慢出翔。。。

Code

/**************************************************************
    Problem: 4066
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:27456 ms
    Memory:13076 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstdlib>
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++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
char buf[1<<22],*O=buf,stk[30];int ts;
void Pr(int x){
    if(!x)*O++=48;else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=48+stk[ts--]);
    }*O++='\n';
}
#define cmax(a,b) (a<b?a=b:1)
#define cmin(a,b) (a>b?a=b:1)
int rt,op,ans,D,tot,X0,X1,Y0,Y1,x,y;
#define fac 0.65
struct T{
    int d[2],s[2],x[2],y[2],w,sum,siz,ty;
    void setup(int xx,int yy,int v){
        s[0]=s[1]=0,x[0]=x[1]=d[0]=xx,y[0]=y[1]=d[1]=yy,sum=w=v,siz=1;
    }
    void clr(){
        x[0]=x[1]=d[0],y[0]=y[1]=d[1];
        s[0]=s[1]=0,sum=w,siz=1;
    }
}t[160010],tmp;
bool cmp(int a,int b){return t[a].d[D]<t[b].d[D];}
class KDTree{public:
#define ls t[now].s[0]
#define rs t[now].s[1]
    int po[160010],pt;
    void mt(int o,int s){
        t[o].sum+=t[s].sum,t[o].siz+=t[s].siz;
        cmin(t[o].x[0],t[s].x[0]),cmin(t[o].y[0],t[s].y[0]);
        cmax(t[o].x[1],t[s].x[1]),cmax(t[o].y[1],t[s].y[1]);
    }
    int bt(int l,int r,int d){
        int mid=l+r>>1,now;D=d;
        std::nth_element(po+l,po+mid,po+r+1,cmp);now=po[mid];
        t[now].clr();t[now].ty=d;
        if(l<mid)ls=bt(l,mid-1,d^1),mt(now,ls);
        if(mid<r)rs=bt(mid+1,r,d^1),mt(now,rs);
        return now;
    }
    void dfs(int now){
        po[++pt]=now;
        if(ls)dfs(ls);
        if(rs)dfs(rs);
    }
    int ins(int p,int now){
        if(!p)return t[now].ty=rand()&1,now;
        mt(p,now);D=t[p].ty;int&nx=t[p].s[t[now].d[D]>=t[p].d[D]];
        if(t[nx].siz>t[p].siz*fac)return po[pt=1]=now,dfs(p),p==rt?rt=bt(1,pt,t[p].ty):bt(1,pt,t[p].ty);
        nx=ins(nx,now);return p;
    }
#define check(a) (a.x[0]<=X1&&X0<=a.x[1]&&a.y[0]<=Y1&&Y0<=a.y[1])
    void query(int now){
        if(X0<=t[now].x[0]&&t[now].x[1]<=X1
         &&Y0<=t[now].y[0]&&t[now].y[1]<=Y1){
            ans+=t[now].sum;return;
        }
        if(X0<=t[now].d[0]&&t[now].d[0]<=X1
         &&Y0<=t[now].d[1]&&t[now].d[1]<=Y1)ans+=t[now].w;
        if(ls&&check(t[ls]))query(ls);
        if(rs&&check(t[rs]))query(rs);
    }
}kdt;
int main(){
    x=y=F()/2;t[tot=rt=1].setup(x,y,0);
    while(op=F(),op!=3)
    if(op==1){
        x=F()^ans,y=F()^ans,t[++tot].setup(x,y,F()^ans);
        kdt.ins(rt,tot);
    }
    else{
        X0=F()^ans,Y0=F()^ans,X1=F()^ans,Y1=F()^ans;
        ans=0,kdt.query(rt),Pr(ans);
    }*--O=0,puts(buf);
}
  评论这张
 
阅读(587)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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