CF 86D Powerful array 【分块算法,n*sqrt(n)】

时间:2021-07-03 19:57:47
  分类: ACM 题解 数据结构 731人阅读 评论(3) 收藏 举报

给定一个数列:A1, A2,……,An,定义Ks为区间(l,r)中s出现的次数。

t个查询,每个查询l,r,对区间内所有a[i],求sigma(K^2*a[i])


离线+分块

将n个数分成sqrt(n)块。

对所有询问进行排序,排序标准:

      1. Q[i].left /block_size < Q[j].left / block_size (块号优先排序)

      2. 如果1相同,则 Q[i].right < Q[j].right (按照查询的右边界排序)


问题求解:

从上一个查询后的结果推出当前查询的结果。(这个看程序中query的部分)

如果一个数已经出现了x次,那么需要累加(2*x+1)*a[i],因为(x+1)^2*a[i] = (x^2 +2*x + 1)*a[i],x^2*a[i]是出现x次的结果,(x+1)^2 * a[i]是出现x+1次的结果。




时间复杂度分析:

排完序后,对于相邻的两个查询,left值之间的差最大为sqrt(n),则相邻两个查询左端点移动的次数<=sqrt(n),总共有t个查询,则复杂度为O(t*sqrt(n))。

又对于相同块内的查询,right端点单调上升,每一块所有操作,右端点最多移动O(n)次,总块数位sqrt(n),则复杂度为O(sqrt(n)*n)。

right和left的复杂度是独立的,因此总的时间复杂度为O(t*sqrt(n)  +  n*sqrt(n))。




[cpp] view plaincopy
  1. #include <cstdio>  
  2. #include <iostream>  
  3. #include <algorithm>  
  4. #include <cstring>  
  5. #include <cmath>  
  6. using namespace std;  
  7. #define N 200100  
  8. typedef long long ll;  
  9. ll a[N], cnt[N*5], ans[N], res;  
  10. int L, R;  
  11.   
  12. struct node {  
  13.     int x, y, l, p;  
  14. } q[N];  
  15. bool cmp(const node &x, const node &y) {  
  16.     if (x.l == y.l) return x.y < y.y;  
  17.     return x.l < y.l;  
  18. }  
  19. void query(int x, int y, int flag) {  
  20.     if (flag) {  
  21.         for (int i=x; i<L; i++) {  
  22.             res += ((cnt[a[i]]<<1)+1)*a[i];  
  23.             cnt[a[i]]++;  
  24.         }  
  25.         for (int i=L; i<x; i++) {  
  26.             cnt[a[i]]--;  
  27.             res -= ((cnt[a[i]]<<1)+1)*a[i];  
  28.         }  
  29.         for (int i=y+1; i<=R; i++) {  
  30.             cnt[a[i]]--;  
  31.             res -= ((cnt[a[i]]<<1)+1)*a[i];  
  32.         }  
  33.         for (int i=R+1; i<=y; i++) {  
  34.             res += ((cnt[a[i]]<<1)+1)*a[i];  
  35.             cnt[a[i]]++;  
  36.         }  
  37.   
  38.     } else {  
  39.         for (int i=x; i<=y; i++) {  
  40.             res += ((cnt[a[i]]<<1)+1)*a[i];  
  41.             cnt[a[i]]++;  
  42.         }  
  43.     }  
  44.     L = x, R = y;  
  45. }  
  46. int main() {  
  47.     int n, t;  
  48.   
  49.     scanf("%d%d", &n, &t);  
  50.     for (int i=1; i<=n; i++) scanf("%I64d", &a[i]);  
  51.     int block_size = sqrt(n);  
  52.   
  53.     for (int i=0; i<t; i++) {  
  54.         scanf("%d%d", &q[i].x, &q[i].y);  
  55.         q[i].l = q[i].x / block_size;  
  56.         q[i].p = i;  
  57.     }  
  58.   
  59.     sort(q, q+t, cmp);  
  60.   
  61.   
  62.     memset(cnt, 0, sizeof(cnt));  
  63.   
  64.     res = 0;  
  65.     for (int i=0; i<t; i++) {  
  66.         query(q[i].x, q[i].y, i);  
  67.         ans[q[i].p] = res;  
  68.     }  
  69.   
  70.     for (int i=0; i<t; i++) printf("%I64d\n", ans[i]);  
  71.   
  72.     return 0;  
  73. }  

 

CF 13E Holes 【块状链表】

分类: ACM 题解 数据结构 310人阅读 评论(0) 收藏 举报

题目描述:

一条直线上n个点,每个点有个“弹力”,可以把当前位置x上面的ball弹到x+a[x]上面。

两种操作

0. 修改a处的弹力值,编程b

1. 询问a点的ball经过多少次能跳出n个点外(就是出界了)。。。。求出弹跳的次数和最后落脚的点。



块状链表就是用来暴力模拟的。

用块状链表可以把时间复杂度从O(n)变成O(sqrt(n))。

这道题目的复杂度为O(m*sqrt(n))。

具体实现还是直接看代码容易理解……


[cpp] view plaincopy
  1. #include <iostream>  
  2. #include <algorithm>  
  3. #include <cmath>  
  4. #include <cstdio>  
  5. using namespace std;  
  6. #define N 100100  
  7. int block[N], c[N], next[N], a[N], end[N];  
  8. int n, m, block_size;  
  9.   
  10. void make(int x) {  
  11.     int y = x + a[x];  
  12.     if (y <= n && block[x] == block[y]) {  
  13.         c[x] = c[y] + 1;  
  14.         next[x] = next[y];  
  15.         end[x] = end[y];  
  16.     } else {  
  17.         end[x] = x;  
  18.         c[x] = 1;  
  19.         next[x] = y;  
  20.     }  
  21. }  
  22. void change(int x, int y) {  
  23.     a[x] = y;  
  24.     for (y=x; y && block[y]==block[x]; y--) make(y);  
  25. }  
  26.   
  27. void ask(int x) {  
  28.     int ret = 0, ans;  
  29.     for (; x<=n; x=next[x]) {  
  30.         ret += c[x];  
  31.         ans = end[x];  
  32.     }  
  33.     cout << ans << " " << ret << endl;  
  34. }  
  35. int main() {  
  36.   
  37.     cin >> n >> m;  
  38.     block_size = sqrt(n);  
  39.   
  40.     for (int i=1; i<=n; i++) {  
  41.         cin >> a[i];  
  42.         block[i] = i/block_size;  
  43.     }  
  44.     for (int i=n; i; i--) make(i);  
  45.   
  46.     int op, x, y;  
  47.     while (m--) {  
  48.         cin >> op;  
  49.         if (op == 0) {  
  50.             cin >> x >> y;  
  51.             change(x, y);  
  52.         } else {  
  53.             cin >> x;  
  54.             ask(x);  
  55.         }  
  56.     }  
  57.   
  58.     return 0;  
  59. }