区间更新改为区间每个点都改一次,属于是负优化了,能过就行

  1. #include<bits/stdc++.h>
  2. #define ULL unsigned long long
  3. #define LL long long
  4. #define endl '\n'
  5. #define debug(a) cout<<#a<<"="<<a<<endl;
  6. #define all(v) v.begin(), v.end()
  7. #define PII pair<int,int>
  8. using namespace std;
  9. const int N = 1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;
  10. int n,m;
  11. int a[N];
  12. struct node
  13. {
  14. int l,r;
  15. LL sum,maxx;
  16. }tr[N*4];
  17. void pushup(int u) //从子节点更新父节点信息
  18. {
  19. tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
  20. tr[u].maxx = max(tr[u<<1].maxx,tr[u<<1|1].maxx);
  21. }
  22. void build(int u,int l,int r)
  23. {
  24. if(l==r) tr[u] = {l,r,a[r],a[r]};
  25. else
  26. {
  27. tr[u] = {l,r};
  28. int mid = l + r >> 1;
  29. build(u<<1,l,mid) , build(u<<1|1,mid+1,r);
  30. pushup(u);
  31. }
  32. }
  33. void modify(int u,int l,int r)
  34. {
  35. if(tr[u].l==tr[u].r) //每个点都改
  36. {
  37. tr[u].sum = sqrt(tr[u].sum);
  38. tr[u].maxx = sqrt(tr[u].maxx);
  39. }
  40. else
  41. {
  42. int mid = tr[u].l + tr[u].r >> 1;
  43. // 区间内最大值大于1就继续暴力开根号
  44. if(l <= mid && tr[u<<1].maxx > 1) modify(u<<1,l,r);
  45. if(r > mid && tr[u<<1|1].maxx > 1) modify(u<<1|1,l,r);
  46. pushup(u);
  47. }
  48. }
  49. LL query(int u,int l,int r)
  50. {
  51. if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
  52. int mid = tr[u].l + tr[u].r >> 1;
  53. LL res = 0;
  54. if(l <= mid) res = query(u<<1,l,r);
  55. if(r > mid) res += query(u<<1|1,l,r);
  56. return res;
  57. }
  58. void solve()
  59. {
  60. cin>>n;
  61. for(int i=1;i<=n;i++) cin>>a[i];
  62. build(1,1,n);
  63. cin>>m;
  64. while (m--)
  65. {
  66. int op,l,r;
  67. cin>>op>>l>>r;
  68. if(op==1) cout<<query(1,l,r)<<endl;
  69. else modify(1,l,r);
  70. }
  71. }
  72. int main()
  73. {
  74. ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
  75. int _=1;
  76. // cin>>_;
  77. while(_--)
  78. {
  79. solve();
  80. }
  81. return 0;
  82. }
  83. /**
  84. * author: Nijika_jia
  85. * created: 2024.10.17 16:31:13
  86. */
点赞(0)
 

9.9 分

2 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论