bzoj:3110: [Zjoi2013]K大数查询

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操作中c<=Maxlongint

树套树……一直纠结要不要可持久化……直接动态开点居然过了……

两层线段树，外层权值，内层区间，即权值在[l,r]间的点在位置[a,b]间有多少个。

挺好理解吧

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int MAXN=50000;
int n,m=0,k,root[MAXN<<2],tp,l,r,c,num=0,p,ch;
struct tree{
    int l,r,s,ta;
} t[20000005];
inline int read(){
    p=0;ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') p=p*10+ch-48, ch=getchar();
    return p;
}
inline int an(int x,int l,int r,int a,int b){
    if (l==a&&r==b) return t[x].s;
    int mid=l+r>>1;
    if (b<=mid) return an(t[x].l,l,mid,a,b)+(b-a+1)*t[x].ta;else
    if (a>mid) return an(t[x].r,mid+1,r,a,b)+(b-a+1)*t[x].ta;else
    return an(t[x].l,l,mid,a,mid)+an(t[x].r,mid+1,r,mid+1,b)+(b-a+1)*t[x].ta;
}
inline int ask(int a,int b,int c){
    int l=1,r=n,mid,k=1,t;
    while(l<r){
        mid=l+r>>1;
        k<<=1;k|=1;
        t=an(root[k],1,n,a,b);
        if (t<c) r=mid,k^=1,c-=t;else l=mid+1;
    }
    return l;
}
inline void ins(int &k,int l,int r,int a,int b){
    if (!k) k=++num;
    t[k].s+=b-a+1;
    if (l==a&&r==b){
        t[k].ta++;
        return;
    }
    int mid=l+r>>1;
    if (b<=mid) ins(t[k].l,l,mid,a,b);else
    if (a>mid) ins(t[k].r,mid+1,r,a,b);else ins(t[k].l,l,mid,a,mid),ins(t[k].r,mid+1,r,mid+1,b);
}
inline void in(int a,int b,int c){
    int l=1,r=n,k=1,mid;
    while(l<r){
        mid=l+r>>1;
        ins(root[k],1,n,a,b);
        k<<=1;
        if (c<=mid) r=mid;else k|=1,l=mid+1;
    }
    ins(root[k],1,n,a,b);
}
int main(){
    n=read();m=read();
    while(m--){
        tp=read();l=read();r=read();c=read();
        if (tp==1) in(l,r,c);else printf("%d
",ask(l,r,c));
    }
}

View Code

Add at 2016.4.1

以上是数据修改前的做法

修改后用树套树就得离散化了……

分治好写些

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

int read_p,read_ca,read_f;
inline int read(){
    read_p=0;read_ca=getchar();read_f=1;
    while(read_ca<'0'||read_ca>'9') {if (read_ca=='-') read_f=-1;read_ca=getchar();}
    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p*read_f;
}
struct na{
    int l,r,t,o;
    ll c;
}b[50001],x1[50001],x2[50001];
struct tree{
    int l,r;
    ll w,k;
}t[250000];
int n,m,num=0,root=0;
ll ans[50001];
bool bo;
const ll INF=3e9;
inline void in(int &p,int l,int r,ll a,ll b){
    if (p==0) p=++num,t[p].l=t[p].r=t[p].w=t[p].k=0;
    if (l==a&&r==b){
        t[p].w++;
        return;
    }
    t[p].k+=b-a+1;
    int mid=(l+r)>>1;
    if (b<=mid) in(t[p].l,l,mid,a,b);else
    if (a>mid) in(t[p].r,mid+1,r,a,b);else
    in(t[p].l,l,mid,a,mid),in(t[p].r,mid+1,r,mid+1,b);
}
int pr_num,pr_ch[1000];
inline void pr(ll k){
    pr_num=0;
    while(k>0) pr_ch[++pr_num]=k%10,k/=10;
    while(pr_num) putchar(pr_ch[pr_num--]+48);
    putchar('
');
}
inline ll ask(int p,int l,int r,ll a,ll b){
    if (!p) return 0;
    if (l==a&&r==b) return t[p].k+t[p].w*(b-a+1);
    int mid=(l+r)>>1;
    if (b<=mid) return ask(t[p].l,l,mid,a,b)+t[p].w*(b-a+1);else
    if (a>mid) return ask(t[p].r,mid+1,r,a,b)+t[p].w*(b-a+1);else
    return ask(t[p].l,l,mid,a,mid)+ask(t[p].r,mid+1,r,mid+1,b)+t[p].w*(b-a+1);
}
inline void work(int f,int t,ll l,ll r){
    register int i;
    if (l==r){
        for (i=f;i<=t;i++)
        if (b[i].o) ans[b[i].t]=l;
        return;
    }
    bo=1;
    for (i=f;i<=t;i++)
    if (b[i].o) bo=0;
    if (bo) return;
    ll mid=(l+r)>>1,a;
    int ta1=0,ta2=0;
    num=root=0;
    bo=1;
    for (i=f;i<=t;i++)
    if (!b[i].o) if (b[i].c<=mid) in(root,1,n,b[i].l,b[i].r),x1[ta1++]=b[i];else x2[ta2++]=b[i];else{
        a=ask(root,1,n,b[i].l,b[i].r);
        if (a>=b[i].c) x1[ta1++]=b[i];else b[i].c-=a,x2[ta2++]=b[i];
    }
    for (i=0;i<ta1;i++) b[i+f]=x1[i];
    for (i=0;i<ta2;i++) b[i+f+ta1]=x2[i];
    if (ta1) work(f,f+ta1-1,l,mid);
    if (ta2) work(f+ta1,t,mid+1,r);
}
int main(){
    register int i;
    n=read();m=read();
    for (i=1;i<=m;i++) b[i].t=i,b[i].o=read()-1,b[i].l=read(),b[i].r=read(),b[i].c=read(),b[i].c=b[i].o?b[i].c:-b[i].c,ans[i]=(!b[i].o)?-INF:0;
    work(1,m,-INF,INF);
    for (i=1;i<=m;i++) if (ans[i]!=-INF) pr(-ans[i]);
}

View Code