BZOJ 1901 Dynamic Rankings

题 http://www.lydsy.com/JudgeOnline/problem.php?id=1901

可离线做的带修改的k大数，我写的整体二分

据说能用树状数组套主席树，下次试一试

具体的话把修改拆成两个操作，加上现在的减去之前的

然后整体二分，BIT里面存的是所处理区间内比mid小的数的数量

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x7f7f7f7f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////


int n,m,cnt,tot,tott,temp[33333],ans[33333],a[33333];
bool mark[33333];
char ch;
////////BIT///////
#define lowbit(x) (x&(-x))
int c[33333];
void change(int pos,int x)
{
    while (pos<=n)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
int query(int pos)
{
    int res=0;
    while (pos)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
}
//////////////////
struct QQ
{
    int x,y,op,k,id,cur;
}Q[33333],tempp[33333];
void solve(int L,int R,int l,int r) //L R q l r ans
{
    if (L>R) return;
    if (l==r)
    {
        rep(i,L,R) if (Q[i].op==1) ans[Q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    rep(i,L,R)
    {
        if (Q[i].op==1) temp[i]=query(Q[i].y)-query(Q[i].x-1);
        else if (Q[i].op==2&&Q[i].y<=mid) change(Q[i].x,1);
        else if (Q[i].op==3&&Q[i].y<=mid) change(Q[i].x,-1);
    }
    rep(i,L,R)
    {
        if (Q[i].op==2&&Q[i].y<=mid) change(Q[i].x,-1);
        else if (Q[i].op==3&&Q[i].y<=mid) change(Q[i].x,1);
    }
    int cnt=0;
    rep(i,L,R)
    {
        if (Q[i].op==1)
        {
            if (Q[i].cur+temp[i]>=Q[i].k)
            {
                mark[i]=1;
                cnt++;
            }
            else
            {
                Q[i].cur+=temp[i];
                mark[i]=0;
            }
        }
        else
        {
            if (Q[i].y<=mid)
            {
                cnt++;
                mark[i]=1;
            }
            else mark[i]=0;
        }
    }
    int L1=L-1,L2=L+cnt-1;
    rep(i,L,R) if (!mark[i]) tempp[++L2]=Q[i]; else tempp[++L1]=Q[i];
    rep(i,L,R) Q[i]=tempp[i];
    solve(L,L1,l,mid);
    solve(L1+1,R,mid+1,r);
}
int main()
{
    read(n,m);
    rep(i,1,n)
    {
        read(a[i]);
        Q[++tot].op=2;
        Q[tot].x=i;
        Q[tot].y=a[i];
    }
    rep(i,1,m)
    {
        ch=getchar();
        while (ch!=’Q’&&ch!=’C’) ch=getchar();
        tot++;
        read(Q[tot].x,Q[tot].y);
        if (ch==’Q’)
        {
            read(Q[tot].k);
            Q[tot].op=1;
            Q[tot].id=++tott;
        }
        if (ch==’C’)
        {
            Q[tot].op=2;
            ++tot;
            Q[tot].x=Q[tot-1].x;
            Q[tot].y=a[Q[tot].x];
            Q[tot].op=3;
            a[Q[tot].x]=Q[tot].y;
        }
    }
    solve(1,tot,0,inf);
    rep(i,1,tott) printf("%d\n",ans[i]);
    return 0;
}

我才不会告诉你这个是wa的，但是我怎么也找不出哪里错了啊，如果好心人看出来了望提醒谢谢