[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)

发布于 2018-04-17  84 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)

Description

给定一个含有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继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Tag

树套树,树状数组,线段树

解决思路

如果是静态的化,就是主席树处理了。但由于有修改操作,如果用前缀和维护的话,查询是\(O(logn)\),但修改就是\(O(n)\)的了。
考虑一种更加均衡的前缀和的查询姿势。我们知道,树状数组的查询和修改都是\(O(logn)\)的,复杂度较均衡。那么可以用树状数组套值域线段树的方式来维护前缀和。

代码

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

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lowbit(x) ((x)&(-(x)))
#define find(x) (lower_bound(&Num[1],&Num[numcnt+1],x)-Num)

const int maxN=30010;
const int maxBit=15;
const int inf=2147483647;

class SegmentData
{
public:
    int cnt;
    int ls,rs;
};

class Question
{
public:
    char opt;
    int a,b,c;
};

int n,m,nodecnt;
int Arr[maxN],root[maxN];
int numcnt=0,Num[maxN];
SegmentData S[maxN*400];
Question Q[maxN];
int rA[maxBit],rB[maxBit],cnt1,cnt2;

void Insert(int pos,int key,int opt);
void Modify(int &now,int l,int r,int pos,int key);
int Query(int l,int r,int kth);

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&Arr[i]);
        Num[++numcnt]=Arr[i];
    }
    for (int i=1;i<=m;i++)
    {
        Q[i].opt=getchar();
        while ((Q[i].opt!='Q')&&(Q[i].opt!='C')) Q[i].opt=getchar();
        if (Q[i].opt=='Q') scanf("%d%d%d",&Q[i].a,&Q[i].b,&Q[i].c);
        if (Q[i].opt=='C')
        {
            scanf("%d%d",&Q[i].a,&Q[i].b);
            Num[++numcnt]=Q[i].b;
        }
    }
    //离散化
    sort(&Num[1],&Num[numcnt+1]);
    numcnt=unique(&Num[1],&Num[numcnt+1])-Num-1;

    for (int i=1;i<=n;i++) Insert(i,find(Arr[i]),1);//初始化
    for (int i=1;i<=m;i++)
        if (Q[i].opt=='Q')
        {
            cnt1=0;cnt2=0;//先分解成log个位置,方便查询
            for (int x=Q[i].a-1;x;x-=lowbit(x)) rA[++cnt1]=root[x];
            for (int x=Q[i].b;x;x-=lowbit(x)) rB[++cnt2]=root[x];
            printf("%d\n",Num[Query(1,numcnt,Q[i].c)]);
        }
        else
        {
            Insert(Q[i].a,find(Arr[Q[i].a]),-1);
            Arr[Q[i].a]=Q[i].b;
            Insert(Q[i].a,find(Arr[Q[i].a]),1);
        }
    return 0;
}

void Insert(int pos,int key,int opt)
{
    while (pos<=n)
    {
        Modify(root[pos],1,numcnt,key,opt);
        pos+=lowbit(pos);
    }
    return;
}

void Modify(int &now,int l,int r,int pos,int key)
{
    S[++nodecnt]=S[now];now=nodecnt;
    S[now].cnt+=key;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (pos<=mid) Modify(S[now].ls,l,mid,pos,key);
    else Modify(S[now].rs,mid+1,r,pos,key);
    return;
}

int Query(int l,int r,int kth)//查询
{
    if (l==r) return l;
    int lsize=0;//运用树状数组的优良性质,查询左边值域的个数
    for (int i=1;i<=cnt2;i++) lsize+=S[S[rB[i]].ls].cnt;
    for (int i=1;i<=cnt1;i++) lsize-=S[S[rA[i]].ls].cnt;
    int mid=(l+r)>>1;
    if (lsize>=kth)//分别向左边或右边走
    {
        for (int i=1;i<=cnt1;i++) rA[i]=S[rA[i]].ls;
        for (int i=1;i<=cnt2;i++) rB[i]=S[rB[i]].ls;
        return Query(l,mid,kth);
    }
    else
    {
        for (int i=1;i<=cnt1;i++) rA[i]=S[rA[i]].rs;
        for (int i=1;i<=cnt2;i++) rB[i]=S[rB[i]].rs;
        return Query(mid+1,r,kth-lsize);
    }
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)


HNCJ OIer