Bakser's Blog

我是逗比。

bzoj3110[Zjoi2013]K大数查询 BIT套线段树

| Comments

不考虑奇怪的东西的话,树套树显然。
但是如果按照一般做法,外层区间内层权值的话会很蛋疼。

所以考虑外层维护权值,内层是区间。
我外层用的BIT,当然权值线段树也可以。每次修改操作外层就是BIT的修改,内层就是线段树的区间覆盖,打标记就好了。
询问时二分答案,由于查询的是k大,不是很好做。就在读入的时候将数倒过来,然后查k小就可以了。

bzoj3110
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N(50100);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define lowbit(x) (x&(-x))
inline void read(int &x)
{
    char c(0);bool flag(0);
    for(;c<'0'||c>'9';c=getchar())if(c=='-')flag=1;
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
}
struct hh
{
    int l,r,sum,cover;
}tree[N<<6];
int n,m,c[N],maxx,L,R,x,tot;
inline void modify(int &x,int l,int r)
{
    if(!x)x=++tot;
    if(l>=L&&r<=R){tree[x].sum+=r-l+1,tree[x].cover++;return;}
    int mid(l+r>>1);
    if(L<=mid)modify(tree[x].l,l,mid);
    if(R>mid)modify(tree[x].r,mid+1,r);
    tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum+tree[x].cover*(r-l+1);
}
inline int query(int x,int l,int r)
{
    if(!x)return 0;
    if(l>=L&&r<=R)return tree[x].sum;
    int mid(l+r>>1),res(0);
    if(L<=mid)res+=query(tree[x].l,l,mid);
    if(R>mid)res+=query(tree[x].r,mid+1,r);
    return res+tree[x].cover*(MIN(r,R)-MAX(L,l)+1);
}
inline void change(int x)
{
    for(int i=x;i<=n;i+=lowbit(i))
        modify(c[i],1,n);
}
inline int calc(int x)
{
    int res(0);
    for(int i=x;i;i-=lowbit(i))
        res+=query(c[i],1,n);
    return res;
}
inline int ask(int x)
{
    int l(1),r(maxx);
    while(l<r)
    {
        int mid(l+r>>1);
        if(calc(mid)<x)l=mid+1;
        else r=mid;
    }
    return r;
}
int main()
{
    read(n);read(m);
    for(int f;m--;)
    {
        read(f);read(L);read(R);read(x);
        if(f==1)
        {
            x=n-x+1;
            maxx=MAX(maxx,x);
            change(x);
        }
        else printf("%d\n",n-ask(x)+1);
    }
    return 0;
}

Comments

comments powered by Disqus