ZOJ2112 Dynamic Rankings(树状数组套主席树 || 分块)

@zryabc  January 10, 2019

题目

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.
    给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:

对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)
并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。

思路1(分块)

很显然分块明显可解。
二分ans,查询在每个块中的<=ans的数有多少个,在根据其与k的关系调整ans。
块内每改变一个值可以直接sort,再二分查找。
复杂度块内$S*log(S)$,块外$(n/S)*log(1e9)$
所以块的大小为$nlog(n)$,时间复杂度为$nlog(nlogn)*log(1e9)$

#include<bits/stdc++.h>
#define M 100005
using namespace std;
int A[M],n,m,s,L,R,K,T,tmp[80][1300],l,r,k,x,t;
char S[5];
bool check(int x) { 
    int ka=L/s,kb=R/s,cnt=0,cur;
    if(ka==kb) {
        for(int i=L; i<=R; i++)
            if(A[i]<=x)cnt++;
    } else {
        for(int i=L; i<(ka+1)*s; i++)cnt+=A[i]<=x;
        for(int i=kb*s; i<=R; i++)cnt+=A[i]<=x;
        for(int i=ka+1; i<kb; i++){
            cur=upper_bound(tmp[i]+1,tmp[i]+tmp[i][0]+1,x)-tmp[i]-1;
            cnt+=cur;
        } 
    }
    return cnt>=K;
}
int query(int a,int b,int k) {
    int l=0,r=1e9,ans=0;
    L=a;R=b;K=k;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            ans=mid;
            r=mid-1;
        } else l=mid+1;
    }
    return ans;
}
int main() {
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m); 
        s=sqrt(log2(n)*n);
        memset(tmp,0,sizeof(tmp));
        if(s==0)s=1;
        for(int i=0; i<n; i++)scanf("%d",&A[i]);
        for(int i=0; i<n/s; i++) {
            tmp[i][0]=0;
            for(int j=i*s; j<(i+1)*s; j++) 
                tmp[i][++tmp[i][0]]=A[j];
            sort(tmp[i]+1,tmp[i]+tmp[i][0]+1);
        }
        while(m--) {
            scanf("%s",S);
            if(S[0]=='Q'){
                scanf("%d%d%d",&l,&r,&k);
                printf("%d\n",query(l-1,r-1,k));
            } 
            if(S[0]=='C'){
                scanf("%d%d",&x,&t);x--;
                int i=x/s;
                int cur=lower_bound(tmp[i]+1,tmp[i]+tmp[i][0]+1,A[x])-tmp[i];
                tmp[i][cur]=t;
                sort(tmp[i]+1,tmp[i]+tmp[i][0]+1);
                A[x]=t;
            }
        }
    }
    return 0;
}

思路2(主席树+树状数组)

年轻人的第一道树套树。
首先静态的主席树不难实现,不会的同学出门左转看以前的文章,关键是如何修改。

这里的办法是在外面套一个树状数组,记录修改的信息。树状数组中每一个节点对应的都是一棵主席树,每棵主席树管的区间是$[n-lowbit(n)+1,n]$
最后查询的时候把这些一起考虑进去就行了。
值得注意的是,要把问题分成一棵初始的静态主席树和动态主席树,这样的时间复杂度是$(n+m)log^2n$的。

然而我BZOJA了,ZOJ一直SG,请大佬帮忙看看。

#include<bits/stdc++.h>
const int N=5e4+5;
const int M=1e4+5;
const int NN=2000005;
using namespace std;
int n,m;
int Lson[NN],Rson[NN],ver[N+N],Cnt[NN];
int tt=0;
vector<int>v1,v2;
void Insert(int od,int &rt,int x,int d,int L,int R){
    rt=++tt;
//    if(tt>M)exit(0);
    Lson[rt]=Lson[od];
    Rson[rt]=Rson[od];
    Cnt[rt]=Cnt[od]+d;
    if(L==R)return;
    int mid=(L+R)>>1;
    if(x<=mid)Insert(Lson[od],Lson[rt],x,d,L,mid);
    else Insert(Rson[od],Rson[rt],x,d,mid+1,R);
}
#define A v1
#define B v2
int query(int l,int r,int L,int R,int k){//plus A ,remove B 
    if(L==R)return L;
    int cnt=Cnt[Lson[r]]-Cnt[Lson[l]];
    for(int i=0;i<(int)A.size();i++)cnt+=Cnt[Lson[A[i]]];
    for(int i=0;i<(int)B.size();i++)cnt-=Cnt[Lson[B[i]]]; 
    int mid=(L+R)>>1;
    if(k<=cnt){
        for(int i=0;i<(int)A.size();i++)A[i]=Lson[A[i]];
        for(int i=0;i<(int)B.size();i++)B[i]=Lson[B[i]]; 
        return query(Lson[l],Lson[r],L,mid,k);
    }
    else {
        for(int i=0;i<(int)A.size();i++)A[i]=Rson[A[i]];
        for(int i=0;i<(int)B.size();i++)B[i]=Rson[B[i]];
        return query(Rson[l],Rson[r],mid+1,R,k-cnt);
    }
}
#undef A
#undef B
int A[N],B[N+M];
struct BIT{
    int C[N];
    void clear(){
        memset(C,0,sizeof(C));
    }
    void add(int x,int od,int d){
        while(x<=n){
            Insert(C[x],C[x],od,-1,1,n); 
            Insert(C[x],C[x],d,1,1,n);
            x+=(x&-x);
        }
    }
    void make_vec(vector<int>& A,int x){
        A.clear();
        while(x){
            A.push_back(C[x]);
            x-=(x&-x);
        }
    }
}tr;
char S[5];
struct Qr{    
    bool fl;
    int l,r,k;
}qr[M];
int main(){
//    printf("%lf",(&cur2-&cur1)/1024.0);
    int T;cin>>T;
    while(T--){
        tt=0;
        memset(ver,0,sizeof(ver));
        Cnt[0]=Lson[0]=Rson[0]=0;
        scanf("%d%d",&n,&m);
        int tp=n;
        for(int i=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i];
        tr.clear();
        for(int i=1,l,r,k;i<=m;i++){
            scanf("%s",S);
            if(S[0]=='Q'){
                scanf("%d%d%d",&l,&r,&k);
                qr[i].fl=0;qr[i].l=l;qr[i].r=r;qr[i].k=k;
            }
            else {
                scanf("%d%d",&l,&r);
                qr[i].fl=1;qr[i].l=l;qr[i].r=r;B[++n]=r;
            }
        }
        sort(B+1,B+n+1);
        n=unique(B+1,B+n+1)-B-1;
        for(int i=1;i<=tp;i++)A[i]=lower_bound(B+1,B+n+1,A[i])-B;
        for(int i=1;i<=tp;i++)Insert(ver[i-1],ver[i],A[i],1,1,n);
        for(int i=1,l,r,k;i<=m;i++){
            l=qr[i].l;r=qr[i].r;k=qr[i].k;
            if(qr[i].fl==0){
                tr.make_vec(v1,r);
                tr.make_vec(v2,l-1);
                printf("%d\n",B[query(ver[l-1],ver[r],1,n,k)]);        
            }
            else {
                r=lower_bound(B+1,B+n+1,r)-B;
                tr.add(l,A[l],r);
                A[l]=r;
            }
        }
    }
    return 0;
}

添加新评论