首页 > 代码库 > 洛谷 P2056 采花 - 莫队算法
洛谷 P2056 采花 - 莫队算法
萧芸斓是 Z国的公主，平时的一大爱好是采花。
今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了 n 朵花，花有 c 种颜色（用整数 1-c 表示） ，且花是排成一排的，以便于公主采花。
公主每次采花后会统计采到的花的颜色数， 颜色数越多她会越高兴！ 同时， 她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。 由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 m 个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！ ） ，最后会选择令公主最高兴的行程（为了拿到更多奖金！ ） 。
输入输出格式
输入格式：
第一行四个空格隔开的整数 n、c 以及 m。
接下来一行 n 个空格隔开的整数，每个数在[1, c]间，第i 个数表示第 i 朵花的颜色。
接下来 m 行每行两个空格隔开的整数 l 和 r（l ≤ r） ，表示女仆安排的行程为公主经过第 l 到第r 朵花进行采花。
输出格式：
共m行， 每行一个整数， 第i个数表示公主在女仆的第i个行程中能采到的花的颜色数。
输入输出样例
输入样例#1：
5 3 5 1 2 2 3 11 5 1 2 2 2 2 3 3 5
输出样例#1：
2 0 0 1 0
说明
对于100%的数据，1 ≤ n ≤10^5，c ≤ n，m ≤ 10^5。
(这题Codevs上也有，只不过，数据范围强制用O(nlog2n)的做法)
分块的数据范围，支持离线，O(1)进行更新，不用莫队还用什么？（我只是建立在降低思考难度和骗分上想的）
Code
1 /** 2 * luogu.org 3 * Problem#2056 4 * Accepted 5 * Time:1100ms 6 * Memory:14179k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream> 11 #include<algorithm> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<cctype> 16 #include<cmath> 17 #include<ctime> 18 #include<map> 19 #include<stack> 20 #include<set> 21 #include<queue> 22 #include<vector> 23 #ifndef WIN32 24 #define AUTO "%lld" 25 #else 26 #define AUTO "%I64d" 27 #endif 28 using namespace std; 29 typedef bool boolean; 30 #define inf 0xfffffff 31 #define smin(a, b) (a) = min((a), (b)) 32 #define smax(a, b) (a) = max((a), (b)) 33 template<typename T> 34 inline boolean readInteger(T& u) { 35 char x; 36 int aFlag = 1; 37 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 38 if(x == -1) { 39 ungetc(x, stdin); 40 return false; 41 } 42 if(x == ‘-‘) { 43 aFlag = -1; 44 x = getchar(); 45 } 46 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 47 u *= aFlag; 48 ungetc(x, stdin); 49 return true; 50 } 51 52 typedef class Segment { 53 public: 54 int from; 55 int end; 56 int first; 57 int id; 58 Segment():from(0), end(0), first(0), id(0) { } 59 60 boolean operator < (Segment b) const { 61 if(first != b.first) return first < b.first; 62 return end < b.end; 63 } 64 }Segment; 65 66 int n, c, q; 67 int m; 68 int *flo; 69 Segment* seg; 70 int *res; 71 int *counter; 72 73 inline void init() { 74 readInteger(n); 75 readInteger(c); 76 readInteger(q); 77 flo = new int[(const int)(n + 1)]; 78 seg = new Segment[(const int)(q + 1)]; 79 res = new int[(const int)(q + 1)]; 80 counter = new int[(const int)(c + 1)]; 81 m = (int)sqrt(n + 0.5); 82 for(int i = 1; i <= n; i++) 83 readInteger(flo[i]); 84 for(int i = 1; i <= q; i++) { 85 readInteger(seg[i].from); 86 readInteger(seg[i].end); 87 seg[i].first = seg[i].from / m; 88 seg[i].id = i; 89 } 90 } 91 92 inline void solve() { 93 sort(seg + 1, seg + q + 1); 94 int val, mdzz = 1; 95 for(int id = 0; id <= m; id++) { 96 val = 0; 97 int l = 1, r = 1; 98 memset(counter, 0, sizeof(int) * (c + 1)); 99 for(; mdzz <= q && seg[mdzz].first == id; mdzz++) {100 while(r <= seg[mdzz].end) {101 counter[flo[r]]++;102 if(counter[flo[r]] == 2) val++;103 r++;104 }105 while(l < seg[mdzz].from) {106 counter[flo[l]]--;107 if(counter[flo[l]] == 1) val--;108 l++;109 }110 while(l > seg[mdzz].from) {111 l--;112 counter[flo[l]]++;113 if(counter[flo[l]] == 2) val++;114 }115 res[seg[mdzz].id] = val;116 }117 }118 for(int i = 1; i <= q; i++)119 printf("%d\n", res[i]);120 }121 122 int main() {123 init();124 solve();125 return 0;126 }
洛谷 P2056 采花 - 莫队算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。