Codeforces 221d D. Little Elephant and Array

二次联通门 : Codeforces 221d D. Little Elephant and Array

/*Codeforces 221d D. Little Elephant and Array题意 : 询问一段区间中出现次数等于自身的数的个数 正解是dp莫队水过， 作为我莫队的入门题 myj的思路 66把所有需查询的区间排序当前查询区间的答案为上一个区间的答案通过多次的区间移动得出*/
#include 
#include 
#include #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;
}

转载于:https://www.cnblogs.com/ZlycerQan/p/6946285.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！