60道留念? REfun的一半留念? 我太菜了留念?

这年头刷水真不容易…重要的翻车说三遍:

数组不要开太大!!!!!!!!!

数组不要开太大!!!!!!!!!

数组不要开太大!!!!!!!!!

懵逼的 题目

ZKJ的OJ

扯淡的 题解

裸的主席树

唯一有必要说一句的就是

我写完了之后, 样例始终过不去, 调试发现我写的没有任何问题, 但是ins()的时候有一个值始终不对, 然后就连锁反应影响了后面的值

任何发现我的数组: MAXN << 32

其实我想写MAXN * 32的…

然后卡了半天空间…在zzzyc的帮助下底下的代码是可以过的…

沙茶的 代码

/**************************************************************
    Problem: 3524
    User: Cansult
    Language: C++
    Result: Accepted
    Time:8088 ms
    Memory:198556 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
using namespace std;
struct node
{
    int le, ri, zh, ls, rs;
}b[MAXN*20];
int root[MAXN], cntb, n, m;
void push_up(int dq)
{ b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh; }
void ins(int& dq, int pre, int le, int ri, int zh)
{
    dq = ++cntb;
    b[dq].le = le, b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].zh = b[pre].zh + 1;
        return ;
    }
    int mi = (le + ri) >> 1;
    if (zh > mi)
        b[dq].ls = b[pre].ls, ins(b[dq].rs, b[pre].rs, mi + 1, ri, zh);
    else
        b[dq].rs = b[pre].rs, ins(b[dq].ls, b[pre].ls, le, mi, zh);
    push_up(dq);
}
int cx(int lt, int rt, int k)
{
    if (b[rt].le == b[rt].ri)
    {
        if (b[rt].zh - b[lt].zh > k)
            return b[rt].le;
        else
            return 0;
    }
    if (b[b[rt].ls].zh - b[b[lt].ls].zh > k)
        return cx(b[lt].ls, b[rt].ls, k);
    else if (b[b[rt].rs].zh - b[b[lt].rs].zh > k)
        return cx(b[lt].rs, b[rt].rs, k);
    else
        return 0;
}
int main()
{
//    cout << "Hello world!" << endl;
//  freopen("in.in", "r", stdin);
    b[0].ls = b[0].rs = b[0].zh = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int srx;
        scanf("%d", &srx);
        ins(root[i], root[i - 1], 1, n, srx);
    }
    for (int i = 1; i <= m; i++)
    {
        int srl, srr;
        scanf("%d%d", &srl, &srr);
        printf("%d\n", cx(root[srl - 1], root[srr], (srr - srl + 1) >> 1));
    }
    return 0;
}

/*
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
*/

By 沙茶 Cansult