[BZOJ1901] Dynamic Rankings, 트리 세트 주석 트리

Time: 2016.05.09 Author:xiaoyimi 전재 주명 출처 감사합니다
전송문(권한)
문제면 1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 6678 Solved: 2777 [Submit][Status][Discuss] 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 jk 또는 C i t Q i jk(i, j, k는 숫자, 1≤i ≤ j≤ n, 1≤ k≤ j-i+1)는 문의 지령을 표시하고, a[i], a[i+1]......a[j]에서 k가 작은 수를 묻는다.Cit(1≤i≤n, 0≤t≤10^9)는 a[i]를 t로 바꾸는 것을 의미한다.
Input
매번 질문할 때마다, 너는 그의 답안을 출력해야 한다. 모든 출력은 단독 줄을 차지한다.
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
HINT
20%의 데이터 중 m, n≤100;40%의 데이터 중 m, n≤1000;100% 데이터 중 m, n≤10000.
사고방식: 나무 수조 세트 주석 나무는 접두사로 나무를 세울지 세트로 나무를 세울지 고민을 많이 했다. 작은 공룡, DaD3zZ와 오랫동안 토론을 했는데 (쓸모없는 것을 꼬집었다는 비판을 받았다) 여러 사람의 모델을 봐도 기분이 좋지 않았다. 결국 황 선배는 비교적 편안했다. 주의했다. 매번의 수정은 사실상 주석 나무를 새로 만들었다.따라서 서열에 대응하는 요소를 대표하는 주석 트리도 끊임없이 업데이트되고 있기 때문에 각 요소가 대응하는 주석 트리의 루트 코드를 실시간으로 기록하는 그룹을 만들어야 한다.

#include<bits/stdc++.h>
#define M 20004
#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]
#define low(x) (x&(-x))
using namespace std;
int n,m,tot,cnt;
int c[M>>1],ID[M],S1[M],S2[M],root[M];
struct Ask
{
    int x,y,k;
    bool opt;
}q[M>>1];
struct disc
{
    int data,id;
    bool operator <(const disc other)const
    {
        return data<other.data;
    } 
}b[M];
struct Chairman_tree
{
    int siz,ch[2];
}a[M*250];
int build(int now,int L,int R,int k,int val)
{
    int rt=++cnt;
    a[rt].siz=a[now].siz+k;
    ls(rt)=ls(now);rs(rt)=rs(now);
    if (L==R) return rt;
    int mid=(L+R)>>1;
    if (mid>=val)
        ls(rt)=build(ls(now),L,mid,k,val);
    else
        rs(rt)=build(rs(now),mid+1,R,k,val);
    return rt;
}
int get(int begin,int end,int k)
{
    if (begin==end) return end;
    int mid=(begin+end)>>1,t=0;
    for (int i=1;i<=S1[0];i++) t-=a[ls(S1[i])].siz;
    for (int i=1;i<=S2[0];i++) t+=a[ls(S2[i])].siz;
    if (k<=t)
    {
        for (int i=1;i<=S1[0];i++) S1[i]=ls(S1[i]);
        for (int i=1;i<=S2[0];i++) S2[i]=ls(S2[i]);
        return get(begin,mid,k);
    }
    else
    {
        for (int i=1;i<=S1[0];i++) S1[i]=rs(S1[i]);
        for (int i=1;i<=S2[0];i++) S2[i]=rs(S2[i]);
        return get(mid+1,end,k-t);
    }
}
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",c+i),
        b[i].id=i,b[i].data=c[i];
    int x,y;
    tot=n;
    for (int i=1;i<=m;i++)
    {
        char ch=getchar();
        while (ch!='Q'&&ch!='C') ch=getchar();
        scanf("%d%d",&q[i].x,&q[i].y);
        if (ch=='C')
            q[i].opt=1,
            b[++tot].id=i+n,b[tot].data=q[i].y;
        else scanf("%d",&q[i].k);
    }
    sort(b+1,b+tot+1);
    for (int i=1;i<=tot;i++)
    {
        ID[i]=b[i].data;
        if (b[i].id>n) q[b[i].id-n].y=i;
        else c[b[i].id]=i;
    }
    root[0]=++cnt;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j+=low(j))
            root[j]=build(root[j],1,tot,1,c[i]);
    for (int i=1;i<=m;i++)
    {
        if (!q[i].opt)
        {
            S1[0]=0;S2[0]=0;
            for (int j=q[i].x-1;j;j-=low(j)) S1[++S1[0]]=root[j];
            for (int j=q[i].y;j;j-=low(j)) S2[++S2[0]]=root[j];
            printf("%d
",ID[get(1,tot,q[i].k)]);
        }
        else
        {
            for (int j=q[i].x;j<=n;j+=low(j))
                root[j]=build(root[j],1,tot,-1,c[q[i].x]);
            c[q[i].x]=q[i].y;
            for (int j=q[i].x;j<=n;j+=low(j))
                root[j]=build(root[j],1,tot,1,c[q[i].x]);
        }
    }
}