首页 > 代码库 > [luoguP1972] [SDOI2009]HH的项链（莫队）

[luoguP1972] [SDOI2009]HH的项链（莫队）

2024-09-23 11:54:45   217人阅读

传送门

 

莫队基础题，适合我这种初学者。

莫队是离线算法，通常不带修改，时间复杂度为 O(n√n)

我们要先保证通过 [ l , r ] 求得 [ l , r + 1 ] , [ l , r - 1 ] , [ l - 1 , r ] , [ l + 1 , r ] 的效率是O(1)的

对于莫队的理解，移步远航休息栈

 

——代码

技术分享
 1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5  6 int n, m, S, ans = 1; 7 int a[50001], ton[1000001], anslist[200001]; 8 struct node 9 {10     int l, r, id, num;11 }q[200001];12 13 inline int read()14 {15     int x = 0;16     char ch = getchar();17     for(; !isdigit(ch); ch = getchar());18     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;19     return x;20 }21 22 inline bool cmp(node x, node y)23 {24     return x.id ^ y.id ? x.id < y.id : x.r < y.r;25 }26 27 int main()28 {29     int i, x, y;30     n = read();31     for(i = 1; i <= n; i++) a[i] = read();32     m = read();33     for(i = 1; i <= m; i++) q[i].l = read(), q[i].r = read(), q[i].num = i;34     S = sqrt(n);35     for(i = 1; i <= m; i++) q[i].id = q[i].l / S + 1;36     std::sort(q + 1, q + m + 1, cmp);37     x = q[1].l, y = q[1].l;38     ton[a[x]]++;39     for(i = 1; i <= m; i++)40     {41         while(x < q[i].l)42         {43             ton[a[x]]--;44             if(!ton[a[x]]) ans--;45             x++;46         }47         while(x > q[i].l)48         {49             x--;50             if(!ton[a[x]]) ans++;51             ton[a[x]]++;52         }53         while(y > q[i].r)54         {55             ton[a[y]]--;56             if(!ton[a[y]]) ans--;57             y--;58         }59         while(y < q[i].r)60         {61             y++;62             if(!ton[a[y]]) ans++;63             ton[a[y]]++;64         }65         anslist[q[i].num] = ans;66     }67     for(i = 1; i <= m; i++) printf("%d\n", anslist[i]);68     return 0;69 }
View Code

代码量真是友善啊

[luoguP1972] [SDOI2009]HH的项链（莫队）


联系
我们