文章

35

粉丝

599

获赞

6

访问

312.4k

头像
用线段树板子会超时啊 40%
P1604
发布于2020年5月11日 17:09
阅读数 7.1k

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <string>
  6. #include <vector>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn=2e5+1;
  10. #define lson x<<1
  11. #define rson (x<<1)+1
  12. ll tree[maxn<<2];
  13. ll lazy[maxn<<2];
  14. int arr[maxn];
  15. ll ans;
  16. int n,m;
  17. void push_up(int x){
  18. tree[x]=tree[lson]+tree[rson];
  19. }
  20. void push_down(int x,int l,int r){//向下传递标记
  21. int mid=(l+r)/2;
  22. if(lazy[x]){
  23. lazy[lson]+=lazy[x];
  24. lazy[rson]+=lazy[x];
  25. tree[lson]+=(mid-l+1)*lazy[x];
  26. tree[rson]+=(r-mid)*lazy[x];
  27. lazy[x]=0;//取消本层标记
  28. }
  29. }
  30. void create(int x,int l,int r){
  31. lazy[x]=0;
  32. if(l==r){
  33. tree[x]=arr[l];
  34. return;
  35. }
  36. int mid=(l+r)/2;
  37. create(lson, l, mid);
  38. create(rson, mid+1, r);
  39. push_up(x);
  40. }
  41. void add(int x,int l,int r,int L,int R, int val){
  42. if(L<=l&&R>=r){
  43. tree[x]+=(r-l+1)*val;
  44. lazy[x]+=val;
  45. return;
  46. }
  47. push_down(x, l, r);
  48. int mid=(l...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发