题解 P2617 【Dynamic Ranking】

· · 题解

这道题目是一道整体二分的好题

想必做这道题目的人都知道二分答案，而整体二分相当于一次性二分所有答案，很显然可以发现，对于这一道题目而言，时间复杂度是m log 1e9，是可以接受的

对于每一次修改，我们可以考虑：减去原来的值，加上修改成的值，包括读入原先序列ai也可以是如此。

还有一个要点是统计mb的排名。最暴力的方式是开一个计数表去一个个数过来，但是我们可以想一下，比如mb=50，前面有两个数，一个a1=4，一个a2=49，那么这两个数的值是有必要考虑的吗？显然没有必要，因为它们都比50小，因此我们可以把它们都当成两个值是1的标记，接下来统计排名只要计算前缀和就可以了。因此这道题目可以用树状数组或者线段树进行维护。

还有一个小要点，就是对于脏数据的处理。脏数据也就是会对计算结果产生影响的数据。对于本题而言，值大于等于mb的操作在[lb,mb)中是没有影响的，但是在[mb,ub)的操作中，值小于mb的操作会产生影响，但是显然如果减去一个k，那么就可以消除这个影响。

其实这个程序有很有趣的一点。这道题的原题是zoj2112，在大学OJ里面是有多组数据的。这个程序几乎可以不用初始化直接提交过去，原因就是每一组数据整体二分之后，所有参与的数组的值全部都空了。具体可以自己证明一下

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct op
{
    int type; 
    //type==0 Change i means position; j means ispositive; k means the number after change
    //type==1 Query i means left; r means right; k means kth-number
    int i,j,k;
    int id;
};

int n,m,a[10050],ans[10050],f[50050];

vector <op> q;

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int k)
{
    while (x<=n)
    {
        f[x]+=k;
        x+=lowbit(x);
    }
}

int query(int k)
{
    int ans=0;
    while (k>0)
    {
        ans+=f[k];
        k-=lowbit(k);
    }
    return ans;
}

void solve(int lb,int ub,vector <op> &q)
{
    vector <op> Left;
    vector <op> Right;
    int mb=(lb+ub)>>1;
    //cout << lb << " " << mb << " " << ub << endl;
    if (ub-lb==1)
    { 
        for (int i=0;i<q.size();i++)
        {
            if (q[i].type==1)
                ans[q[i].id]=lb;
        }
        return;
    }
    else if (q.empty())
        return;
    for (int i=0;i<q.size();i++)
    {
        op tmp=q[i];
        if (tmp.type==0)
        {
            if (tmp.k<mb)
            {
                add(tmp.i,tmp.j);//i:pos j:num
                Left.push_back(tmp);
            }
            else
                Right.push_back(tmp);
        }
        else        
        {
            int kth=query(tmp.j)-query(tmp.i-1);
            if (kth>=tmp.k)
                Left.push_back(tmp);
            else
            {
                tmp.k-=kth;
                Right.push_back(tmp);
            }
        }
    }
    for (int x=0;x<Left.size();x++)
        if(Left[x].type==0)
            add(Left[x].i,-Left[x].j);
    solve(lb,mb,Left);
    solve(mb,ub,Right);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        op tmp={0,i,1,a[i]};
        q.push_back(tmp);
    }
    for (int x=0;x<m;x++)
    {
        char cmd;
        int i;
        scanf("%s%d",&cmd,&i);
        if (cmd=='C')
        {
            int t;
            scanf("%d",&t);
            op tmp={0,i,-1,a[i],0};
            q.push_back(tmp);
            a[i]=t;
            tmp={0,i,1,t,0};
            q.push_back(tmp);
        }
        else
        {
            int j,k;
            scanf("%d%d",&j,&k);
            op tmp={1,i,j,k,x};
            q.push_back(tmp);
        }
    }
    for (int i=0;i<m;i++)
        ans[i]=-1;
    solve(0,1e9,q);
    for (int i=0;i<m;i++)
        if (ans[i]!=-1)
            printf("%d\n",ans[i]);
    return 0;
}

然而整体二分还是比树套树慢，但是整体二分的优势就是好写。特别对于我这种弱省蒟蒻而言。