记录编号	432688	评测结果	TTTTTTTTTT
题目名称	[河南省队2012] 找第k小的数	最终得分	0
用户昵称	WildRage	是否通过	未通过
代码语言	C++	运行时间	10.000 s
提交时间	2017-08-03 17:38:55	内存使用	49.69 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
namespace FIFO {
char ch, B[1 << 20], *S = B, *T = B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa, bb;
inline int F()
{
    while (ch = getc(), !isd(ch) && ch != '-'); ch == '-' ? aa = bb = 0 : (aa = ch - '0', bb = 1);
    while (ch = getc(), isd(ch))aa = aa * 10 + ch - '0'; return bb ? aa : -aa;
}
}
#define gi FIFO::F()
const int full = 19;
struct Trie_Node
{
    Trie_Node *ch[2];
    int s;
    Trie_Node()
    {
        ch[0] = ch[1] = NULL;
        s = 0;
    }
    void *operator new (size_t);
} *null , *C , *Num;
inline void *Trie_Node::operator new (size_t)
{
    if (C == Num)
    {
        C = new Trie_Node[(1 << 22) + 10];
        Num = C + (1 << 22) + 10;
    }
    return C++;
}
struct Trie
{
    Trie_Node *root[100005];
    Trie()
    {
        null = new Trie_Node();
        null->ch[0] = null->ch[1] = null;
        root[0] = new Trie_Node();
        root[0]->ch[1] = root[0]->ch[0] = null;
    }
    inline Trie_Node *NewNode()
    {
        Trie_Node *rt = new Trie_Node();
        rt->ch[0] = rt->ch[1] = null;
        return rt;
    }
    inline void copy(Trie_Node *&a, Trie_Node *b)
    {
        if (b == null)
            a = null;
        else
            a = NewNode(), *a = *b;
    }
    inline void Insert(int x, int cnt)
    {
        copy(root[cnt], root[cnt - 1]);
        Trie_Node *rt1 = root[cnt], *rt2 = root[cnt - 1];
        for (register int i = full; i >= 0; i--)
        {
            int k = (x >> i) & 1;
            copy(rt1->ch[k], rt2->ch[k]);
            if (rt1->ch[k] == null)
                rt1->ch[k] = NewNode();
            rt1 = rt1->ch[k], rt2 = rt2->ch[k];
            rt1->s++;
        }
    }
    inline int kth(int k, int l, int r)
    {
        int res = 0;
        Trie_Node *rt1 = root[r], *rt2 = root[l - 1];
        for (register int i = full; i >= 0; i--)
        {
            if (k > rt1->ch[0]->s - rt2->ch[0]->s)
            {
                k -= (rt1->ch[0]->s - rt2->ch[0]->s);
                res |= (1 << i);
                rt1 = rt1->ch[1], rt2 = rt2->ch[1];
            }
            else
            {
                rt1 = rt1->ch[0], rt2 = rt2->ch[0];
            }
        }
        return res;
    }
} root;
int Main()
{
    freopen("kth.in", "r", stdin);
    freopen("kth.out", "w", stdout);
    int n, m;
    n = gi; m = gi;
    register int i;
    for (i = 1; i <= n; i += 4)
    {
        root.Insert(gi, i);
        root.Insert(gi, i + 1);
        root.Insert(gi, i + 2);
        root.Insert(gi, i + 3);
    }
    i -= 4;
    for (; i <= n; i++)
        root.Insert(gi, i);
        register int b, k , c;
    while (m--)
    {
        b = gi; c = gi; k = gi;
        printf("%d\n", root.kth(k, b, c));
    }
    return 0;
}
int wq = Main();
int main() {;}