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继续回答上面的问题。

Input#

第一行一个数字N，代表测试组数 对于每组数据第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。 C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t

Output#

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input#

1
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output#

3
6

题解#

简单的来说就是待修改的区间k小值

我们用让线段树外面套一层树状数组就可以修改了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1000000000;
#define lowbit(_) ((_) & (-_))
struct Seg_Node
{
    Seg_Node *ch[2];
    int sum, l, r;
    Seg_Node(int L, int R)
    {
        sum = 0, l = L, r = R;
        ch[1] = ch[0] = NULL;
    }
#define sum(_) ((_) ? (_)->sum : 0)
    void Pushup()
    {
        sum = sum(ch[0]) + sum(ch[1]);
    }
} * root[50005];
int a[50005];
int n;
void Insert(Seg_Node *rt, int num)
{
    if (rt->l == rt->r)
    {
        rt->sum++;
        return;
    }
    int m = rt->l + rt->r >> 1;
    if (num <= m)
    {
        if (!rt->ch[0])
            rt->ch[0] = new Seg_Node(rt->l, m);
        Insert(rt->ch[0], num);
    }
    else
    {
        if (!rt->ch[1])
            rt->ch[1] = new Seg_Node(m + 1, rt->r);
        Insert(rt->ch[1], num);
    }
    rt->Pushup();
}
void Insert(int x, int num)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        if (root[i] == NULL)
            root[i] = new Seg_Node(0, N);
        Insert(root[i], num);
    }
}
void Delete(Seg_Node *&rt, int num)
{
    if (rt->l == rt->r)
    {
        rt->sum--;
        if (!rt->sum)
            delete rt, rt = NULL;
        return;
    }
    int m = rt->l + rt->r >> 1;
    if (num <= m)
        Delete(rt->ch[0], num);
    else
        Delete(rt->ch[1], num);
    rt->Pushup();
    if (!rt->sum)
        delete rt, rt = NULL;
}
void Delete(int x, int num)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        Delete(root[i], num);
    }
}
vector<Seg_Node *> Get(int x)
{
    vector<Seg_Node *> ans;
    for (int i = x; i > 0; i -= lowbit(i))
    {
        ans.push_back(root[i]);
    }
    return ans;
}
vector<Seg_Node *> Get_ch(vector<Seg_Node *> x, int op)
{
    for (int i=0;i<x.size();i++)
        if (x[i])
            x[i] = x[i]->ch[op];
    return x;
}
int Query(vector<Seg_Node *> list1, vector<Seg_Node *> list2, int l, int r, int k)
{
    if (l == r)
        return l;
    int ans = 0;
    for (int i=0;i<list2.size();i++)
        if (list2[i])
            ans += sum(list2[i]->ch[0]);
    for (int i=0;i<list1.size();i++)
        if (list1[i])
            ans -= sum(list1[i]->ch[0]);
    int m = l + r >> 1;
    if (ans >= k)
        return Query(Get_ch(list1, 0), Get_ch(list2, 0), l, m, k);
    else
        return Query(Get_ch(list1, 1), Get_ch(list2, 1), m + 1, r, k - ans);
}
void DFS(Seg_Node *&rt)
{
    if (rt)
    {
        DFS(rt->ch[0]);
        DFS(rt->ch[1]);
        delete rt;
        rt=NULL;
    }
}
void remove()
{
    for (int i = 1; i <= n; i++)
    {
        DFS(root[i]);
    }
}
int main(int argc, char const *argv[])
{
    //freopen("dynrank.in","r",stdin);
    //freopen("dynrank.out","w",stdout);
    //int T;
    //scanf("%d", &T);
    //while (T--)
    //{
        int m;
        scanf("%d%d", &n, &m);
        //memset(a,0,sizeof(a));
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            Insert(i, a[i]);
        }
        //sort(a + 1, a + n + 1);
        char op[3];
        int p, b, c;
        for (int i = 1; i <= m; i++)
        {
            scanf("%s", op);
            if (op[0] == 'Q')
            {
                scanf("%d%d%d", &p, &b, &c);
                printf("%d\n", Query(Get(p - 1), Get(b), 0, N, c));
            }
            else
            {
                scanf("%d%d", &p, &b);
                Delete(p, a[p]);
                Insert(p, b);
                a[p] = b;
            }
        }
        remove();
 //   }
    return 0;
}

树套树#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[50005], n;
class Treap
{
    class Node
    {
      public:
        int size, v, key;
        Node *ch[2];
        Node(int x)
        {
            key = rand();
            v = x;
            size = 1;
            ch[0] = ch[1] = NULL;
        }
#define size(_) ((_) ? (_)->size : 0)
        void Pushup()
        {
            size = size(ch[0]) + size(ch[1]) + 1;
        }
    } * root;
    Node *Merge(Node *A, Node *B)
    {
        if (!A)
            return B;
        if (!B)
            return A;
        if (A->key > B->key)
        {
            A->ch[1] = Merge(A->ch[1], B);
            A->Pushup();
            return A;
        }
        else
        {
            B->ch[0] = Merge(A, B->ch[0]);
            B->Pushup();
            return B;
        }
    }
    typedef pair<Node *, Node *> DNode;
    DNode Split(Node *rt, int k)
    {
        if (!rt)
            return DNode(NULL, NULL);
        DNode o;
        if (size(rt->ch[0]) >= k)
        {
            o = Split(rt->ch[0], k);
            rt->ch[0] = o.second;
            rt->Pushup();
            o.second = rt;
        }
        else
        {
            o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
            rt->ch[1] = o.first;
            rt->Pushup();
            o.first = rt;
        }
        return o;
    }
  public:
    Treap()
    {
        root = NULL;
    }
    int kth(int k)
    {
        DNode x = Split(root, k - 1);
        DNode y = Split(x.second, 1);
        Node *ans = y.first;
        root = Merge(x.first, Merge(y.first, y.second));
        return ans->v;
    }
    int rank(int x)
    {
        return rank(root, x);
    }
    int rank(Node *rt, int x)
    {
        if (!rt)
            return 0;
        return x <= rt->v ? rank(rt->ch[0], x) : rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
    }
    void Insert(int x)
    {
        int k = rank(root, x);
        DNode y = Split(root, k);
        Node *n = new Node(x);
        root = Merge(Merge(y.first, n), y.second);
    }
    void remove(int x)
    {
        int k = rank(root, x);
        DNode a = Split(root, k);
        DNode b = Split(a.second, 1);
        root = Merge(a.first, b.second);
    }
} root[50005 << 2];
#define lch l, m, rt << 1
#define rch m + 1, r, rt << 1 | 1
void build(int l, int r, int rt)
{
    for (int i = l; i <= r; i++)
        root[rt].Insert(a[i]);
}
void buildtree(int l, int r, int rt)
{
    build(l, r, rt);
    if (l == r)
        return;
    int m = l + r >> 1;
    buildtree(lch);
    buildtree(rch);
}
void updata(int k, int x, int y, int l, int r, int rt)
{
    root[rt].remove(y);
    root[rt].Insert(x);
    if (l == r)
        return;
    int m = l + r >> 1;
    if (k <= m)
        updata(k, x, y, lch);
    else
        updata(k, x, y, rch);
}
int rank(int L, int R, int x, int l, int r, int rt)
{
    if (L <= l && R >= r)
        return root[rt].rank(x);
    int m = l + r >> 1;
    if (R <= m)
        return rank(L, R, x, lch);
    if (L > m)
        return rank(L, R, x, rch);
    return rank(L, R, x, lch) + rank(L, R, x, rch);
}
int kth(int L, int R, int k)
{
    int l = -1e10, r = 1e10;
    while (l <= r)
    {
        int m = l + r >> 1;
        int num = rank(L, R, m, 1, n, 1) + 1;
        if (num <= k)
            l = m + 1;
        else
            r = m - 1;
    }
    return r;
}
int main()
{
    //freopen("dynrank.in", "r", stdin);
    //freopen("dynrank.out", "w", stdout);
    //int T;
    //scanf("%d", &T);
    //while (T--)
    //{
    //    memset(root,0,sizeof(root));
        int m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        buildtree(1, n, 1);
        char s[5];
        int i, j, k, t;
        while (m--)
        {
            scanf("%s", s);
            if (s[0] == 'Q')
            {
                scanf("%d%d%d", &i, &j, &k);
                printf("%d\n", kth(i, j, k));
            }
            else
            {
                scanf("%d%d", &i, &t);
                updata(i, t, a[i], 1, n, 1);
                a[i] = t;
            }
        }
    //}
}