[关闭]
@zhshh 2021-04-21T02:49:03.000000Z 字数 3635 阅读 1120

线段树

@zhshh cpp OI 数据结构

模板

单标记（加、max、min）

回到顶部

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #define cnt tree[root]
  5. #define lr (root<<1)
  6. #define rr ((root<<1)|1)
  7. #define lt tree[lr]
  8. #define rt tree[rr]
  9. #define MX (100010)
  10. #define LL long long
  11. using namespace std;
  12. struct node{
  13.     int left,right;
  14.     LL add,val;
  15.     node(){
  16.         add=0;
  17.     }
  18. }tree[MX<<2];
  19. LL a[MX];
  20. int n;
  21. void pushup(int root){
  22.     cnt.val=lt.val+rt.val;//更新换成自己的操作
  23. }
  24. void pushdown(int root){
  25.     if(cnt.add!=0){
  26.         lt.val=lt.val+cnt.add*(lt.right-lt.left+1);
  27.         lt.add=lt.add+cnt.add;
  28.         rt.val=rt.val+cnt.add*(rt.right-rt.left+1);
  29.         rt.add=rt.add+cnt.add;
  30.         cnt.add=0;
  31.     }
  32. }
  33. void add(int root,int left,int right,int c){
  34.     if(left<=cnt.left && right>=cnt.right){
  35.         cnt.add=cnt.add+c;
  36.         cnt.val=(cnt.val+c*(cnt.right-cnt.left+1));
  37.         return ;
  38.     }
  39.     pushdown(root);
  40.     int mid=cnt.left+cnt.right>>1;
  41.     if(left<=mid)add(lr,left,right,c);
  42.     if(right>mid)add(rr,left,right,c);
  43.     pushup(root);
  44.     return ;
  45. }
  46. LL query(int root,int left,int right){
  47.     if(left<=cnt.left && right>=cnt.right){
  48.         return cnt.val;
  49.     }
  50.     pushdown(root);
  51.     int mid=cnt.left+cnt.right>>1;
  52.     LL ans=0;
  53.     if(left<=mid)ans+=query(lr,left,right);
  54.     if(right>mid)ans+=query(rr,left,right);
  55.     return ans;
  56. }
  57. void build(int root,int left,int right){
  58.     cnt.left=left;
  59.     cnt.right=right;
  60.     if(left==right){
  61.         cnt.val=a[left];
  62.         return ;
  63.     }
  64.     int mid=(cnt.left+cnt.right)>>1;
  65.     build(lr,left,mid);
  66.     build(rr,mid+1,right);
  67.     pushup(root);
  68.     return ;
  69. }
  70. int main(){
  71.     int n,m;
  72.     cin>>n>>m;
  73.     for(int i=1;i<=n;i++){
  74.         cin>>a[i];
  75.     }
  76.     build(1,1,n);
  77.     int left,right,c;
  78.     for(int i=1;i<=m;i++){
  79.         cin>>c;
  80.         if(c==1){
  81.             cin>>left>>right>>c;
  82.             add(1,left,right,c);
  83.         }else{
  84.             cin>>left>>right;
  85.             cout<<query(1,left,right)<<endl;
  86.         }
  87.     }
  88.     return 0;
  89. }

双标记

回到顶部

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #define cnt tree[root]
  5. #define lr (root<<1)
  6. #define rr ((root<<1)|1)
  7. #define lt tree[lr]
  8. #define rt tree[rr]
  9. #define ci const int
  10. #define MX (100010+10)
  11. #define LL long long
  12. using namespace std;
  13. struct node{
  14.     int left,right;
  15.     LL add,mul,val;
  16.     node(){
  17.         mul=1;
  18.         add=0;
  19.     }
  20. }tree[MX<<2];
  21. LL a[MX];
  22. int n;
  23. LL mod;
  24. void pushup(ci root){
  25.     cnt.val=lt.val+rt.val;
  26. }
  27. void pushdown(ci root){
  28.     if(cnt.mul!=1 || cnt.add!=0){
  29.         lt.val=(lt.val*cnt.mul)%mod;
  30.         lt.val=(lt.val+cnt.add*(lt.right-lt.left+1))%mod;
  31.         lt.add=(lt.add*cnt.mul)%mod;
  32.         lt.add=(lt.add+cnt.add)%mod;
  33.         lt.mul=(lt.mul*cnt.mul)%mod;
  35.         rt.val=(rt.val*cnt.mul)%mod;
  36.         rt.val=(rt.val+cnt.add*(rt.right-rt.left+1))%mod;
  37.         rt.add=(rt.add*cnt.mul)%mod;
  38.         rt.add=(rt.add+cnt.add)%mod;
  39.         rt.mul=(rt.mul*cnt.mul)%mod;
  41.         cnt.mul=1;
  42.         cnt.add=0;
  43.     }
  44. }
  45. void mul(ci root,ci left,ci right,ci k){
  46.     if(left<=cnt.left && right>=cnt.right){
  47.         cnt.mul=(cnt.mul*k)%mod;
  48.         cnt.add=(cnt.add*k)%mod;
  49.         cnt.val=(cnt.val*k)%mod;
  50.         return ;
  51.     }
  52.     pushdown(root);
  53.     int mid=(cnt.left+cnt.right)>>1;
  54.     if(left<=mid)mul(lr,left,right,k);
  55.     if(right>mid)mul(rr,left,right,k);
  56.     pushup(root);
  57. }
  58. void add(ci root,ci left,ci right,ci c){
  59.     if(left<=cnt.left && right>=cnt.right){
  60.         cnt.add=(cnt.add+c)%mod;
  61.         cnt.val=(cnt.val+c*(cnt.right-cnt.left+1))%mod;
  62.         return ;
  63.     }
  64.     pushdown(root);
  65.     int mid=(cnt.left+cnt.right)>>1;
  66.     if(left<=mid)add(lr,left,right,c);
  67.     if(right>mid)add(rr,left,right,c);
  68.     pushup(root);
  69.     return ;
  70. }
  71. LL query(ci root,ci left,ci right){
  72.     if(left<=cnt.left && right>=cnt.right){
  73.         return cnt.val;
  74.     }
  75.     pushdown(root);
  76.     int mid=(cnt.left+cnt.right)>>1;
  77.     LL ans=0;
  78.     if(left<=mid)ans=(ans+query(lr,left,right))%mod;
  79.     if(right>mid)ans=(ans+query(rr,left,right))%mod;
  80.     return ans;
  81. }
  82. void build(ci root,ci left,ci right){
  83.     cnt.left=left;
  84.     cnt.right=right;
  85.     if(left==right){
  86.         cnt.val=a[left];
  87.         return ;
  88.     }
  89.     int mid=(cnt.left+cnt.right)>>1;
  90.     build(lr,left,mid);
  91.     build(rr,mid+1,right);
  92.     pushup(root);
  93.     return ;
  94. }
  95. void pr(){
  96.     for(int i=1;i<=n;i++){
  97.         printf("%3d%7d\n",i,query(1,i,i));
  98.     }
  99.     cout<<endl;
  100. }
  101. int main(){
  102. //    freopen("in.txt","r",stdin);
  103.     int m,t1,t2,t3;
  104.     cin>>n>>m>>mod;
  105.     for(int i=1;i<=n;i++){
  106.         cin>>a[i];
  107.         a[i]%=mod;
  108.     }
  109.     build(1,1,n);
  110.     for(int i=1;i<=m;i++){
  111.         cin>>t1;
  112.         if(t1==1){
  113.             cin>>t1>>t2>>t3;
  114.             mul(1,t1,t2,t3);
  115.         }else{
  116.             if(t1==2){
  117.                 cin>>t1>>t2>>t3;
  118.                 add(1,t1,t2,t3);
  119.             }else{
  120.                 cin>>t1>>t2;
  121.                 cout<<query(1,t1,t2)<<endl;
  122.             }
  123.         }
  124.     }
  125. //    pr(); 
  126. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注