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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3110][Zjoi2013]K大数查询  

2014-12-12 11:20:49|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3110: [Zjoi2013]K大数查询

这道题有三种做法……
一开始一种写法也不会QAQ
没认真读题,以为求第k小= =、最后改成第k大的时候各种混乱导致WA
太弱
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
typedef long long ll;
struct Data{
int i,t,a,b,c;
}ask[N*2],tmp[N];
int n,m,data[N],list[N*2],ans[N];
namespace tr{
ll tree[2][N];
void push(int t,int x,int val){for(;x<=n+1;x+=x&-x)tree[t][x] += val;}
ll get(int t,int x){ll re=0;for(;x;x-=x&-x)re += tree[t][x];return re;}
int query(int l,int r){
ll tmp=0;
tmp = (get(0,r) - get(0,l-1))*(r+1) - (get(1,r)-get(1,l-1)) + get(0,l-1)*(r-l+1);
return tmp;
}
void add(int l,int r,int val){
push(0,l,val);
push(0,r+1,-val);
push(1,l,l*val);
push(1,r+1,(r+1)*-val);
}
}
short v[N],va[N];
bool Select(Data &a){return !v[a.i];}
void solve(int la,int ra,int ld,int rd){
using namespace tr;
int mid = (ld+rd)/2,mida,i;
//if(list[mid]==8) printf("0");
if(ld==rd){
for(i=la;i<=ra;i++)
if(ask[i].t==2) ans[ask[i].i] = list[ld];
return;
}
for(i=la;i<=ra;i++){
if(ask[i].t==1){
if(ask[i].c > mid)add(ask[i].a,ask[i].b,1),v[ask[i].i]=1;
else v[ask[i].i]=0;
}else{
int tmp=0;
tmp = query(ask[i].a,ask[i].b);
if(ask[i].c <= tmp)v[ask[i].i]=1;
else v[ask[i].i]=0,ask[i].c -= tmp;
}
}
for(i=la;i<=ra;i++)
if(ask[i].t==1 && ask[i].c > mid)add(ask[i].a,ask[i].b,-1);

mida = std::stable_partition(ask+la,ask+1+ra,Select)-ask-1;
//printf("[%d]",list[mid]);
// for(i=la;i<=mida;i++)printf("%d ",ask[i].i);printf("| ");
// for(i=mida+1;i<=ra;i++)printf("%d ",ask[i].i);printf("\n");
//for(i=la;i<mida;i++)if(ask[i].i > ask[i+1].i)printf("W");
//for(i=mida+1;i<ra;i++)if(ask[i].i > ask[i+1].i)printf("W");
//printf("%d %d\n",mida,v[ask[mida+1].i]);
solve(la,mida,ld,mid);
solve(mida+1,ra,mid+1,rd);
}
int main(){
int i,j,a,b,c;
//freopen("in.txt","r",stdin);
n = scan();m = scan();
for(i=1;i<=m;i++){
j = scan();a = scan();b = scan();c = scan();
ask[i] = (Data){i,j,a,b,c};
if(ask[i].t==1)list[++list[0]] = c;
else va[i]=1;
}
sort(list+1,list+1+list[0]);
list[0] = unique(list+1,list+1+list[0]) - list - 1;
for(i=1;i<=m;i++)
if(ask[i].t == 1)
ask[i].c = lower_bound(list+1,list+1+list[0],ask[i].c)-list;
solve(1,m,1,list[0]);
for(i=1;i<=m;i++)if(va[i])printf("%d\n",ans[i]);
return 0;
}

题解:
解法一:
· 线段树套线段树,外层是权值线段树,内层是维护标记的区间线段树。
直接写容易被卡常数。
优化:
外层用树状数组(我不会写……)
内层标记永久化
解法二:
树状数组套主席树。
单点修改可以这么做显而易见吧。
那这个题就用可以区间修改区间查询树状数组套主席树
(话说这里还能算主席树吗……准确地来说应该只是普通的线段树吧……)
解法三:
线段树+整体二分。
感觉是听起来最高大上的写法/w\
我用的这种写法
优化:
线段树改成区间修改区间查询的树状数组。
  评论这张
 
阅读(1413)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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