记录编号	319659	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]2387	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.821 s
提交时间	2016-10-10 21:05:31	内存使用	0.97 MiB

#pragma GCC optimize(3)
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <cstdarg>
#include <cstring>
#include <string>
#include <list>
#include <cctype>
#include <vector>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
int fast_read()
{
    int r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = false;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_mapped_type, less<int>, rb_tree_tag, 
            tree_order_statistics_node_update> phs;
            
#define MAXN 200001
int key[MAXN];
map<int, phs> table;

int main()
{
    freopen("2387_.in", "r", stdin);
    freopen("2387_.out", "w", stdout);
    int n, m;
    n = fast_read();
    m = fast_read();
    for(int i = 1; i <= n; i++)
    {
        int v = fast_read();
        table[v].insert(i);
        key[i] = v;
    }
    int last = n;
    while(m--)
    {
        char c;
        while(!isalpha(c = getchar()));
        int a = fast_read()^last;
        int b = fast_read()^last;
        if(c == 'Q')
        {
            phs::iterator it = table[a].find_by_order(b-1);
            if(it == table[a].end())
            {
                puts("0");
                last = 0;
            }else
            {
                int p = *it;
                printf("%d\n", p);
                last = p;
            }
        }else if(c == 'M')
        {
            int v = key[a];
            table[v].erase(table[v].find(a));
            table[b].insert(a);
            key[a] = b;
        }
    }
    return 0;
}