记录编号	316645	评测结果	AAAAAAAAAA
题目名称	[AHOI 2013] 作业	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	13.684 s
提交时间	2016-10-06 23:03:24	内存使用	32.33 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdarg>
#include <map>
#include <cctype>
#include <cmath>
#include <set>
#include <algorithm>
#define BT __attribute__((optimize("O3")))
#define MAXN 100002
using namespace std;
BT
int fast_read()
{
    int r;
    char c;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}
int data[MAXN];
struct que
{
    int l, r;
    int a, b;
    int ans1, ans2;
    int bk;
}ques[1000003];
int st[1000003];
bool cmp(int a, int b)
{
    return (ques[a].bk < ques[b].bk) || ((ques[a].bk == ques[b].bk) && (ques[a].r < ques[b].r));
}
int n;
int cnt[MAXN];  //count panchong
int c1[MAXN], c2[MAXN];
int lowbit(int x)
{
    return x&-x;
}

BT
inline int add1(int p, int v)
{
    for(int i = p; i <= n; i += lowbit(i))c1[i] += v;
}
BT
inline int add2(int p, int v)
{
    for(int i = p; i <= n; i += lowbit(i))
        c2[i] += v;
}

BT
int cnt1(int l, int r)
{
    int s1 = 0, s2 = 0;
    for(int i = l; i > 0; i -= lowbit(i))s1 += c1[i];
    for(int i = r; i > 0; i -= lowbit(i))s2 += c1[i];
    return s2-s1;
}
BT
int cnt2(int l, int r)
{
    int s1 = 0, s2 = 0;
    for(int i = l; i > 0; i -= lowbit(i))s1 += c2[i];
    for(int i = r; i > 0; i -= lowbit(i))s2 += c2[i];
    return s2-s1;
}

BT
int main()
{
    freopen("ahoi2013_homework.in", "r", stdin);
    freopen("ahoi2013_homework.out", "w", stdout);
    int m;
    n = fast_read();
    m = fast_read();
    int magic = (int)sqrt(n);
    for(int i = 1; i <= n; i++)
        data[i] = fast_read();
     
    for(int i = 1; i <= m; i++)
    {
        que &q = ques[i];
        q.l = fast_read();
        q.r = fast_read();
        q.a = fast_read();
        q.b = fast_read();
        q.bk = q.l/magic;
        st[i] = i;
    }
    sort(st+1, st+1+m, cmp);
    int l = 1, r = 1;  //不要从0开始，否则0 += lowbit(0)会导致循环成为无限循环
    cnt[data[1]]++;
    add1(data[1], 1);
    add2(data[1], 1);
    for(int i = 1; i <= m; i++)
    {
        que &q = ques[st[i]];
        while(l < q.l)
        {
            add1(data[l], -1);  //del
            cnt[data[l]]--;
            if(cnt[data[l]] == 0)add2(data[l], -1);
            l++;
        }
        while(l > q.l)
        {
            l--;
            add1(data[l], 1);
            cnt[data[l]]++;
            if(cnt[data[l]] == 1)add2(data[l], 1);
        }
        while(r < q.r)
        {
            r++;
            add1(data[r], 1);
            cnt[data[r]]++;
            if(cnt[data[r]] == 1)add2(data[r], 1);
        }
        while(r > q.r)
        {
            add1(data[r], -1);
            cnt[data[r]]--;
            if(cnt[data[r]] == 0)add2(data[r], -1);
            r--;
        }
        q.ans1 = cnt1(q.a-1, q.b);
        q.ans2 = cnt2(q.a-1, q.b);
    }
    for(int i = 1; i <= m; i++)
        printf("%d %d\n", ques[i].ans1, ques[i].ans2);
}