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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ZJOI2013 k大数查询  

2013-04-01 19:43:38|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本着是ZJOI的题。。于是去看了一下,想过了这道题然后当作讲课的例题的。。。没想到水过头了的说。。。
浙江出这种裸数据结构题有意思吗???而且还是非常非常简单的无脑数据结构
(题解等在BZOJ上过了再说)
算了,本机上过了就不说了。。
首先数据规模不是nlogn级别的,就很容易想到nlog^2n对吧。。。然后自然是什么东西套个什么东西的说。。。不过有人说可以用树状数组,反正我不知道树状数组怎么做的,于是写了个线段树。
为了支持查询操作,我们在线段树的每个区间记录下两个东西——子区间中添加的数的个数,以及完全包含了这个区间的数的个数。这两个东西是没有交的。
然后发现很容易写。。。也很好调,几乎一遍写对,于是BZOJ上一交,Output_Limit_Exceed.
只想说和vfleaking的神题相比,这种题目还差了一大截。
=======================================================
好了现在已经过了。。惊现1K代码,吓尿了,这得写多短啊!
=======================================================
和wyx大神讨论了一下,瞬间明白为何可以用树状数组做了。。
外围树状数组是记录权值的。而内部的线段树则记录区间。
我们知道线段树很自由,而树状数组在只有单点修改时是非常方便的。。而这样就只有单点修改了,实在是太神了。
现在似乎还是有问题??怎么用树状数组二分呢?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=300000+10;
const int NUM=10000000+10;

struct node
{
node* lc,*rc;
int sum;
void update()
{
sum=(lc?lc->sum:0)+(rc?rc->sum:0);
}
node():lc(0),rc(0),sum(0){}
}tree[NUM];
int cnt;

node* newnode()
{
return tree+cnt++;
}

node* add(node* u,int l,int r,int x,int c)
{
node* np=newnode();
if(u)*np=*u;
if(l==r)
np->sum+=c;
else
{
int mid=(l+r)/2;
if(x<=mid)
np->lc=add(u?u->lc:0,l,mid,x,c);
else
np->rc=add(u?u->rc:0,mid+1,r,x,c);
np->update();
}
return np;
}

node* root[MAX];//包含整个区间的情况
node* flag[MAX];//儿子的情况
int size[MAX];
int n,m;

void build(int u,int l,int r)
{
root[u]=newnode();
flag[u]=newnode();
size[u]=r-l+1;
if(l==r)return;
int mid=(l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
}

void insert(int u,int l,int r,int a,int b,int c)
{
if(r<a || b<l)
return;
if(a<=l && r<=b)
{
root[u]=add(root[u],1,n,c,1);
return;
}
int mid=(l+r)/2;
insert(u*2,l,mid,a,b,c);
insert(u*2+1,mid+1,r,a,b,c);
int num=min(r,b)-max(a,l)+1;
flag[u]=add(flag[u],1,n,c,num);
}

int top=0;
node* q[MAX];
int mult[MAX];

void ask(int u,int l,int r,int a,int b)
{
if(r<a || b<l)return;
int num=min(r,b)-max(a,l)+1;
q[++top]=root[u];
mult[top]=num;
if(a<=l && r<=b)
{
q[++top]=flag[u];
mult[top]=1;
return;
}
int mid=(l+r)/2;
ask(u*2,l,mid,a,b);
ask(u*2+1,mid+1,r,a,b);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j;
scanf("%d%d",&n,&m);
build(1,1,n);
int a,b,c,d;
REP(i,1,m)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a==1)
insert(1,1,n,b,c,d);
else
{
top=0;
ask(1,1,n,b,c);
int left=1,right=n;
while(left<right)
{
int mid=(left+right)/2;
LL k=0;
REP(j,1,top)
k+=( q[j] && q[j]->rc ) ?q[j]->rc->sum*mult[j]:0;
int mm=0;
if(k>=d)
{
left=mid+1;
REP(j,1,top)
if(q[j]->rc)
{
q[++mm]=q[j]->rc;
mult[mm]=mult[j];
}
}
else
{
right=mid;
d-=k;
REP(j,1,top)
if(q[j]->lc)
{
q[++mm]=q[j]->lc;
mult[mm]=mult[j];
}
}
top=mm;
}
printf("%d\n",left);
}
}
return 0;
}





  评论这张
 
阅读(1015)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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