解题思路:
区间更新,区间查询------》线段树
普通方法能过,但是原题的数据量描述如下:
对于 30% 的数据, n, m <= 10^3
对于 100% 的数据, n, m <= 10^5
线段树的东西,这里就赘述了,大家还是看博客博客比较好
注意事项: 注意边界
参考代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; struct Node{ int L, R; int mid() { return L + R >> 1; } }tree[N << 2]; ll sum[N << 2], table[N << 2]; void PushUp(int ri) { sum[ri] = sum[ri << 1] + sum[ri << 1 | 1]; } void BuildTree(int ri, int L, int R) { tree[ri] = { L, R }; if(L == R) { scanf("%d", &sum[ri]); return ; } int m = tree[ri].mid(); BuildTree(ri << 1, L, m); BuildTree(ri << 1 | 1, m + 1, R); PushUp(ri); } void UpdateTree(int ri, int L, int R) { if(tree[ri].L == tree[ri].R) { sum[ri] = table[sum[ri]]; return ; } int m = tree[ri].mid(); if(R <= m) UpdateTree(ri << 1, L, R); else if(L > m) UpdateTree(ri << 1 | 1, L, R); else { UpdateTree(ri << 1, L, m); UpdateTree(ri << 1 | 1, m + 1, R); } PushUp(ri); } int main() { int n, m; for(int i = 1; i < (N << 2); ++i) table[i] = (int)floor(log2(i)) + 1; scanf("%d%d", &n, &m); BuildTree(1, 1, n); int l, r; for(int i = 1; i <= m; ++i) { scanf("%d%d", &l, &r); UpdateTree(1, l, r); printf("%lld\n", sum[1]); } return 0; } /* 对于 30% 的数据, n, m <= 10^3 对于 100% 的数据, n, m <= 10^5 */
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:681 |
C二级辅导-求偶数和 (C语言代码)浏览:603 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:698 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:494 |
C语言程序设计教程(第三版)课后习题3.7 (C++代码)浏览:988 |
校门外的树 (C语言代码)浏览:1113 |
【亲和数】 (C语言代码)浏览:855 |
Pascal三角 (C语言代码)格式错误浏览:516 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:590 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:850 |