题目描述

在一条 $R$ 河流域，繁衍着一个古老的名族 $Z$。

他们世代沿河而居，也在河边发展出了璀璨的文明。

$Z$ 族在 $R$ 河沿岸修建了很多建筑，最近，他们热衷攀比起来。

他们总是在比谁的建筑建得最奇特。

幸好 Z 族人对奇特的理解都差不多，他们很快给每栋建筑都打了分，这样评选谁最奇特就轻而易举了。

于是，根据分值，大家很快评出了最奇特的建筑，称为大奇迹。

后来他们又陆续评选了第二奇特、第二奇特、……、第七奇特的建筑，依次称为第二大奇迹、第三大奇迹、……、第七大奇迹。

最近，他们开始评选第八奇特的建筑，准备命名为第八大奇迹。

在评选中，他们遇到了一些问题。

首先，$Z$ 族一直在发展，有的建筑被拆除又建了新的建筑，新建筑的奇特值和原建筑不一样，这使得评选不那么容易了。

其次，$Z$ 族的每个人所生活的范围可能不一样，他们见过的建筑并不是所有的建筑，他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。

$Z$ 族首领最近很头疼这个问题，他害怕因为意见不一致导致 $Z$ 族发生分歧。

他找到你，他想先了解一下，民众自己认为的奇迹是怎样的。

现在告诉在 $R$ 河周边的建筑的变化情况，以及在变化过程中一些人的生活范围，请编程求出每个人认为的第八大奇迹的奇特值是多少。

输入格式

输入的第一行包含两个整数 $L,N$，分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑，或者说所有的奇特值为 $0$。

接下来 $N$ 行，每行一条你要处理的信息。

如果信息为 C p x，表示流域中第 $p$ 个位置 $(1≤p≤L)$ 建立了一个建筑，其奇特值为 $x$。如果这个位置原来有建筑，原来的建筑会被拆除。

如果信息为 Q a b，表示有个人生活的范围是河流的第 a 到 b 个位置（包含 $a$ 和 $b$，$a≤b$），这时你要算出这个区间的第八大奇迹的奇特值，并输出。如果找不到第八大奇迹，输出 $0$。

输出格式

对于每个为 $Q$ 的信息，你需要输出一个整数，表示区间中第八大奇迹的奇特值。

题目分析

树状数组+整体二分
带修改区间第k大，主席树不便于修改，此问题离线，而整体二分天然带修改，并且复杂度也很优秀$O(nlog^2n)$

当然也可以用树套树：
①下标线段树套值域线段树需要二分答案，由于多一个二分答案复杂度3个log
②值域线段树套下标平衡树求答案时可以在值域线段树上二分答案复杂度2个log
详细可参考我之前的博客树套树 我永远不想再写树套树

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
int n,L;
struct node
{
    int op,x,y,k;
    int id;
}q[N],rq[N],lq[N];
int ans[N];
int tree[N];
int now[N];
int lowbit(int x)
{
    return x&-x;
}
void change(int k,int x)
{
    for(;k<=L;k+=lowbit(k)) tree[k]+=x;
}
int query(int k)
{
    int res=0;
    for(;k;k-=lowbit(k)) res+=tree[k];
    return res;
}
void solve(int vl,int vr,int ql,int qr)
{
    if(ql>qr) return;
    if(vl==vr)
    {
        for(int i=ql;i<=qr;i++)
            if(q[i].op==2) ans[q[i].id]=vl;
        return;
    }
    int mid=vl+vr>>1;
    int l=0,r=0;
    for(int i=ql;i<=qr;i++)
    {
        if(q[i].op==1)
        {
            if(q[i].y<=mid) 
                lq[++l]=q[i];
            else 
                change(q[i].x,q[i].k),rq[++r]=q[i];
        }
        else
        {
            int tmp=query(q[i].y)-query(q[i].x-1);
            if(q[i].k<=tmp) 
                rq[++r]=q[i];
            else 
                q[i].k-=tmp,lq[++l]=q[i];
        }
    }
    for(int i=ql;i<=qr;i++)
        if(q[i].op==1&&q[i].y>mid)
            change(q[i].x,-q[i].k);
    for(int i=1;i<=l;i++) q[ql+i-1]=lq[i];
    for(int i=1;i<=r;i++) q[ql+l+i-1]=rq[i];
    solve(vl,mid,ql,ql+l-1);
    solve(mid+1,vr,ql+l,qr);
}
int main()
{
    cin>>L>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        ans[i]=-1;
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='C')
        {
            if(now[x])
            {
                q[++cnt]={1,x,now[x],-1};
                q[++cnt]={1,x,y,1};
                now[x]=y;
            }
            else
            {
                q[++cnt]={1,x,y,1};
                now[x]=y;
            }
        }
        else 
            q[++cnt]={2,x,y,8,i};
    }
    solve(0,1e9,1,cnt);
    for(int i=1;i<=n;i++)
        if(ans[i]!=-1) cout<<ans[i]<<'\n';
    return 0;
}

要加油哦~