二次联通门 :Codeforces 221d D. Little Elephant and Array
/*Codeforces 221d D. Little Elephant and Array题意 : 询问一段区间中出现次数等于自身的数的个数 正解是dp莫队水过， 作为我莫队的入门题 myj的思路 66把所有需查询的区间排序当前查询区间的答案为上一个区间的答案通过多次的区间移动得出*/#include <algorithm>#include <cstdio>#include <cmath>#define Max 100005void read (int &now){now = 0;register char word = getchar ();bool temp = false;while (word < '0' || word > '9'){if (word == '-')temp = true;word = getchar ();}while (word >= '0' && word <= '9'){now = now * 10 + word - '0';word = getchar ();}if (temp)now = -now;}int N, M;int belong[Max];struct Data{int l, r;int ID;bool operator < (const Data &now) const {if (belong[now.l] == belong[this->l])return now.r > this->r;return belong[now.l] > belong[this->l];}};int number[Max];int K_Size;int count[Max];int rank_[Max];Data query[Max];int Answer[Max], Result;int pos[Max];incount void Updata (int now, int key){if (count[number[now]] == pos[now])Result--;count[number[now]] += key;if (count[number[now]] == pos[now])Result++;}int main (int argc, char *argv[]){read (N);read (M);K_Size = sqrt (N);for (int i = 1; i <= N; i++){read (number[i]);rank_[i] = number[i];pos[i] = number[i];belong[i] = (i + 1) / K_Size;}std :: sort (rank_ + 1, rank_ + 1 + N);int Size = std :: unique (rank_ + 1, rank_ + 1 + N) - rank_ - 1;for (int i = 1; i <= N; i++)number[i] = std :: lower_bound (rank_ + 1, rank_ + 1 + Size, number[i]) - rank_;for (int i = 1; i <= M; i++){read (query[i].l);read (query[i].r);query[i].ID = i; }std :: sort (query + 1, query + 1 + M);int l = 1, r = 0;for (int cur = 1, now_1, now_2; cur <= M; cur++){now_1 = query[cur].l;now_2 = query[cur].r;if (l < now_1)for (int i = l; i < now_1; i++)Updata (i, -1);elsefor (int i = l - 1; i >= now_1; i--)Updata (i, 1);if (r < now_2)for (int i = r + 1; i <= now_2; i++)Updata (i, 1);else for (int i = r; i > now_2; i--)Updata (i, -1);l = now_1;r = now_2;Answer[query[cur].ID] = Result;}for (int i = 1; i <= M; i++)printf ("%d\n", Answer[i]);return 0;}
