我知道ls想让我写一个树套树，可是。。
用O(n)的kth算法可以AC为什么写树套树呢？
```c++
测试数据 #0: Accepted, time = 250 ms, mem = 948 KiB, score = 10
测试数据 #1: Accepted, time = 500 ms, mem = 948 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 952 KiB, score = 10
测试数据 #3: Accepted, time = 312 ms, mem = 948 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 948 KiB, score = 10
测试数据 #5: Accepted, time = 500 ms, mem = 952 KiB, score = 10
测试数据 #6: Accepted, time = 515 ms, mem = 948 KiB, score = 10
测试数据 #7: Accepted, time = 531 ms, mem = 948 KiB, score = 10
测试数据 #8: Accepted, time = 656 ms, mem = 952 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 952 KiB, score = 10

Accepted, time = 3575 ms, mem = 952 KiB, score = 100

c++
#include <bits/stdc++.h>
using namespace std;

int n, q, t;
char c;
int arr[50005], a[50005];

int read()
{
int a = 0, c;
do c = getchar(); while (!isdigit(c));
while (isdigit(c)) {
a = a*10+c-'0';
c = getchar();
}
return a;
}

char get()
{
char c;
while (!isalpha(c))
c = getchar();
return c;
}

int kth(int l, int r, int k)
{
for (int i = l; i <= r; i++) arr[i] = a[i];
while (1) {
//cout << l << " " << r << " " << k << endl;
if (l == r) return arr[l];
swap(arr[l], arr[(l+r)>>1]);
int m = l;
for (int i = l+1; i <= r; i++)
if (arr[i] < arr[l])
swap(arr[++m], arr[i]);
swap(arr[l], arr[m]);
// cout << l << " " << r << " " << k << " " << m << endl;
if (k == m) return arr[k];
else if (k <= m) r = m-1;
else l = m+1;
}
}
int main()
{
n = read(); q = read();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= q; i++) {
c = get();
int a1, b, d;
if (c == 'Q') {
a1 = read(); b = read(); d = read();
if (b < a1) swap(a1, b);
printf("%d\n", kth(a1, b, a1+d-1));
} else {
a1 = read(); b = read();
a[a1] = b;
}
}
return 0;
}

Markdown

#include <bits/stdc++.h>

using namespace std;
const int N = 50010;
typedef unsigned long ul;
typedef int seg[90 * N];
typedef int arr[N];
typedef pair<int, int> pii;
seg lson, rson, c;
arr a, bit;
vector<int> x;
int tot, n, m, xsiz;

struct T {
    int p, val, l, r;
    char t;
} q[N];

void init_hash() {
    sort(x.begin(), x.end());
    auto en = unique(x.begin(), x.end());
    xsiz = (int) (en - x.begin());
    x.resize((ul) xsiz);
}

int hafn(int val) {
    return (int) (lower_bound(x.begin(), x.end(), val) - x.begin()) + 1;
}

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

void segins(int &i, int l, int r, int p, int del) {
    if (i == 0)
        i = [&tot]() {
            int res = ++tot;
            lson[res] = rson[res] = c[res] = 0;
            return res;
        }();
    c[i] += del;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) segins(lson[i], l, mid, p, del);
    else segins(rson[i], mid + 1, r, p, del);
}

void bitchg(int p, int val, int del) {
    while (p <= n) {
        segins(bit[p], 1, xsiz, val, del);
        p += lowbit(p);
    }
}

int bitask(int l, int r, int k) {
    vector<pii> v;
    auto f = [&v](int x, int del) {
        while (x) {
            v.push_back(pii(bit[x], del));
            x -= lowbit(x);
        }
    };
    auto turn = [&v](int dir) {
        transform(v.begin(), v.end(), v.begin(), [dir](pii x) -> pii {
            return dir ? pii(rson[x.first], x.second) : pii(lson[x.first], x.second);
        });
    };
    auto getleft = [&v]() {
        int tot = 0;
        for_each(v.begin(), v.end(), [&tot](pii x) { tot += c[lson[x.first]] * x.second; });
        return tot;
    };
    f(l - 1, -1);
    f(r, 1);
    l = 1;
    r = xsiz;
    while (l < r) {
        int mid = l + r >> 1, tmp = getleft();
        if (k <= tmp) {
            r = mid;
            turn(0);
        } else {
            l = mid + 1;
            k = k - tmp;
            turn(1);
        }
    }
    return l;
}

int main() {
    //int t;
    //cin >> t;
    //while (t--) {
        x.clear();
        tot = 0;
        cin >> n >> m;
        memset(bit, 0, sizeof(int) * (n + 1));
        for (int i = 1; i <= n; i++) scanf("%d", a + i), x.push_back(a[i]);
        for (int i = 1; i <= m; i++) {
            getchar();
            q[i].t = (char) getchar();
            if (q[i].t == 'C') {
                scanf("%d%d", &q[i].p, &q[i].val);
                x.push_back(q[i].val);
            } else scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].val);
        }
        init_hash();
        transform(a + 1, a + n + 1, a + 1, [](int x) { return hafn(x); });
        for (int i = 1; i <= n; i++) bitchg(i, a[i], 1);
        for (int i = 1; i <= m; i++)
            if (q[i].t == 'C') q[i].val = hafn(q[i].val);
        for (int j = 1; j <= m; j++) {
            auto i = q[j];
            if (i.t == 'C') {
                bitchg(i.p, a[i.p], -1);
                a[i.p] = i.val;
                bitchg(i.p, a[i.p], 1);
            } else {
                int id = bitask(i.l, i.r, i.val);
                printf("%d\n", x[id - 1]);
            }
        }
    //}
    return 0;
}

树状数组套线段数哦

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
//平衡树套线段树 
const int maxst=200005,maxbbt=1000005;
struct bTree {
    int father,child[2]; //0左儿子 1右儿子
    int key,size; //key为结点属性 size为子树大小
    bTree() {}
    bTree(int fa,int lc,int rc,int data,int sz):father(fa),key(data),size(sz) {
        child[0]=lc,child[1]=rc;
    }
};
struct Splay {
    bTree tree[maxbbt];
    void init() {
        memset(tree,0,sizeof(tree));
    }
    void clear(int index) {
        tree[index]=bTree(0,0,0,0,0);
    }
    int checkson(int index) { //判断是父亲的左儿子还是右儿子
        return tree[tree[index].father].child[1]==index;
    }
    void update(int index) { //更新size
        if(!index)return;
        tree[index].size=1;
        if(tree[index].child[0])tree[index].size+=tree[tree[index].child[0]].size;
        if(tree[index].child[1])tree[index].size+=tree[tree[index].child[1]].size;
    }
    void rotate(int index) { //旋转到根
        int father=tree[index].father,grandpa=tree[father].father,side=checkson(index);
        tree[father].child[side]=tree[index].child[side^1];
        tree[tree[father].child[side]].father=father;
        tree[father].father=index;
        tree[index].child[side^1]=father;
        tree[index].father=grandpa;
        if(grandpa)tree[grandpa].child[tree[grandpa].child[1]==father]=index;
        update(father);
        update(index);
    }
    void splay(int& root,int index) {
        if(index==root)return;
        for(int father; (father=tree[index].father); rotate(index)) //基本旋转
            if(tree[father].father)rotate((checkson(index)==checkson(father))?father:index); //附加旋转
        root=index;
    }
    void insert(int& root,int index,int v) {
        if(!root) {
            root=index;
            tree[index]=bTree(0,0,0,v,1);
            return;
        }
        int now=root,father=0;
        while(true) {
            father=now; //保存父亲
            now=tree[now].child[tree[now].key<v]; //往哪边走
            if(!now) {
                tree[index]=bTree(father,0,0,v,1);
                tree[father].child[tree[father].key<v]=index;
                update(father);
                splay(root,index);
                break;
            }
        }
    }
    void remove(int& root) { //删除根 
        if(!tree[root].child[0]||!tree[root].child[1]) { //只有左右儿子 
            int oldroot=root;
            root=tree[root].child[tree[root].child[0]==0];
            tree[root].father=0;
            clear(oldroot);
            return; 
        }
        int pre=inline_pre_next(root,0),oldroot=root;
        splay(root,pre); //伸展前驱 
        tree[tree[oldroot].child[1]].father=root; //将原根右子树接到根上（相当于删除了）
        tree[root].child[1]=tree[oldroot].child[1];
        clear(oldroot);
        update(root); 
    }
    int inline_pre_next(int& root,int bj) {
        int now=tree[root].child[bj];
        while(tree[now].child[bj^1])now=tree[now].child[bj^1];
        return now;
    }
    int find(int& root,int rank) { //在root为根的树中找到排名为rank的点，返回下标
        int now=root;
        while(true) {
            if(rank<=0||now<=0)return -1; //找不到 
            if(tree[now].child[0]&&rank<=tree[tree[now].child[0]].size)now=tree[now].child[0];
            else {
                int tmp=(tree[now].child[0]?tree[tree[now].child[0]].size:0)+1;
                if(rank<=tmp)return now;
                rank-=tmp;
                now=tree[now].child[1];
            }
        }
    }
} bbt;
int n;
struct sTree {
    int left,right,root; //记录对应平衡树编号 
    sTree() {}
    sTree(int l,int r,int roo):left(l),right(r),root(roo) {}
};
struct Segment_Tree {
    sTree tree[maxst];
    void init() {
        memset(tree,0,sizeof(tree));
        bbt.init();
    }
    void build(int index,int depth,int Left,int Right,int* a) {
        tree[index]=sTree(Left,Right,0);
        if(Left==Right) { //叶子节点 
            bbt.insert(tree[index].root,(depth-1)*n+Left,a[Left]); //对应编号（类似分层图）
            return; 
        }
        int mid=(Left+Right)>>1;
        build(index<<1,depth+1,Left,mid,a);
        build((index<<1)|1,depth+1,mid+1,Right,a);
        for(int i=Left; i<=Right; i++)bbt.insert(tree[index].root,(depth-1)*n+i,a[i]); //路径上的都要建 
    }
    void modify(int index,int depth,int pos,int v) {
        int M=(depth-1)*n+pos; //计算出平衡树中编号
        bbt.splay(tree[index].root,M);
        bbt.remove(tree[index].root);
        bbt.insert(tree[index].root,M,v);
        int l=tree[index].left,r=tree[index].right;
        if(l==r)return;
        int mid=(l+r)>>1;
        if(pos<=mid)modify(index<<1,depth+1,pos,v);
        else modify((index<<1)|1,depth+1,pos,v);
    }
    int query(int index,int Left,int Right,int v) { //统计比v小的个数 
        if(tree[index].right<Left||tree[index].left>Right)return 0;
        if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 
            int Now=tree[index].root,sum=0;
            while(Now) {
                if(bbt.tree[Now].key<v)sum+=bbt.tree[bbt.tree[Now].child[0]].size+1;
                Now=bbt.tree[Now].child[bbt.tree[Now].key<v];
            }
            return sum;
        }
        return query(index<<1,Left,Right,v)+query((index<<1)|1,Left,Right,v);
    }
    int find(int Left,int Right,int rank) { //寻找第rank小的数 
        int Now=tree[1].root,ans=0;
        if(Left==1&&Right==n)return bbt.tree[bbt.find(Now,rank)].key; //特殊情况
        while(Now) { //二分查找 
            if(query(1,Left,Right,bbt.tree[Now].key)<=rank-1) {
                ans=bbt.tree[Now].key;
                Now=bbt.tree[Now].child[1];
            } else Now=bbt.tree[Now].child[0];
        }
        return ans;
    }
} st;
int m,a[50005];
int main() {
    n=Get_Int();
    m=Get_Int();
    st.init();
    for(int i=1; i<=n; i++)a[i]=Get_Int();
    st.build(1,1,1,n,a);
    for(int i=1; i<=m; i++) {
        char order='a';
        while(order!='C'&&order!='Q')order=getchar();
        int x=Get_Int(),y=Get_Int();
        if(order=='Q') {
            int val=Get_Int();
            printf("%d\n",st.find(x,y,val));
        } else st.modify(1,1,x,y);
    }
    return 0;
}

以此纪念我的第一个树套树：

测试数据 #0: Accepted, time = 250 ms, mem = 21704 KiB, score = 10
测试数据 #1: Accepted, time = 359 ms, mem = 21708 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 21708 KiB, score = 10
测试数据 #3: Accepted, time = 296 ms, mem = 21712 KiB, score = 10
测试数据 #4: Accepted, time = 234 ms, mem = 21704 KiB, score = 10
测试数据 #5: Accepted, time = 406 ms, mem = 21708 KiB, score = 10
测试数据 #6: Accepted, time = 437 ms, mem = 21716 KiB, score = 10
测试数据 #7: Accepted, time = 343 ms, mem = 21708 KiB, score = 10
测试数据 #8: Accepted, time = 453 ms, mem = 21704 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 21708 KiB, score = 10
Accepted, time = 2996 ms, mem = 21716 KiB, score = 100

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
//data默认为int类型，如果要进行修改，请定义新的类型，并重载比较运算符
struct DATA{
    int x;
    DATA (int t){
        x=t;
    }
    DATA (){}
};
bool operator < (const DATA a,const DATA b){
    return a.x<b.x;
}
bool operator > (const DATA a,const DATA b){
    return a.x>b.x;
}
bool operator == (const DATA a,const DATA b){
    return a.x==b.x;
}
bool operator != (const DATA a,const DATA b){
    return a.x!=b.x;
}
struct data_class{
    int HASH;
    DATA data;
    data_class(int h,DATA d){
        HASH=h;data=d;
    }
    data_class(){}
};
bool operator < (const data_class a,const data_class b){
    return (a.data<b.data||a.data==b.data&&a.HASH<b.HASH);
}
bool operator > (const data_class a,const data_class b){
    return (a.data>b.data||a.data==b.data&&a.HASH>b.HASH);
}
bool operator == (const data_class a,const data_class b){
    return a.data==b.data&&a.HASH==b.HASH;
}
bool operator >= (const data_class a,const data_class b){
    return a>b||a==b;
}
struct sbt
{
    int left,right,size;
    data_class data;
    sbt(){
        left=right=0;
        size=0;
    }
};
sbt tree[1000000];
int top;
struct SBT{
public:
    int root;
    SBT(){
        root=0;
    }
    int datacmp(const data_class a,const data_class b){
        if (a.data<b.data) return 1;
        if (a.data>b.data) return -1;
        return 0;
    }
    //如果要维护父亲节点和儿子节点的其他域值则修改adapt
    void adapt(int x){
        tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    }
    DATA getDATA(int n){
        return tree[n].data.data;
    }
    void left_rot(int &x){
        int y=tree[x].right;
        tree[x].right=tree[y].left;
        tree[y].left=x;
        tree[y].size=tree[x].size;
        adapt(x);
        x=y;
    }
    void right_rot(int &x){
        int y=tree[x].left;
        tree[x].left=tree[y].right;
        tree[y].right=x;
        tree[y].size=tree[x].size;
        adapt(x);
        x=y;
    }
    void Maintain(int &x,bool flag){
        if (!flag){
            if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size)
                right_rot(x);
            else
            if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size)
                left_rot(tree[x].left),right_rot(x);
            else
            return;
        }
        else{
            if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size)
                left_rot(x);
            else
            if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size)
                right_rot(tree[x].right),left_rot(x);
            else
            return;
        }
        Maintain(tree[x].left,0);
        Maintain(tree[x].right,1);
        Maintain(x,1);
        Maintain(x,0);
    }
    void insert(int &x,data_class data){
        if (x==0){
            x=++top;
            tree[x].size=1;
            tree[x].left=tree[x].right=0;
            tree[x].data=data;
        }
        else{
            tree[x].size++;
            if (data<tree[x].data) insert(tree[x].left,data);
            else insert(tree[x].right,data);
            Maintain(x,data>=tree[x].data);
        }
    }
    int remove(int fa,int &x,data_class data){
        if (!x) return 0;
        tree[x].size--;
        if (datacmp(data,tree[x].data)==-1)
            remove(x,tree[x].right,data);
        else
        if (datacmp(data,tree[x].data)==1)
            remove(x,tree[x].left,data);
        else{
            if (tree[x].left!=0&&tree[x].right==0){
                tree[x]=tree[tree[x].left];
                return x;
            }
            else
            if (tree[x].right!=0&&tree[x].left==0){
                tree[x]=tree[tree[x].right];
                return x;
            }
            else
            if (tree[x].left==0&&tree[x].right==0){
                if (root==x) root=0;
                if (fa)
                    if (tree[fa].left==x) tree[fa].left=0;
                    else tree[fa].right=0;
            }
            else{
                int ret=tree[x].right;
                while (tree[ret].left)
                    ret=tree[ret].left;
                tree[x].data=tree[ret].data;
                remove(x,tree[x].right,tree[ret].data);
            }
        }
    }
    data_class select(int &x,int k){
        int r=tree[tree[x].left].size+1;
        if (k<r) return select(tree[x].left,k);
        else
        if (k>r) return select(tree[x].right,k-r);
        else
        return tree[x].data;
    }
    int rank(int &x,data_class data){
        if (x==0) return 0;
        if (data>tree[x].data) return tree[tree[x].left].size+1+rank(tree[x].right,data);
        else
        if (data<tree[x].data) return rank(tree[x].left,data);
        else
        return tree[tree[x].left].size+1;
    }
    //插入一个数
    void Insert(int data){
        insert(root,data_class(top+1,data));
    }
    //删除一个数，在相同的情况下，任意删除其中一个
    void Remove(int data){
        remove(0,root,data_class(0,data));
    }
    //查询第k小的数字
    DATA Select(int k){
        return select(root,k).data;
    }
    //查询比data小（严格）的数字有多少个
    int Rank(int data){
        return rank(root,data_class(-1,data));
    }
    //查找data是否存在
    bool Find(int data){
        if (!root) return 0;
        else {
            int x=root;
            while (tree[x].data.data!=data&&x){
                if (tree[x].data.data<data) x=tree[x].right;
                else x=tree[x].left;
            }
            if (!x) return 0;
            else if (tree[x].data.data==data) return 1;
        }
    }
    //统计data一共有多少个
    int Count(int data){
        bool exi=Find(data);
        if (exi){
            int aaa=Rank(data);
            int bbb=Rank(data+1);
            return bbb-aaa;
        }
        else return 0;
    }
};
struct INTERVAL_DATA{
    int left,right;
    SBT SET;
    INTERVAL_DATA(){
        left=right=0;
    }
};
int st[10000],TOP=-1;
struct INTERVAL_TREE{
    int n;
    INTERVAL_DATA *tree;
    INTERVAL_TREE(int height){
        tree=new INTERVAL_DATA[2<<height];
        n=height;

        int h=0;
        tree[0].left=0;tree[0].right=(1<<n)-1;
        for (int i=0;i<((1<<n)-1);i++){
            if (i>(2<<h)-2) h++;
            tree[i*2+1].left=tree[i].left;
            tree[i*2+2].left=(1<<(n-h-1))|tree[i].left;
            tree[i*2+1].right=tree[i*2+1].left+(1<<(n-h-1))-1;
            tree[i*2+2].right=tree[i*2+2].left+(1<<(n-h-1))-1;
        }
        tree[0].left++;tree[0].right++;
        for (int i=0;i<(1<<n)-1;i++){
            tree[i*2+1].left++;tree[i*2+1].right++;
            tree[i*2+2].left++;tree[i*2+2].right++;
        }
    }
    void add(int index,int x){
        index+=(1<<n)-2;
        while (index){
            tree[index].SET.Insert(x);
            index=(index-1)>>1;
        }
        tree[0].SET.Insert(x);
    }
    void change(int index,int y){
        index+=(1<<n)-2;
        int x=tree[index].SET.getDATA(tree[index].SET.root).x;
        while (index){
            tree[index].SET.Remove(x);
            tree[index].SET.Insert(y);
            index=(index-1)>>1;
        }
        tree[0].SET.Remove(x);
        tree[0].SET.Insert(y);
    }
    void getinterval(int root,int l,int r){
        if (tree[root].left==l&&tree[root].right==r) st[++TOP]=root;
        else {
            int mid=(tree[root].left+tree[root].right)/2;
            if (r<=mid) getinterval(root*2+1,l,r);
            else if (l>mid) getinterval(root*2+2,l,r);
            else {
                getinterval(root*2+1,l,mid);
                getinterval(root*2+2,mid+1,r);
            }
        }
    }
} a(16);
void shownode(int x){
    cout<<tree[x].data.data.x<<' ';
    if (tree[x].left) shownode(tree[x].left);
    if (tree[x].right) shownode(tree[x].right);
}
void show(SBT x){
    shownode(x.root);
    cout<<endl;
}
int getans(int I,int J,int K){
    TOP=-1;
    K--;
    a.getinterval(0,I,J);

    int Max=1000000000,Min=-1,tmp=0,RANK;
    while (Max-Min>1){
        tmp=(Max+Min)/2;
        RANK=0;
        for (int i=0;i<=TOP;i++)
            RANK+=a.tree[st[i]].SET.Rank(tmp);
        if (RANK<=K) Min=tmp;
        else Max=tmp;
    }
    return Min;
}
int main(){
    int n,m,tmp;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&tmp);
        a.add(i,tmp);
    }

    char ord[3];
    int I,J,K;
    for (int i=1;i<=m;i++){
        scanf("%s",ord);
        if (ord[0]=='Q'){
            scanf("%d%d%d",&I,&J,&K);
            cout<<getans(I,J,K)<<endl;
        }
        else {
            scanf("%d%d",&I,&J);
            a.change(I,J);
        }
    }
    return 0;
}

貌似不允许在讨论区发题解（防止剧透？） (。_。)

平方分割：http://www.cnblogs.com/Onlynagesha/p/5355133.html

由于懒得离散化....
树状数组套动态开点的线段树...
不论卡内存还是卡时间都特别紧.......
还好水过了......

PS: 时限是5s?????

Accepted, time = 281 ms, mem = 160984 KiB, score = 10
Accepted, time = 453 ms, mem = 160980 KiB, score = 10
Accepted, time = 78 ms, mem = 160984 KiB, score = 10
Accepted, time = 281 ms, mem = 160984 KiB, score = 10
Accepted, time = 234 ms, mem = 160984 KiB, score = 10
Accepted, time = 468 ms, mem = 160984 KiB, score = 10
Accepted, time = 468 ms, mem = 160980 KiB, score = 10
Accepted, time = 343 ms, mem = 160988 KiB, score = 10
Accepted, time = 468 ms, mem = 160984 KiB, score = 10
Accepted, time = 125 ms, mem = 160988 KiB, score = 10

代码百把行....相当于打个树链剖分...

Code

const int INF=(1<<30)-1;

int n;
struct node*nil;
struct node
{
int v; //total
node*l,*r;
void update()
{ v=l->v+r->v; }
}pool[13000000];
node*nt=pool;
node*newnode()
{
nt->l=nt->r=nil;
nt->v=0;
return nt++;
}

int cp,cv;

//Sub segment trees
struct SegmentTree
{
node*root;

node*Change(node*x,int l=0,int r=INF)
{
if(cp<l || r<cp) return x;
if(x==nil) x=newnode();
if(l==r) { x->v+=cv; return x; }
int mid=avg(l,r);
x->l=Change(x->l,l,mid);
x->r=Change(x->r,mid+1,r);
x->update();
return x;
}

void Set(int p,int v)
{
if(root<pool) root=nil;
cp=p;
cv=v;
root=Change(root);
}
};

//original segment tree
//performed as tree array

#define bt(x) (x&-x)

int a[1000000]; //this array must be stay here....
SegmentTree t[1000000];
void Change(int p,int s,int v) //location of point, value of point, delete or add in.
{ for(int i=p;i<=n;i+=bt(i)) t[i].Set(s,v); }

node*c[1000];
int adt,ct;

int Query(int l,int r,int k) //find the element which is rank k.
{
adt=0;

for(int i=r;i>0;i-=bt(i))
c[adt++]=t[i].root;

ct=adt;
for(int i=l-1;i>0;i-=bt(i))
c[ct++]=t[i].root;

//we perform add when i<adt, and than dec when adt<=i<ct

l=0,r=INF;
while(l!=r)
{
//for(int i=0;i<ct;i++)
//cout<<c[i]<<' '; cout<<endl; cout<<l<<' '<<r<<endl; cout<<endl;

int mid=avg(l,r);
int clv=0; //current node's left node count.

for(int i=0;i<adt;i++)
clv+=c[i]->l->v;
for(int i=adt;i<ct;i++)
clv-=c[i]->l->v;

if(k<=clv) //the element we want find is on the left block
{
for(int i=0;i<ct;i++)
c[i]=c[i]->l;
r=mid;
}
else
{
for(int i=0;i<ct;i++)
c[i]=c[i]->r;
k-=clv;
l=mid+1;
}
}

return l;
}

int q;

int main()
{
nil=newnode();
nil->l=nil->r=nil;
nil->v=0;

n=getint();
q=getint();
for(int i=0;i<n;i++)
Change(i+1,a[i+1]=getint(),1);

for(int i=0;i<q;i++)
{
char c[5];
scanf("%s",c);
if(c[0]=='C')
{
int i=getint();
int v=getint();
Change(i,a[i],-1);
Change(i,a[i]=v,1);
}
else
{
int i=getint();
int j=getint();
int k=getint();
printf("%d\n",Query(i,j,k));
}
}

return 0;
}

主席树随便搞？

线段树套treap也可做
一开始试了一下线段树套Splay，不知道是写萎了还是什么...TLE了很久...

树状数组套主席树：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAXN 50001
#define lowbit(x)(((~(x))+1)&x)
#define MAXM 10001
#define For(i,x) for (int i=x;i;i-=lowbit(i))
#define Rep(i,x) for (int i=x;i<=n;i+=lowbit(i))
#define MAXT 20

void getint(int &t) {
scanf("%d",&t);
}

void putint(int t) {
printf("%d\n",t);
}

struct saver {
int v,t;
} num[MAXN+MAXM];
int R[MAXN+MAXM],C[MAXN+MAXM],RN=0;

bool cmp(saver x,saver y) {
return x.v<y.v;
}

int a[MAXN];
int Query[MAXM][4];
int n,m,V=0;

struct node {
int s;
int left,right;
node () {
s=left=right=0;
}
} Node[MAXN*MAXT*MAXT];

int T[MAXN];
int M=0;

void build(int l,int r,int &t) {
if (!t) t=++M;
if (l==r) return ;
int mid=(l+r)>>1;
build(l,mid,Node[t].left),build(mid+1,r,Node[t].right);
}

void Add(int x,int y,int l,int r,int u,int t) {
Node[t].s=Node[u].s+y;
if (l==r) return ;
int mid=(l+r)>>1;
if (x<=mid) {
Node[t].right=Node[u].right;
Add(x,y,l,mid,Node[u].left, Node[t].left=++M);
} else {
Node[t].left=Node[u].left;
Add(x,y,mid+1,r,Node[u].right,Node[t].right=++M);
}
}

void INIT() {
getint(n),getint(m);
for (int i=0;i++<n;) {
getint(a[i]);
num[++V].v=a[i];
num[V].t=i;
}
for (int i=0;i++<m;) {
int c;
while (1) {
c=getchar();
if (c==int('Q')||c==int('C')) break;
}
if (c==int('Q')) {
Query[i][0]=1;
getint(Query[i][1]),getint(Query[i][2]),getint(Query[i][3]);
} else {
Query[i][1]=0;
getint(Query[i][1]),getint(Query[i][2]);
num[++V].v=Query[i][2];
num[V].t=n+i;
}
}
sort(num+1,num+V+1,cmp);
C[++RN]=num[1].v,R[num[1].t]=1;
for (int i=1;i++<V;) {
if (num[i].v!=num[i-1].v) {
C[++RN]=num[i].v;
}
R[num[i].t]=RN;
}
memset(T,0,sizeof(T));
build(1,RN,T[0]);
for (int i=0;i++<n;) {
int p=T[0];
for (int j=i-lowbit(i);j++<i;) {
Add(R[j],1,1,RN,p,T[i]=++M);
p=T[i];
}
}
}

int t1[MAXT],t2[MAXT];
int n1,n2,sum;

void Solve() {
for (int i=0;i++<m;) {
if (!Query[i][0]) {
int p;
Rep(j,Query[i][1]) {
Add(R[Query[i][1]],-1,1,RN,T[j],p=++M);
T[j]=p;
}
Rep(j,Query[i][1]) {
Add(R[n+i],1,1,RN,T[j],p=++M);
T[j]=p;
}
R[Query[i][1]]=R[n+i];
} else {
n1=n2=0;
For(j,Query[i][2]) t1[++n1]=T[j];
For(j,Query[i][1]-1) t2[++n2]=T[j];
int l=1,r=RN;
while (l!=r) {
sum=0;
for (int j=0;j++<n1;) sum+=Node[Node[t1[j]].left].s;
for (int j=0;j++<n2;) sum-=Node[Node[t2[j]].left].s;
if (sum>=Query[i][3]) {
r=(l+r)>>1;
for (int j=0;j++<n1;) t1[j]=Node[t1[j]].left;
for (int j=0;j++<n2;) t2[j]=Node[t2[j]].left;
} else {
Query[i][3]-=sum;
l=((l+r)>>1)+1;
for (int j=0;j++<n1;) t1[j]=Node[t1[j]].right;
for (int j=0;j++<n2;) t2[j]=Node[t2[j]].right;
}
}
putint(C[l]);
}
}
}

int main() {
INIT();
Solve();
return 0;
}

树状数组套函数式线段树+离散化
时间复杂度：O((n+m)log(n+m)+(n+m)log^2(n+m))

编译成功

测试数据 #0: Accepted, time = 187 ms, mem = 158932 KiB, score = 10
测试数据 #1: Accepted, time = 312 ms, mem = 158940 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 158932 KiB, score = 10
测试数据 #3: Accepted, time = 109 ms, mem = 158936 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 158936 KiB, score = 10
测试数据 #5: Accepted, time = 203 ms, mem = 158936 KiB, score = 10
测试数据 #6: Accepted, time = 218 ms, mem = 158932 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 158936 KiB, score = 10
测试数据 #8: Accepted, time = 218 ms, mem = 158936 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 158936 KiB, score = 10
Accepted, time = 1542 ms, mem = 158940 KiB, score = 100

树状数组+SBT+二分查找O(n log^2 n + m log^3 m)弱弱AC......

编译成功

foo.cpp: In function 'int main()':
foo.cpp:220:16: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1]' [-Wformat]
测试数据 #0: Accepted, time = 562 ms, mem = 11920 KiB, score = 10
测试数据 #1: Accepted, time = 859 ms, mem = 17052 KiB, score = 10
测试数据 #2: Accepted, time = 93 ms, mem = 3120 KiB, score = 10
测试数据 #3: Accepted, time = 531 ms, mem = 9072 KiB, score = 10
测试数据 #4: Accepted, time = 421 ms, mem = 8436 KiB, score = 10
测试数据 #5: Accepted, time = 765 ms, mem = 17108 KiB, score = 10
测试数据 #6: Accepted, time = 812 ms, mem = 18616 KiB, score = 10
测试数据 #7: Accepted, time = 593 ms, mem = 10728 KiB, score = 10
测试数据 #8: Accepted, time = 796 ms, mem = 15896 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 3684 KiB, score = 10
Accepted, time = 5588 ms, mem = 18616 KiB, score = 100
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 50001

struct node {
int key,s;
node *left,*right;
};

node* t[MAXN];
node* R[MAXN];
node *bank=new(node);

int a[MAXN];
int n,m;

int lowbit(int x){
return ((~x)+1)&x;
}

//--------------Size_Balanced_Tree------------------

int left_ratote(node* &t){
node *k=(*t).right;
(*t).right=(*k).left;
(t).s=((t).left).s+((*t).right).s+1;
(*k).left=t;
(*k).s=(t).s+((*k).right).s+1;
t=k;
return 0;
}

int right_ratote(node* &t){
node *k=(*t).left;
(*t).left=(*k).right;
(t).s=((t).left).s+((*t).right).s+1;
(*k).right=t;
(k).s=((*k).left).s+(*t).s+1;
t=k;
return 0;
}

int maintain(node* &t){
if ((((t).left).left).s>((*t).right).s){
right_ratote(t);
maintain((t).right);
maintain(t);
return 0;
}
if (((*(t).left).right).s>((*t).right).s){
left_ratote((*t).left);
right_ratote(t);
maintain((*t).left);
maintain((t).right);
maintain(t);
return 0;
}
if (((*(t).right).right).s>((*t).left).s){
left_ratote(t);
maintain((t).left);
maintain(t);
return 0;
}
if (((*(t).right).left).s>((*t).left).s){
right_ratote((*t).right);
left_ratote(t);
maintain((*t).left);
maintain((*t).right);
return 0;
}
return 0;
}

int INSERT(int key,node* &t){
if (t==bank){
t=new(node);
(*t).left=(*t).right=bank;
(*t).s=1;
(*t).key=key;
return 0;
}
(*t).s++;
if (key<=(*t).key){
INSERT(key,(*t).left);
} else INSERT(key,(*t).right);
maintain(t);
return 0;
}

int DELETE(int key,node* &t){
if (key==(*t).key){
if ((*t).left==bank&&(*t).right==bank){
delete(t);
t=bank;
return 0;
}
if ((*t).left==bank){
node *p=(*t).right;
delete(t);
t=p;
return 0;
}
if ((*t).right==bank){
node *p=(*t).left;
delete(t);
t=p;
return 0;
}
right_ratote(t);
DELETE(key,(*t).right);
(t).s=((t).left).s+((*t).right).s+1;
maintain(t);
return 0;
}
if (key<(*t).key){
DELETE(key,(*t).left);
} else DELETE(key,(*t).right);
(t).s=((t).left).s+((*t).right).s+1;
return 0;
}

int get_rank(int key,node *t){
int rec=0;
node *p=t;
while (p!=bank){
if ((p).key<key){
rec+=(((*p).left).s+1);
p=(*p).right;
} else {
p=(*p).left;
}
}
return rec;
}

//----------------Binary_Search--------------------

node *range[MAXN];
int rm;

int GET_RANK(int key){
int rec=0;
for (int i=0;i++<rm;){
rec+=get_rank(key,range[i]);
}
return rec;
}

int get_ans(int l,int r,int k){
rm=0;
int i=r;
while (i>=l){
int s=i-lowbit(i)+1;
if (s>=l){
range[++rm]=t[i];
i=s-1;
} else {
range[++rm]=R[i];
i--;
}
}
int left=-0x7fffffff,right=0x7fffffff;
for (i=0;i++<rm;){
node *p=range[i];
while (p!=bank){
if ((*p).key<left){
p=(*p).right;
continue;
}
if ((*p).key>right){
p=(*p).left;
continue;
}
int s=GET_RANK((*p).key);
if (s==k-1){
return (*p).key;
}
if (s<k-1){
left=(*p).key;
p=(*p).right;
} else {
right=(*p).key;
p=(*p).left;
}
}
}
return left;
}

//----------------------------------------------

int main(){
(*bank).s=0;
(*bank).left=(*bank).right=bank;
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
t[i]=R[i]=bank;
for (int j=i-lowbit(i);j++<i;){
INSERT(a[j],t[i]);
}
INSERT(a[i],R[i]);
}
while (m--){
char c[1];
scanf("%s",&c);
if (c[0]=='Q'){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",get_ans(l,r,k));
} else {
int x,y;
scanf("%d%d",&x,&y);
int i=x;
while (i<=n){
DELETE(a[x],t[i]);
INSERT(y,t[i]);
i+=lowbit(i);
}
(*R[x]).key=y;
a[x]=y;
}
}
return 0;
}

这时限。。。这数据。。。直接暴力过。。冷掉~
测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
Accepted, time = 39120 ms, mem = 832 KiB, score = 100
代码就免了。。。。直接STL排序

这时限。。。这数据。。。直接暴力过。。冷掉~
测试数据 #0: Accepted, time = 3062 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 6062 ms, mem = 828 KiB, score = 10
测试数据 #2: Accepted, time = 250 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 3109 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 1937 ms, mem = 832 KiB, score = 10
测试数据 #5: Accepted, time = 5781 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 5796 ms, mem = 832 KiB, score = 10
测试数据 #7: Accepted, time = 5015 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 7296 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 812 ms, mem = 824 KiB, score = 10
Accepted, time = 39120 ms, mem = 832 KiB, score = 100
代码就免了。。。。直接STL排序

├ 测试数据 01：答案正确... (1681ms, 6460KB)

├ 测试数据 02：答案正确... (2664ms, 7436KB)

├ 测试数据 03：答案正确... (464ms, 5676KB)

├ 测试数据 04：答案正确... (2461ms, 6848KB)

├ 测试数据 05：答案正确... (1556ms, 6848KB)

├ 测试数据 06：答案正确... (2742ms, 7436KB)

├ 测试数据 07：答案正确... (2570ms, 7628KB)

├ 测试数据 08：答案正确... (3334ms, 7044KB)

├ 测试数据 09：答案正确... (3678ms, 7436KB)

├ 测试数据 10：答案正确... (1447ms, 6652KB)

表示快排改一下也可以做……（好像也慢不了多少啊）

附上代码：

type arr=array[0..50001] of longint;

var a:arr;

l,r,n,m,i,j,k,pos,w:longint;

x:char;

function sort(t,w:longint; a:arr):longint;

var i,j,mid,o:longint;

begin

i:=t; j:=w; mid:=a[(i+j) shr 1];

repeat

while a[i]mid do dec(j);

if ij;

if k=i-(l-1) then exit(sort(i,w,a)) else

exit(mid);

end;

begin

readln(n,m);

for i:=1 to n do read(a[i]); readln;

for i:=1 to m do

begin

read(x);

if x='Q' then

begin

readln(l,r,k);

writeln(sort(l,r,a));

end;

if x='C' then

begin

readln(pos,w);

a[pos]:=w;

end;

end;

end.

编译通过...

├ 测试数据 01：答案正确... 618ms

├ 测试数据 02：答案正确... 976ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 664ms

├ 测试数据 05：答案正确... 415ms

├ 测试数据 06：答案正确... 867ms

├ 测试数据 07：答案正确... 883ms

├ 测试数据 08：答案正确... 898ms

├ 测试数据 09：答案正确... 1054ms

├ 测试数据 10：答案正确... 290ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：6690ms

2010-7-9 评测机：6K

线段树套SBT M*lg^2N*lg(10^9) 140行

速度被lx神牛BS了...

编译通过...

├ 测试数据 01：答案正确... 2556ms

├ 测试数据 02：答案正确... 4244ms

├ 测试数据 03：答案正确... 666ms

├ 测试数据 04：答案正确... 3572ms

├ 测试数据 05：答案正确... 2291ms

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：答案正确... 4025ms

├ 测试数据 08：答案正确... 4916ms

├ 测试数据 09：答案正确... 5275ms

├ 测试数据 10：运行超时|格式错误...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：27545ms

我疯了 vijos mini 这么卡。。。。r~！

delete:=key[t];

if (left[t]=0)or(right[t]=0) then t:=left[t]+right[t]

else key[t]:=delete(left[t],v);

忘了写key[t]:=调了很多数据都没发现，

还有就是排序写好后忘了把sort（1，rr）写上去（就是没掉用）

我用的是树套树，写到一半才想到树状数组+SBT

听SWJ神牛说还可以用离散化+二分（这个问题的解是谁）+二维树状数组+hash，

就是（x，y）表示1-x的区间内1-y的和（离散化后重新编号，暴力赋值（像计数排序））。每次用求x-y的小于k有多少个时，分别求1-x-1，和1-y。

树状数组+SBT 200 行

悲剧的碰上 vag 6K

编译通过...

├ 测试数据 01：答案正确... 306ms

├ 测试数据 02：答案正确... 493ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 352ms

├ 测试数据 05：答案正确... 181ms

├ 测试数据 06：答案正确... 555ms

├ 测试数据 07：答案正确... 555ms

├ 测试数据 08：答案正确... 602ms

├ 测试数据 09：答案正确... 540ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3734ms

纯线段树不行么？