题目大意：给出一些数，问在一个区间中不同的数值有多少种，和在一个区间中不同的数值有多少个。

思路：因为没有改动，所以就想到了莫队算法。然后我写了5K+的曼哈顿距离最小生成树，然后果断T了。(100s的时限啊,刷status都要刷疯了..,结果最后加了手写读入也没能A)。

后来果断放弃，写了分块版的莫队算法。

84sAC。。。这题卡的。。貌似莫队并非正解。

其有用分块来写莫队就非常easy了。仅仅须要将全部询问的区间排序。左端点所在块作为第一键值，右端点作为第二季键值排序，之后就能够转移了。理论上来时还是曼哈顿距离最小生成树比較快。可是常数实在是太大。随处可见的pair。sort。。

还不太好写。

。

唉。

。

时代的眼泪。。。

CODE(84816AC)：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 1100010

using namespace std;

struct Ask{

	int x,y,_id;

	int block;

	int a,b;

	bool operator <(const Ask &a)const {

		if(block == a.block)	return y < a.y;

		return block < a.block;

	}

	void Read(int p) {

		scanf("%d%d%d%d",&x,&y,&a,&b);

		_id = p;

	}

}ask[MAX];

int cnt,asks;

pair<int,int *> xx[MAX << 1];

int src[MAX];

int t;

int fenwick[MAX << 1],_fenwick[MAX];

int num[MAX];

pair<int,int> ans[MAX];

inline int GetSum(int fenwick[],int x)

{

	int re = 0;

	for(; x; x -= x&-x)

		re += fenwick[x];

	return re;

}

inline void Fix(int fenwick[],int x,int c)

{

	for(; x <= t; x += x&-x)

		fenwick[x] += c;

}

int main()

{

	cin >> cnt >> asks;

	int temp = 0;

	for(int i = 1; i <= cnt; ++i)

		scanf("%d",&xx[++temp].first),xx[temp].second = &src[i];

	for(int i = 1; i <= asks; ++i) {

		ask[i].Read(i);

		xx[++temp] = make_pair(ask[i].a,&ask[i].a);

		xx[++temp] = make_pair(ask[i].b,&ask[i].b);

	}

	sort(xx + 1,xx + temp + 1);

	for(int i = 1; i <= temp; ++i) {

		if(!t || xx[i].first != xx[i - 1].first)

			++t;

		*xx[i].second = t;

	}

	int block = static_cast<int>(sqrt(cnt));

	for(int i = 1; i <= asks; ++i)

		ask[i].block = ask[i].x / block;

	sort(ask + 1,ask + asks + 1);

	int l = 1,r = 0;

	for(int x = 1; x <= asks; ++x) {

		while(r < ask[x].y) {

			++num[src[++r]];

			Fix(fenwick,src[r],1);

			if(num[src[r]] == 1)	Fix(_fenwick,src[r],1);

		}

		while(l > ask[x].x) {

			++num[src[--l]];

			Fix(fenwick,src[l],1);

			if(num[src[l]] == 1)	Fix(_fenwick,src[l],1);

		}

		while(r > ask[x].y) {

			--num[src[r]];

			Fix(fenwick,src[r],-1);

			if(!num[src[r]])	Fix(_fenwick,src[r],-1);

			--r;

		}

		while(l < ask[x].x) {

			--num[src[l]];

			Fix(fenwick,src[l],-1);

			if(!num[src[l]])	Fix(_fenwick,src[l],-1);

			++l;

		}

		int p = ask[x]._id;

		ans[p].first = GetSum(fenwick,ask[x].b) - GetSum(fenwick,ask[x].a - 1);

		ans[p].second = GetSum(_fenwick,ask[x].b) - GetSum(_fenwick,ask[x].a - 1);

	}

	for(int i = 1; i <= asks; ++i)

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

	return 0;

}

CODE(TLE)：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 1100010

#define INF 0x3f3f3f3f

using namespace std;

inline int GetInt()

{

    int res=0;

    char t=getchar();

    for (;t>'9'||t<'0';t=getchar());

    for (;t>='0'&&t<='9';t=getchar()) res=res*10+t-'0';

    return res;

}

struct Ask{

    int x,y,_id;

    int a,b;

    bool operator <(const Ask &a)const {

        if(x == a.x)    return y < a.y;

        return x < a.x;

    }

    void Read() {

        x = GetInt();

        y = GetInt();

        a = GetInt();

        b = GetInt();

    }

}ask[MAX];

struct Edge{

    int x,y,length;

    Edge(int _,int __,int ___):x(_),y(__),length(___) {}

    Edge() {}

    bool operator <(const Edge &a)const {

        return length < a.length;

    }

}edge[MAX << 3];

int cnt,asks;

int src[MAX];

int y_x[MAX],t,gt,edges;

pair<int,int *> xx[MAX << 1];

int fenwick[MAX << 1],_fenwick[MAX];

int father[MAX];

int head[MAX],total;

int next[MAX << 1],aim[MAX << 1];

int num[MAX];

pair<int,int> ans[MAX];

inline int CalcM(const Ask &a,const Ask &b)

{

    return abs(a.x - b.x) + abs(a.y - b.y);

}

inline int GetPos(int x)

{

    int re = 0;

    for(; x <= t; x += x&-x)

        if(ask[fenwick[x]].x + ask[fenwick[x]].y < ask[re].x + ask[re].y)

            re = fenwick[x];

    return re;

}

inline void Fix(int x,int pos)

{

    for(; x; x -= x&-x)

        if(ask[fenwick[x]].x + ask[fenwick[x]].y > ask[pos].x + ask[pos].y)

            fenwick[x] = pos;

}

void MakeGraph()

{

    for(int dir = 1; dir <= 4; ++dir) {

        if(dir == 2 || dir == 4)

            for(int i = 1; i <= asks; ++i)

                swap(ask[i].x,ask[i].y);

        if(dir == 3)

            for(int i = 1; i <= asks; ++i)

                ask[i].y *= -1;

        sort(ask + 1,ask + asks + 1);

        for(int i = 1; i <= asks; ++i)

            xx[i] = make_pair(ask[i].y - ask[i].x,&y_x[i]);

        sort(xx + 1,xx + asks + 1);

        t = 0;

        for(int i = 1; i <= asks; ++i) {

            if(!t || xx[i].first != xx[i - 1].first)

                ++t;

            *xx[i].second = t;

        }

        memset(fenwick,0,sizeof(fenwick));

        for(int i = asks; i; --i) {

            int temp = GetPos(y_x[i]);

            if(temp)

                edge[++edges] = Edge(ask[temp]._id,ask[i]._id,CalcM(ask[temp],ask[i]));

            Fix(y_x[i],i);

        }

    }

    for(int i = 1; i <= asks; ++i)

        ask[i].x *= -1;

}

int Find(int x)

{

    if(father[x] == x)  return x;

    return father[x] = Find(father[x]);

}

inline void Add(int x,int y)

{

    next[++total] = head[x];

    aim[total] = y;

    head[x] = total;

}

void MST()

{

    sort(edge + 1,edge + edges + 1);

    for(int i = 1; i <= edges; ++i) {

        int fx = Find(edge[i].x);

        int fy = Find(edge[i].y);

        if(fx != fy) {

            father[fx] = fy;

            Add(fx,fy),Add(fy,fx);

        }

    }

}

inline int GetSum(int fenwick[],int x)

{

    int re = 0;

    for(; x; x -= x&-x)

        re += fenwick[x];

    return re;

}

inline void Fix(int fenwick[],int x,int c)

{

    for(; x <= gt; x += x&-x)

        fenwick[x] += c;

}

void DFS(int x,int last)

{

    static int l = 1,r = 0;

    while(r < ask[x].y) {

        ++num[src[++r]];

        Fix(fenwick,src[r],1);

        if(num[src[r]] == 1)    Fix(_fenwick,src[r],1);

    }

    while(l > ask[x].x) {

        ++num[src[--l]];

        Fix(fenwick,src[l],1);

        if(num[src[l]] == 1)    Fix(_fenwick,src[l],1);

    }

    while(r > ask[x].y) {

        --num[src[r]];

        Fix(fenwick,src[r],-1);

        if(!num[src[r]])    Fix(_fenwick,src[r],-1);

        --r;

    }

    while(l < ask[x].x) {

        --num[src[l]];

        Fix(fenwick,src[l],-1);

        if(!num[src[l]])    Fix(_fenwick,src[l],-1);

        ++l;

    }

    int p = ask[x]._id;

    ans[p].first = GetSum(fenwick,ask[x].b) - GetSum(fenwick,ask[x].a - 1);

    ans[p].second = GetSum(_fenwick,ask[x].b) - GetSum(_fenwick,ask[x].a - 1);

    for(int i = head[x]; i; i = next[i]) {

        if(aim[i] == last)  continue;

        DFS(aim[i],x);

        while(r < ask[x].y) {

            ++num[src[++r]];

            Fix(fenwick,src[r],1);

            if(num[src[r]] == 1)    Fix(_fenwick,src[r],1);

        }

        while(l > ask[x].x) {

            ++num[src[--l]];

            Fix(fenwick,src[l],1);

            if(num[src[l]] == 1)    Fix(_fenwick,src[l],1);

        }

        while(r > ask[x].y) {

            --num[src[r]];

            Fix(fenwick,src[r],-1);

            if(!num[src[r]])    Fix(_fenwick,src[r],-1);

            --r;

        }

        while(l < ask[x].x) {

            --num[src[l]];

            Fix(fenwick,src[l],-1);

            if(!num[src[l]])    Fix(_fenwick,src[l],-1);

            ++l;

        }

    }

}

int main()

{

    ask[0].x = ask[0].y = INF;

    cnt = GetInt();

    asks = GetInt();

    int temp = 0;

    for(int i = 1; i <= cnt; ++i) {

        xx[++temp].first = GetInt();

        xx[temp].second = &src[i];

    }

    for(int i = 1; i <= asks; ++i) {

        ask[i].Read();

        xx[++temp] = make_pair(ask[i].a,&ask[i].a);

        xx[++temp] = make_pair(ask[i].b,&ask[i].b);

        ask[i]._id = i;

        father[i] = i;

    }

    sort(xx + 1,xx + temp + 1);

    for(int i = 1; i <= temp; ++i) {

        if(!gt || xx[i].first != xx[i - 1].first)

            ++gt;

        *xx[i].second = gt;

    }

    MakeGraph();

    MST();

    memset(fenwick,0,sizeof(fenwick));

    DFS(1,0);

    for(int i = 1; i <= asks; ++i)

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

    return 0;

}