zoj_2112 Dynamic Rankings

题目:

  The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0 < k < =j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
  Your task is to write a program for this computer, which
  Reads N numbers from the input (1 <= N <= 50,000)
  Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.

思路:

  • 分块:
      考虑去二分第大的值。那么只要能求出一个区间内大于的值的个数,二分就能实现了。对整个序列分块,并在块内排序。查询时,对于散块就直接暴力地用每个数去和比较。对于整块就用二分去计算个数。修改时直接在块内再做一次插入排序就行了。那么设块大小为。整个问题的复杂度就是。当时最小(把看做)。
  • 主席树:
      如果直接写普通的主席树,因为主席树维护的是一个前缀,那么每次修改的时候就要修改棵树了(最坏情况)。这样显然是不行的,考虑到前缀,不难想到树状数组。所以只要用树状数组维护主席树(为了好写,我只维护了修改的结果),每次操作就只有了。

代码:

  • 分块:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define MN 50005
#define BL 900
#define Log(a,b) (log(a)/log(b))
using namespace std;
int a[MN],bl[BL][BL];
int id[MN],tot[BL];
int query(int l,int r,int k){
    int ans=0;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)
            ans+=(a[i]<=k);
        return ans;
    }
    for(int i=l;id[i]==id[l];i++)
        ans+=(a[i]<=k);
    for(int i=r;id[i]==id[r];i--)
        ans+=(a[i]<=k);
    for(int i=id[l]+1;i<id[r];i++)
        ans+=upper_bound(bl[i]+1,bl[i]+1+tot[i],k)-bl[i]-1;
    return ans;
}
int solve(int l,int r,int k){
    int L=0,R=1e9,mid,ans;
    while(L<=R){
        mid=L+R>>1;
        if(query(l,r,mid)>=k)
            ans=mid,R=mid-1;
        else
            L=mid+1;
    }
    return ans;
}
void upd(int w,int x){
    int p=lower_bound(bl[id[w]]+1,bl[id[w]]+1+tot[id[w]],a[w])-bl[id[w]];
    bl[id[w]][p]=x;
    for(int i=p;i<tot[id[w]];i++){
        if(bl[id[w]][i]<bl[id[w]][i+1])break;
        swap(bl[id[w]][i],bl[id[w]][i+1]);
    }
    for(int i=p;i>1;i--){
        if(bl[id[w]][i]>bl[id[w]][i-1])break;
        swap(bl[id[w]][i],bl[id[w]][i-1]);
    }
    a[w]=x;
}
#define read(c) \
    do \
        c=getchar(); \
    while(c==' '||c=='\n')
int main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt","r",stdin);
#endif
    int n,m,bs,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(tot,0,sizeof tot);
        bs=sqrt(n*Log(n,2))+1;
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            id[i]=i/bs+1;
            bl[id[i]][++tot[id[i]]]=a[i];
        }
        for(int i=1;i<=id[n];i++)
            sort(bl[i]+1,bl[i]+1+tot[i]);
        int l,r,k;char c;
        while(m--){
            read(c);
            if(c=='Q'){
                int x;
                scanf("%d%d%d",&l,&r,&k);
                printf("%d\n",x=solve(l,r,k));
            }
            else {
                scanf("%d%d",&l,&k);
                upd(l,k);
            }
        }
    }
    return 0;
}
  • 主席树:
#include <bits/stdc++.h>
#define MN 50005
using namespace std;
#define ls(o) tre[o].LS
#define rs(o) tre[o].RS
struct Node{
    int LS,RS,sum;
};
Node tre[MN*50];
int num[MN<<1],a[MN],cnt,tot,siz,n,m;
void upd(int &o,int x,int v,int L,int R){
    tre[++tot]=tre[o];o=tot;
    tre[o].sum+=v;
    if(L==R)return;
    int mid=L+R>>1;
    if(x<=mid)upd(ls(o),x,v,L,mid);
    else upd(rs(o),x,v,mid+1,R);
}
int has(int x){return lower_bound(num+1,num+1+siz,x)-num;}
int Rt[MN],rot[MN];
#define low(x) (-(x)&(x))
void add(int p,int v){
    int tmp=has(a[p]);
    for(int i=p;i<=n;i+=low(i))
        upd(rot[i],tmp,v,1,siz);
}
void build(){
    sort(num+1,num+1+cnt);
    siz=unique(num+1,num+1+cnt)-num-1;
    tot=0;
    for(int i=1;i<=n;i++){
        upd(Rt[i]=Rt[i-1],has(a[i]),1,1,siz);
        rot[i]=0;
    }
}
int q1[MN],q2[MN],t1,t2;
int calc(){
    int sum=0;
    for(int i=1;i<=t1;i++)
        sum-=tre[ls(q1[i])].sum;
    for(int i=1;i<=t2;i++)
        sum+=tre[ls(q2[i])].sum;
    return sum;
}
int query(int l,int r,int k){
    t1=t2=0;
    for(int i=l-1;i;i-=low(i))q1[++t1]=rot[i];
    for(int i=r;i;i-=low(i))q2[++t2]=rot[i];
    l=Rt[l-1];r=Rt[r];
    int L=1,R=siz;
    while(1){
        if(L==R)return L;
        int sum=calc()+tre[ls(r)].sum-tre[ls(l)].sum,mid=L+R>>1;
        if(k<=sum){
            for(int i=1;i<=t1;i++)q1[i]=ls(q1[i]);
            for(int i=1;i<=t2;i++)q2[i]=ls(q2[i]);
            l=ls(l);r=ls(r);
            R=mid;
        }
        else {
            for(int i=1;i<=t1;i++)q1[i]=rs(q1[i]);
            for(int i=1;i<=t2;i++)q2[i]=rs(q2[i]);
            l=rs(l);r=rs(r);
            L=mid+1;k-=sum;
        }
    }
}
struct Ques{
    int i,j,k;
    char c;
};
Ques q[MN];
#define read(c) do c=getchar(); while(c!='C'&&c!='Q')
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            num[++cnt]=a[i];
        }
        for(int i=1;i<=m;i++){
            read(q[i].c);
            if(q[i].c=='Q')scanf("%d%d%d",&q[i].i,&q[i].j,&q[i].k);
            else {
                scanf("%d%d",&q[i].i,&q[i].k);
                num[++cnt]=q[i].k;
            }
        }
        build();
        for(int i=1;i<=m;i++){
            if(q[i].c=='Q')printf("%d\n",num[query(q[i].i,q[i].j,q[i].k)]);
            else {
                add(q[i].i,-1);
                a[q[i].i]=q[i].k;
                add(q[i].i,1);
            }
        }
    }
    return 0;
}