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

n+e

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

 
 
 

日志

 
 

[BZOJ3110][Zjoi2013]K大数查询  

2015-01-05 19:36:25|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3110: [Zjoi2013]K大数查询

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1491  Solved: 680
[Submit][Status]

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M
接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

HINT

【样例说明】
第一个操作后位置 1 的数只有 1 ,位置 2 的数也只有 1 。 第二个操作后位置 1的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问位置 1 到位置 2 第 3大的数是 1 。?

N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中abs(c)<=Maxlongint

Solution

十分无脑的想法是,把这个东西弄成二维的,第一维为权值,第二维为序列的坐标。

我们对这个二维的平面建一棵二维的线段树,这样的话,插入一段区间就相当于修改log个包含权值c的线段树,查询的话就是在第一层的权值线段树上二分,也要查log个包含所查询的权值范围的线段树。这样的话就可以在O(n*log^2)的时间內出解,只不过常数太大,虽然能过就是了。

因为线段树如果直接开的话,需要O(n^2)的内存,无法承受,所以对于每一个节点都要动态开内存,类似主席树那样的写法(我会说我脑补了好久写法吗...)

然后这题还有其他解法,比如整体二分+cdq之类的没太明白,反正我拿它当我的第一题树套树。

其实树套树很短的2333不到2K

Code

/**************************************************************
    Problem: 3110
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:8580 ms
    Memory:236204 kb
****************************************************************/
 
#include<cstdio>
#define u32 unsigned int
u32 aa;char ch;u32 F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
u32 tot,n,m,op,x,y,c,root[262144],cnt;
struct T{u32 ls,rs,sum,tag;}t[15000000];
void pd(u32 o,u32 l,u32 r)
{
    if(t[o].tag)
    {
        u32 mid=l+r>>1;
        if(t[o].ls==0)t[o].ls=++tot;
        if(t[o].rs==0)t[o].rs=++tot;
        t[t[o].ls].tag+=t[o].tag;
        t[t[o].rs].tag+=t[o].tag;
        t[t[o].ls].sum+=(mid-l+1)*t[o].tag;
        t[t[o].rs].sum+=(r-mid)*t[o].tag;
        t[o].tag=0;
    }
}
u32 up1(u32 o,u32 l,u32 r)
{
    if(o==0)o=++tot;
    if(x<=l&&r<=y)t[o].sum+=r-l+1,t[o].tag++;
    else
    {
        u32 mid=l+r>>1;pd(o,l,r);
        if(x<=mid)t[o].ls=up1(t[o].ls,l,mid);
        if(mid<y)t[o].rs=up1(t[o].rs,mid+1,r);
        t[o].sum=t[t[o].ls].sum+t[t[o].rs].sum;
    }
    return o;
}
u32 qu1(u32 o,u32 l,u32 r)
{
    if(o==0)return 0;
    if(x<=l&&r<=y)return t[o].sum;
    u32 mid=l+r>>1,tmp=0;pd(o,l,r);
    if(x<=mid)tmp+=qu1(t[o].ls,l,mid);
    if(mid<y)tmp+=qu1(t[o].rs,mid+1,r);
    return tmp;
}
void up2(u32 o,u32 l,u32 r)
{
    root[o]=up1(root[o],1,n);
    if(l!=r)
    {
        u32 mid=l+r>>1;
        if(c<=mid)up2(o<<1,l,mid);
        else up2(o<<1|1,mid+1,r);
    }
}
u32 qu2(u32 o,u32 l,u32 r,u32 res)
{
    if(l==r)return l;u32 mid=l+r>>1,sum=qu1(root[o<<1|1],1,n);
    if(sum<res)return qu2(o<<1,l,mid,res-sum);
    else return qu2(o<<1|1,mid+1,r,res);
}
int main()
{
    for(n=F(),m=F();m--;)
    {
        op=F(),x=F(),y=F(),c=F();
        if(op==1)up2(1,1,n);
        else printf("%u\n",qu2(1,1,n,c));
    }
}
  评论这张
 
阅读(76)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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