BZOJ3110: [Zjoi2013]K大数查询

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3110

Solution

调了一个晚上。。。
我用线段树套线段树做的常数巨大
外面一层放权值线段树，里面普通区间线段树。
里面的线段树记录外面对应节点权值在区间出现的次数。
查询k大的时候类似二分，找mid+1~r中的数有多少次出现询问区间中，记ans，
若ans＞k，向右继续找，否则向左找第k-ans大。
注意long long。(为什么别人的板子不要┑(￣Д ￣)┍)
注意负数和零。(但好像并没这种情况)

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 1000005
#define M 20000010
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch>'9'||ch<'0'){if (ch=='-') f=-1; ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
inline void writeln(ll x){
    write(x); putchar('\n');
}
ll left[M],right[M],lazy[M],root[N];
ll n,m,opt,a,b,c,size;
long long sum[M],k;
void pushdown(ll x,ll L,ll R){
    if (!left[x]) left[x]=++size;
    if (!right[x]) right[x]=++size;
    ll l=left[x],r=right[x],mid=L+R>>1;
    if (lazy[x]){
        lazy[l]+=lazy[x]; lazy[r]+=lazy[x];
        sum[l]+=lazy[x]*(mid-L+1); sum[r]+=lazy[x]*(R-mid);
        lazy[x]=0;
    }
}
void pushup(ll x){sum[x]=sum[left[x]]+sum[right[x]];}
void add(ll l,ll r,ll x,ll y,ll &p){
    if (!p) p=++size;
    if (l==x&&r==y){
        sum[p]+=r-l+1;
        lazy[p]++;
        return;
    }
    pushdown(p,l,r);
    ll mid=l+r>>1;
    if (y<=mid) add(l,mid,x,y,left[p]);
    else if (x>mid) add(mid+1,r,x,y,right[p]);
    else add(l,mid,x,mid,left[p]),add(mid+1,r,mid+1,y,right[p]);
    pushup(p);
}
void ADD(ll l,ll r,ll x,ll y,ll v,ll p){
    add(1,n,x,y,root[p]);
    if (l==r) return;
    ll mid=l+r>>1;
    if (v<=mid) ADD(l,mid,x,y,v,p<<1);
    else ADD(mid+1,r,x,y,v,p<<1|1);
}
long long query(ll l,ll r,ll x,ll y,ll p){
    if (!p) return 0;
    if (l==x&&r==y) return sum[p];
    pushdown(p,l,r);
    ll mid=l+r>>1;
    if (y<=mid) return query(l,mid,x,y,left[p]);
    else if (x>mid) return query(mid+1,r,x,y,right[p]);
    else return query(l,mid,x,mid,left[p])+query(mid+1,r,mid+1,y,right[p]);
}
ll QUERY(ll l,ll r,ll x,ll y,long long k,ll p){
    if (l==r) return l;
    ll mid=l+r>>1;long long ans=query(1,n,x,y,root[p<<1|1]);
    if (k>ans) return QUERY(l,mid,x,y,k-ans,p<<1);
    else return QUERY(mid+1,r,x,y,k,p<<1|1);
}
int main(){
    n=read(); m=read();
    while (m--){
        opt=read(); a=read(); b=read();
        if (opt==1) c=read(),ADD(0,n<<1,a,b,c+n,1);
        else scanf("%lld",&k),writeln(QUERY(0,n<<1,a,b,k,1)-n);
    }
}