zoj 2112 Dynamic Rankings 带修改区间第k大的几种解法

1.分块算法 (n*sqrt(n)*log^2n) 3200+ms

给出n个数，有两种操作，一种是修改某个数的值，另一种查询指定区间第k大。

比较快的做法是树套树，而分块算法复杂度比较高写起来方便。分块算法可以很简单的处理单独修改某个值的情况。

将n个数分成num块，每块大小siz=n/num。每一个块内部进行排序，查询[l,r]第k大时，先二分答案，对于完全包含在区间的内块直接二分搜索，而对于区间两端只有部分包含的则直接遍历查找。复杂度是logn*(2*siz+num*log(siz)),这里取siz=sqrt(n),复杂度主要就是logn*sqrt(n)*logn。

对于修改，因为一个数只在一个块里，直接在那个块里进行修改，原本所在块是已排序的，修改后只有一个数不满足顺序，做一次冒泡就好了，复杂为siz=sqrt(n)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=5e4+10;
int n,m;
int num,siz;
vector<int> sorted[1000];
int arr[maxn];

int main()
{
    int X;
    cin>>X;
    while(X--){
        cin>>n>>m;
        for(int i=0; i<n; i++)
            scanf("%d", arr+i);

        siz=sqrt(n);//每一块的大小
        num=(n+siz-1)/siz;//共num块
        for(int i=0; i<num; i++) sorted[i].clear();
        for(int i=0; i<n; i++){
            sorted[i/siz].push_back(arr[i]);
        }
        for(int i=0; i<num; i++)
            sort(sorted[i].begin(), sorted[i].end());

        while(m--){
            char s[5]; int a,b,k;
            scanf("%s%d%d", s, &a, &b);
            if(s[0]=='Q'){
                scanf("%d", &k);
                a--;b--;
                int l=0,r=1e9+1;
                int ans;
                while(l<r){//二分答案统计<=m的有多少个数
                    int m=(l+r)>>1;
                    int cnt=0;
                    for(int i=a/siz+1; i<b/siz; i++)//处理一定完全包含的块
                        cnt+=upper_bound(sorted[i].begin(), sorted[i].end(), m)-sorted[i].begin();
                        
                    if(a%siz==0)//处理左端可能部分包含的块
                        cnt+=upper_bound(sorted[a/siz].begin(), sorted[a/siz].end(), m)-sorted[a/siz].begin();
                    else{
                        for(int i=a; i%siz!=0; i++)
                            cnt+=arr[i]<=m;
                    }
                    
                    if(b%siz==siz-1)//处理右端可能部分包含的块
                        cnt+=upper_bound(sorted[b/siz].begin(), sorted[b/siz].end(), m)-sorted[b/siz].begin();
                    else{
                        for(int i=b; i%siz!=siz-1; i--)
                            cnt+=arr[i]<=m;
                    }

                    if(cnt>=k){
                        ans=m;
                        r=m;
                    }
                    else l=m+1;
                }
                printf("%d\n", ans);
            }
            else{
                a--;
                int pos=lower_bound(sorted[a/siz].begin(), sorted[a/siz].end(), arr[a])-sorted[a/siz].begin();
                arr[a]=sorted[a/siz][pos]=b;
                while(pos>0 && sorted[a/siz][pos]<sorted[a/siz][pos-1]){//冒泡
                    swap(sorted[a/siz][pos], sorted[a/siz][pos-1]);
                    pos--;
                }
                while(pos<sorted[a/siz].size()-1 && sorted[a/siz][pos]>sorted[a/siz][pos+1]){
                    swap(sorted[a/siz][pos], sorted[a/siz][pos+1]);
                    pos++;
                }

            }
        }
    }
    return 0;
}

2.线段树/树状数组套平衡树 O(n*log^3n) 700+ms sqrt(n)和logn还是差的挺远的

每个区间节点维护的是一棵平衡树，平衡树维护的是对应区间内的所有数。

查询的时候同样是二分答案mid，找到[l,r]对应所有区间节点，在每个节点的平衡树上查询<=mid的数有多少个,复杂度二分+线段树+平衡树=O(logn*logn*logn)。

修改的时候找到对应区间删除原来的数，再插入新的数即可 O(logn*logn)。

这种做法满足区间和，所以线段树可以用树状数组替换会比较快。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=5e4+10;
struct SBT
{
    int left,right,size,key;
    void Init()
    {
        left=right=0;
        size=1;
    }
}tree[20*maxn];
int tot;
void left_rotate(int &x)//左旋
{
    int y=tree[x].right;
    tree[x].right=tree[y].left;
    tree[y].left=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void right_rotate(int &x)//右旋
{
    int y=tree[x].left;
    tree[x].left=tree[y].right;
    tree[y].right=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void maintain(int &x,int flag)
{
    if(flag==0)
    {
        if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)
           right_rotate(x);
        else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)
            left_rotate(tree[x].left),right_rotate(x);
        else return;
    }
    else
    {
        if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)
            left_rotate(x);
        else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)
            right_rotate(tree[x].right),left_rotate(x);
        else return;
    }
    maintain(tree[x].left,0);
    maintain(tree[x].right,1);
    maintain(x,0);
    maintain(x,1);
}
//插入元素，相同元素放在右子树中
void insert(int &x,int key)
{
    if(x==0)
    {
        x=++tot;
        tree[x].Init();
        tree[x].key=key;
    }
    else
    {
        tree[x].size++;
        if(key<tree[x].key)insert(tree[x].left,key);
        else insert(tree[x].right,key);
        maintain(x,key>=tree[x].key);
    }
}
//删除key值的元素
int del(int &x,int key)
{
    if(!x)return 0;
    tree[x].size--;
    if(key==tree[x].key || (key<tree[x].key&&tree[x].left==0)
       || (key>tree[x].key&&tree[x].right==0))
    {
        if(tree[x].left && tree[x].right)
        {
            int p=del(tree[x].left,key+1);
            tree[x].key=tree[p].key;
            return p;
        }
        else
        {
            int p=x;
            x=tree[x].left+tree[x].right;
            return p;
        }
    }
    else return del(key<tree[x].key?tree[x].left:tree[x].right,key);
}

//名字改的不好。。功能是查询<=k的数有多少个
int get_kth(int &x,int k)
{
    if(!x) return 0;
    if(k<tree[x].key)
        return get_kth(tree[x].left, k);
    else
        return 1+tree[tree[x].left].size+get_kth(tree[x].right, k);
}

int n,m;
int a[maxn];
int root[maxn];


void bit_add(int x, int v)
{
 while(x<=n){
  insert(root[x], v);
  x+=(x&-x);
 }
}

void bit_del(int x, int v)
{
 while(x<=n){
  del(root[x], v);
  x+=(x&-x);
 }
}

int sum(int x, int v)
{
 int ret=0;
 while(x){
  ret+=get_kth(root[x], v);
  x-=(x&-x);
 }
 return ret;
}

void init()
{
 tot=0;
 memset(root, 0, sizeof(root));
 tree[0].Init(); tree[0].size=0;

 for(int i=1; i<=n; i++){
  scanf("%d", a+i);
  bit_add(i, a[i]);
 }
}

int main()
{
 int t;
 cin>>t;
 while(t--){
  scanf("%d%d", &n, &m);
  init();
  while(m--){
   char s[5]; int b,c,d;
   scanf("%s%d%d", s, &b, &c);
   if(s[0]=='Q'){
    scanf("%d", &d);
    int l=1,r=1e9+1,ans;
    while(l<r){
     int mid=(l+r)>>1;
     int cnt=sum(c, mid)-sum(b-1, mid);
     //cout<<mid<<' '<<cnt<<endl;
     if(cnt>=d){
      ans=mid;
      r=mid;
     }
     else l=mid+1;

    }
    printf("%d\n", ans);
   }
   else{
    bit_del(b, a[b]);
    bit_add(b, c);
    a[b]=c;
   }
  }
 }
 return 0;
}

3.按值建线段树套平衡树 O(n*log^2n) 500ms

这种做法跟第二种刚好相反，线段树是按值建的，节点[l,r]是指满足值>=l && <=r。平衡树维护的是数对应的数组下标。先将所有可能用到的值（包含初始值和修改的值）读入，然后离散化建立线段树，对于a[i]（离散化后的）,找到所有包含a[i]也就是l<=a[i]<=r的区间节点，将i插入到对应的平衡树中。

查询[ll,rr]的第k大的时候，对于线段树区间[l,r]，先查询左孩子[l,mid]中的平衡树查找在[ll,rr]范围内的数有cnt个，假如cnt<=k，则直接递归到左孩子。cnt>k，递归到右孩子查询第k-cnt大(因为左孩子已经包含最小的cnt个了）。思想相当于整体二分吧，复杂度O(logn*logn)。

修改和2类似，复杂度O(logn*logn)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=5e4+10;
struct Query
{
    int l, r, k;
    int kind;
};
Query q[maxn];

struct SBT
{
    int left,right,size,key;
    void Init()
    {
        left=right=0;
        size=1;
    }
}tree[20*maxn];
int tot;
void left_rotate(int &x)//左旋
{
    int y=tree[x].right;
    tree[x].right=tree[y].left;
    tree[y].left=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void right_rotate(int &x)//右旋
{
    int y=tree[x].left;
    tree[x].left=tree[y].right;
    tree[y].right=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void maintain(int &x,int flag)
{
    if(flag==0)
    {
        if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)
           right_rotate(x);
        else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)
            left_rotate(tree[x].left),right_rotate(x);
        else return;
    }
    else
    {
        if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)
            left_rotate(x);
        else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)
            right_rotate(tree[x].right),left_rotate(x);
        else return;
    }
    maintain(tree[x].left,0);
    maintain(tree[x].right,1);
    maintain(x,0);
    maintain(x,1);
}
//插入元素，相同元素放在右子树中
void insert(int &x,int key)
{
    if(x==0)
    {
        x=++tot;
        tree[x].Init();
        tree[x].key=key;
    }
    else
    {
        tree[x].size++;
        if(key<tree[x].key)insert(tree[x].left,key);
        else insert(tree[x].right,key);
        maintain(x,key>=tree[x].key);
    }
}
//删除key值的元素
int del(int &x,int key)
{
    if(!x)return 0;
    tree[x].size--;
    if(key==tree[x].key || (key<tree[x].key&&tree[x].left==0)
       || (key>tree[x].key&&tree[x].right==0))
    {
        if(tree[x].left && tree[x].right)
        {
            int p=del(tree[x].left,key+1);
            tree[x].key=tree[p].key;
            return p;
        }
        else
        {
            int p=x;
            x=tree[x].left+tree[x].right;
            return p;
        }
    }
    else return del(key<tree[x].key?tree[x].left:tree[x].right,key);
}

//查询<=k的元素有多少个
int get_kth(int &x,int k)
{
    if(!x) return 0;
    if(k<tree[x].key)
        return get_kth(tree[x].left, k);
    else
        return 1+tree[tree[x].left].size+get_kth(tree[x].right, k);
}

int n,m;
int a[maxn];
int h[2*maxn];
int root[4*maxn];
#define getc int m=(l+r)>>1, lc=rt<<1, rc=rt<<1|1;
void seg_insert(int rt, int l, int r, int p, int v)
{
    insert(root[rt], v);
    if(l==r)
        return;


    getc;
    if(p<=m)
        seg_insert(lc, l, m, p, v);
    else seg_insert(rc, m+1, r, p, v);
}

void seg_del(int rt, int l, int r, int p, int v)
{
    del(root[rt], v);
    if(l==r)
        return;

    getc;
    if(p<=m)
        seg_del(lc, l, m, p, v);
    else seg_del(rc, m+1, r, p, v);
}

int query(int rt, int l, int r, int ll, int rr, int k)
{
    if(l==r)
        return l;

    getc;
    int cnt=get_kth(root[lc], rr)-get_kth(root[lc],ll-1);
    if(cnt>=k)
        return query(lc, l, m, ll, rr, k);
    else return query(rc, m+1, r, ll, rr, k-cnt);
}


int num=0;
void init()
{
 tot=0;
 memset(root, 0, sizeof(root));
 tree[0].Init(); tree[0].size=0;
    memset(root, 0, sizeof(root));
    scanf("%d", &m);
    num=0;
    for(int i=1; i<=n; i++){
        scanf("%d", a+i);
        h[num++]=a[i];
    }

    for(int i=0; i<m; i++){
        char s[5];
        scanf("%s%d%d", s, &q[i].l, &q[i].r);
        if(s[0]=='Q') q[i].kind=2;
        else q[i].kind=1;
        if(q[i].kind==2)
            scanf("%d", &q[i].k);
        else
            h[num++]=q[i].r;
    }

    sort(h,h+num);
    num=unique(h, h+num)-h;
    for(int i=1; i<=n; i++) a[i]=lower_bound(h, h+num, a[i])-h+1;
    for(int i=0; i<m; i++)
        if(q[i].kind==1)q[i].r=lower_bound(h, h+num, q[i].r)-h+1;

    for(int i=1; i<=n; i++){
        seg_insert(1, 1, num, a[i], i);
    }
}

int main()
{
 int t;
 cin>>t;
 while(t--&&cin>>n){
        init();
        for(int i=0; i<m; i++){
            if(q[i].kind==1){
                seg_del(1, 1, num, a[q[i].l], q[i].l);
                seg_insert(1, 1, num, q[i].r, q[i].l);
                a[q[i].l]=q[i].r;
            }
            else{
                int ans=query(1, 1, num, q[i].l, q[i].r, q[i].k);
                printf("%d\n", h[ans-1]);
            }
        }
    }
 return 0;
}

上面三种做法一种比一种快，但是代码也越来越复杂。。。。

还有两种做法，但是还没学会。。。树状数组套主席树和cdq分治也可以做，cdq分治应该是时间和空间都最优的