모팀 알고리즘 Gym - 100496D Data Mining
14752 단어 data mining
제목 전송문
1 /* 2 : i , , , p 3 : a[i+p-1] a[j], [l, r] , :) 4 */ 5 #include <cstdio> 6 #include <algorithm> 7 #include <map> 8 #include <set> 9 #include <vector> 10 #include <cmath> 11 #include <cstring> 12 using namespace std; 13 14 const int MAXN = 2e6 + 10; 15 const int INF = 0x3f3f3f3f; 16 map<int, int> table; 17 vector<int> V[MAXN]; 18 int cnt[MAXN]; 19 int a[MAXN]; 20 int ans[MAXN]; 21 struct Data 22 { 23 int b, l, r, id; 24 Data () {} 25 Data (int b, int l, int r, int id) : b (b), l (l), r (r), id (id) {}; 26 }data[MAXN]; 27 int n, m; 28 int ret; 29 30 bool cmp(Data x, Data y) 31 { 32 if (x.b == y.b) return x.r < y.r; 33 else return x.b < y.b; 34 } 35 36 void updata(int v) 37 { 38 if (v == 1) ret++; 39 else if (v == 0) ret--; 40 } 41 42 void Modui(void) 43 { 44 sort (data+1, data+1+m, cmp); 45 memset (cnt, 0, sizeof (cnt)); 46 47 int l = 1, r = 0; ret = 0; 48 for (int i=1; i<=m; ++i) 49 { 50 while (data[i].l < l) 51 { 52 ++cnt[a[--l]]; 53 if (cnt[a[l]] == 1) ret++; 54 } 55 while (data[i].l > l) 56 { 57 --cnt[a[l]]; 58 if (cnt[a[l]] == 0) ret--; 59 l++; 60 } 61 while (data[i].r > r) 62 { 63 ++cnt[a[++r]]; 64 if (cnt[a[r]] == 1) ret++; 65 } 66 while (data[i].r < r) 67 { 68 --cnt[a[r]]; 69 if (cnt[a[r]] == 0) ret--; 70 r--; 71 } 72 73 ans[data[i].id] = ret; 74 } 75 76 for (int i=1; i<=m; ++i) 77 { 78 printf ("%d
", ans[i]); 79 } 80 } 81 82 int main(void) //Gym - 100496D Data Mining 83 { 84 // freopen ("D.in", "r", stdin); 85 freopen ("data.in", "r", stdin); 86 freopen ("data.out", "w", stdout); 87 88 while (scanf ("%d", &n) == 1) 89 { 90 table.clear (); 91 for (int i=1; i<=n; ++i) V[i].clear (); 92 93 int num = 0; 94 for (int i=1; i<=n; ++i) 95 { 96 scanf ("%d", &a[i]); 97 a[i] = table[a[i]] ? table[a[i]] : table[a[i]] = ++num; 98 V[a[i]].push_back (i); 99 } 100 101 int block = (int) sqrt (n * 1.0); 102 scanf ("%d", &m); 103 for (int i=1; i<=m; ++i) 104 { 105 int l, r; scanf ("%d%d", &l, &r); 106 r = l + r - 1; 107 int pos = lower_bound (V[a[r]].begin (), V[a[r]].end (), l) - V[a[r]].begin (); 108 r = V[a[r]][pos]; 109 data[i] = Data (l / block, l, r, i); 110 } 111 112 Modui (); 113 } 114 115 return 0; 116 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
모팀 알고리즘 Gym - 100496D Data Mining텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.