[luoguP2709] 小B的询问（莫队）

传送门

个数　　1　　2　　3　　4　　5

答案　　1　　4　　9　 16　 25

做差　　1　　3　　5　　7　　9

显然增加一个数只需要增加 ton[a[x]] << 1 | 1 即可

　　减去一个数也减去这个

注意先加减再更新 ton

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 6 const int MAXN = 50001; 7 int n, m, S, k, ans = 1; 8 int a[MAXN], ton[MAXN], anslist[MAXN]; 9 struct node 10 q[MAXN]; 13 14 inline int read() 15 22 23 inline bool cmp(node x, node y) 24 27 28 int main() 29 49 while(x > q[i].l) 50 55 while(y > q[i].r) 56 61 while(y < q[i].r) 62 67 anslist[q[i].num] = ans; 68 } 69 for(i = 1; i <= m; i++) printf("%d\n", anslist[i]); 70 return 0; 71 }
View Code

上一篇：[luoguP3390]【模板】矩阵快速幂

下一篇：[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）

---

莫队