laekov

好一道卡常数。不仅卡时间，还卡空间。堪称丧心病狂的极致。

首先因为空间小所以得用莫队。然后不知为何树状数组没有直接分块跑得快。

没有救啦。

#include <cstdio>

#include <cctype>

#include <cmath>

#include <cstring>

#include <algorithm>

 

usingnamespacestd;

 

structqry {

    intl, r, a, b, n;

};

 

int_d_;

#define readInt(_x_) { \

    int& _s_ = _x_; \

    while(!isdigit(_d_ = getchar())); \

    _s_ = 0; \

    while((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \

}

 

constintmaxn = 100009;

constintmaxm = 1000009;

 

intn, m, bsz, a[maxn], c[maxn], w[maxn], b[maxn], ans[maxm];

qry q[maxm];

 

inlineboolcmpQry(constqry& a, constqry& b) {

    returnw[a. l] < w[b. l] || (w[a. l] == w[b. l] && a. r < b. r);

}

 

inlinevoidchg(intp, intv) {

    b[w[p]] += v;

}

 

intqry(intl, intr) {

    ints = 0;

    if(w[l] == w[r]) {

        while(l <= r) {

            if(c[l])

                ++ s;

            ++ l;

        }

    }

    else{

        for(inti = l; w[i] == w[l]; ++ i)

            if(c[i])

                ++ s;

        for(inti = w[l] + 1; i < w[r]; ++ i)

            s += b[i];

        for(inti = r; w[i] == w[r]; -- i)

            if(c[i])

                ++ s;

    }

    returns;

}

 

intmain() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

 

    readInt(n);

    readInt(m);

    bsz = (int)sqrt(n / 4) + 1;

    for(inti = 1; i <= n; ++ i) {

        readInt(a[i]);

        w[i] = (i - 1) / bsz + 1;

    }

    for(inti = 0; i < m; ++ i) {

        readInt(q[i]. l);

        readInt(q[i]. r);

        readInt(q[i]. a);

        readInt(q[i]. b);

        q[i]. n = i;

    }

    sort(q, q + m, cmpQry);

    memset(b, 0, sizeof(b));

    chg(a[1], 1);

    c[a[1]] = 1;

    for(inti = 0, l = 1, r = 1; i < m; ++ i) {

        while(l > q[i]. l) {

            -- l;

            if(!c[a[l]])

                chg(a[l], 1);

            ++ c[a[l]];

        }

        while(r < q[i]. r) {

            ++ r;

            if(!c[a[r]])

                chg(a[r], 1);

            ++ c[a[r]];

        }

        while(l < q[i]. l) {

            -- c[a[l]];

            if(!c[a[l]])

                chg(a[l], -1);

            ++ l;

        }

        while(r > q[i]. r) {

            -- c[a[r]];

            if(!c[a[r]])

                chg(a[r], -1);

            -- r;

        }

        ans[q[i]. n] = qry(q[i]. a, q[i]. b);

    }

    for(inti = 0; i < m; ++ i)

        printf("%d\n", ans[i]);

}