fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long
  5. #define int long long
  6. struct SegmentTree{
  7. private:
  8.     int sz=1,skip=0;
  9.     vector<int>seg,lazy;
  10.     void propegate(int l,int r,int node)
  11.     {
  12.         if(lazy[node]==0)return;
  13.         if(l!=r)
  14.         {
  15.             lazy[2*node+1]+=lazy[node];
  16.             lazy[2*node+2]+=lazy[node];
  17.         }
  18.         int len=r-l+1;
  19.         seg[node]+=len*lazy[node];
  20.         lazy[node]=0;
  21.     }
  22.     void update(int l,int r,int node,int lx,int rx,int val)
  23.     {
  24.         propegate(l,r,node);
  25.         if(l>rx||r<lx)
  26.         {
  27.             return;
  28.         }
  29.         if(l>=lx&&r<=rx)
  30.         {
  31.             lazy[node]+=val;
  32.             propegate(l,r,node);
  33.             return;
  34.         }
  35.         int mid=l+r>>1;
  36.         update(l,mid,2*node+1,lx,rx,val);
  37.         update(mid+1,r,2*node+2,lx,rx,val);
  38.         seg[node]=seg[2*node+1]+seg[2*node+2];
  39.     }
  40.     int query(int l,int r,int node,int lx,int rx)
  41.     {
  42.         propegate(l,r,node);
  43.         if(l>=lx&&r<=rx)
  44.         {
  45.             return seg[node];
  46.         }
  47.         if(l>rx||r<lx)
  48.         {
  49.             return skip;
  50.         }
  51.         int mid=l+r>>1;
  52.         return query(l,mid,2*node+1,lx,rx)+query(mid+1,r,2*node+2,lx,rx);
  53.     }
  54. public:
  55.     void update(int l,int r,int val)
  56.     {
  57.         update(0,sz-1,0,l,r,val);
  58.     }
  59.     int query(int l,int r)
  60.     {
  61.         return query(0,sz-1,0,l,r);
  62.     }
  63.     SegmentTree(int n){
  64.         while(sz<=n)sz*=2;
  65.         seg=vector<int>(sz*2,0);
  66.         lazy=vector<int>(sz*2,0);
  67.     }
  68. };
  69. struct SegmentTreeBeats{
  70. private:
  71. #define L 2*node+1
  72. #define R 2*node+2
  73. #define mid (l+r>>1)
  74. #define inf 1e15+5
  75.     struct Node{
  76.         int sum,mx,secMx,mxCnt,mn,mnCnt,secMn,lazyAdd,lazySet;
  77.         Node(int summ,int mxx,int secMxx,int mxCntt,int mnn,int secMnn,int mnCntt,int add=0,int set=-1)
  78.                 :sum(summ),mx(mxx),secMx(secMxx),mxCnt(mxCntt),
  79.                  mn(mnn),secMn(secMnn),mnCnt(mnCntt),
  80.                  lazyAdd(add),lazySet(set){}
  81.     };
  82.     int sz;vector<Node>seg;
  83.     Node merge(Node&a,Node&b)
  84.     {
  85.         Node ret(0,-inf,-inf,0,inf,inf,0,0,-1);
  86.         ret.sum=a.sum+b.sum;
  87.         ret.mx=max(a.mx,b.mx);// max
  88.         ret.secMx=max(a.secMx,b.secMx);
  89.         if(ret.mx==a.mx) ret.mxCnt+=a.mxCnt;
  90.         else ret.secMx=max(ret.secMx,a.mx);
  91.         if(ret.mx==b.mx) ret.mxCnt+=b.mxCnt;
  92.         else ret.secMx=max(ret.secMx,b.mx);
  93.         ret.mn=min(a.mn,b.mn);// min
  94.         ret.secMn=min(a.secMn,b.secMn);
  95.         if(ret.mn==a.mn) ret.mnCnt+=a.mnCnt;
  96.         else ret.secMn=min(ret.secMn,a.mn);
  97.         if(ret.mn==b.mn) ret.mnCnt+=b.mnCnt;
  98.         else ret.secMn=min(ret.secMn,b.mn);
  99.         return ret;
  100.     }
  101.     void pushSet(int l,int r,int node,int val)
  102.     {
  103.         seg[node]=Node(val*(r-l+1),val,-inf,r-l+1,val,inf,r-l+1,0,val);
  104.     }
  105.     void pushMin(int l,int r,int node,int mn)
  106.     {
  107.         if(seg[node].mn>=mn)
  108.         {
  109.             pushSet(l,r,node,mn);
  110.             return;
  111.         }
  112.         if(seg[node].mx>mn)
  113.         {
  114.             if(seg[node].secMn==seg[node].mx) seg[node].secMn=mn;
  115.             int val=seg[node].mx-mn;
  116.             seg[node].sum-=val*seg[node].mxCnt;
  117.             seg[node].mx=mn;
  118.         }
  119.     }
  120.     void pushMax(int l,int r,int node,int mx)
  121.     {
  122.         if(seg[node].mx<=mx)
  123.         {
  124.             pushSet(l,r,node,mx);
  125.             return;
  126.         }
  127.         if(seg[node].mn<mx)
  128.         {
  129.             if(seg[node].secMx==seg[node].mn) seg[node].secMx=mx;
  130.             int val=mx-seg[node].mn;
  131.             seg[node].sum+=val*seg[node].mnCnt;
  132.             seg[node].mn=mx;
  133.         }
  134.     }
  135.     void pushAdd(int l,int r,int node,int val)
  136.     {
  137.         if(seg[node].mx==seg[node].mn)
  138.         {
  139.             pushSet(l,r,node,seg[node].mn+val);
  140.             return;
  141.         }
  142.         seg[node].mx+=val;
  143.         if(seg[node].secMx!=-inf)  seg[node].secMx+=val;
  144.         seg[node].mn+=val;
  145.         if(seg[node].secMn!=inf)  seg[node].secMn+=val;
  146.         seg[node].sum+=(r-l+1)*val;
  147.         seg[node].lazyAdd+=val;
  148.     }
  149.     void propegate(int l,int r,int node)
  150.     {
  151.         if(l==r) return;
  152.         if(seg[node].lazySet!=-1)
  153.         {
  154.             pushSet(l,mid,L,seg[node].lazySet);
  155.             pushSet(mid+1,r,R,seg[node].lazySet);
  156.             seg[node].lazySet=-1;
  157.         }
  158.         else
  159.         {
  160.             pushAdd(l,mid,L,seg[node].lazyAdd);
  161.             pushAdd(mid+1,r,R,seg[node].lazyAdd);
  162.             seg[node].lazyAdd=0;
  163.             pushMin(l,mid,L,seg[node].mx);
  164.             pushMin(mid+1,r,R,seg[node].mx);
  165.             pushMax(l,mid,L,seg[node].mn);
  166.             pushMax(mid+1,r,R,seg[node].mn);
  167.         }
  168.     }
  169.     void build(int l,int r,int node,vector<int>&v)
  170.     {
  171.         if(l==r)
  172.         {
  173.             if(l<v.size())
  174.             {
  175.                 seg[node]=Node(v[l],v[l],-inf,1,v[l],inf,1);
  176.             }
  177.             return;
  178.         }
  179.         build(l,mid,L,v);
  180.         build(mid+1,r,R,v);
  181.         seg[node]= merge(seg[L],seg[R]);
  182.     }
  183.     void updateAdd(int l,int r,int node,int lx,int rx,int val)
  184.     {
  185.         if(l>rx||r<lx)return;
  186.         if(l>=lx&&r<=rx)
  187.         {
  188.             pushAdd(l,r,node,val);
  189.             return;
  190.         }
  191.         propegate(l,r,node);
  192.         updateAdd(l,mid,L,lx,rx,val);
  193.         updateAdd(mid+1,r,R,lx,rx,val);
  194.         seg[node]=merge(seg[L],seg[R]);
  195.     }
  196.     void updateSet(int l,int r,int node,int lx,int rx,int val)
  197.     {
  198.         if(l>rx||r<lx)return;
  199.         if(l>=lx&&r<=rx)
  200.         {
  201.             pushSet(l,r,node,val);
  202.             return;
  203.         }
  204.         propegate(l,r,node);
  205.         updateSet(l,mid,L,lx,rx,val);
  206.         updateSet(mid+1,r,R,lx,rx,val);
  207.         seg[node]=merge(seg[L],seg[R]);
  208.     }
  209.     void updateMin(int l,int r,int node,int lx,int rx,int mn)
  210.     {
  211.         if(r<lx||l>rx||seg[node].mx<=mn) return;
  212.         if(l>=lx&&r<=rx&&mn>seg[node].secMx)
  213.         {
  214.             pushMin(l,r,node,mn);
  215.             return;
  216.         }
  217.         propegate(l,r,node);
  218.         updateMin(l,mid,L,lx,rx,mn);
  219.         updateMin(mid+1,r,R,lx,rx,mn);
  220.         seg[node]=merge(seg[L],seg[R]);
  221.     }
  222.     void updateMax(int l,int r,int node,int lx,int rx,int mx)
  223.     {
  224.         if(l>rx||r<lx||mx<=seg[node].mn) return;
  225.         if(l>=lx&&r<=rx&&mx<seg[node].secMn)
  226.         {
  227.             pushMax(l,r,node,mx);
  228.             return;
  229.         }
  230.         propegate(l,r,node);
  231.         updateMax(l,mid,L,lx,rx,mx);
  232.         updateMax(mid+1,r,R,lx,rx,mx);
  233.         seg[node]=merge(seg[L],seg[R]);
  234.     }
  235.     int querySum(int l,int r,int node,int lx,int rx)
  236.     {
  237.         if(l>rx||r<lx)return 0;
  238.         if(l>=lx&&r<=rx)return seg[node].sum;
  239.         propegate(l,r,node);
  240.         return querySum(l,mid,L,lx,rx)+querySum(mid+1,r,R,lx,rx);
  241.     }
  242.     int queryMin(int l,int r,int node,int lx,int rx)
  243.     {
  244.         if(l>rx||r<lx)return inf;
  245.         if(l>=lx&&r<=rx)return seg[node].mn;
  246.         propegate(l,r,node);
  247.         return min(queryMin(l,mid,L,lx,rx),queryMin(mid+1,r,R,lx,rx));
  248.     }
  249.     int queryMax(int l,int r,int node,int lx,int rx)
  250.     {
  251.         if(l>rx||r<lx)return -inf;
  252.         if(l>=lx&&r<=rx)return seg[node].mx;
  253.         propegate(l,r,node);
  254.         return max(queryMax(l,mid,L,lx,rx),queryMax(mid+1,r,R,lx,rx));
  255.     }
  256. #undef L
  257. #undef R
  258. #undef mid
  259. public:
  260.     SegmentTreeBeats(vector<int>&v)
  261.     {
  262.         int n=v.size()+5;
  263.         sz=1;
  264.         while(sz<=n)sz<<=1;
  265.         seg=vector<Node>(sz<<1,Node(0,-inf,-inf,0,inf,inf,0,0,-1));
  266.         build(0,sz-1,0,v);
  267.     }
  268.     void updateAdd(int l,int r,int val)
  269.     {
  270.         updateAdd(0,sz-1,0,l,r,val);
  271.     }
  272.     void updateSet(int l,int r,int val)
  273.     {
  274.         updateSet(0,sz-1,0,l,r,val);
  275.     }
  276.     void updateMin(int l,int r,int mn)
  277.     {
  278.         updateMin(0,sz-1,0,l,r,mn);
  279.     }
  280.     void updateMax(int l,int r,int mx)
  281.     {
  282.         updateMax(0,sz-1,0,l,r,mx);
  283.     }
  284.     int queryMax(int l,int r)
  285.     {
  286.         return queryMax(0,sz-1,0,l,r);
  287.     }
  288.     int queryMin(int l,int r)
  289.     {
  290.         return queryMin(0,sz-1,0,l,r);
  291.     }
  292.     int querySum(int l,int r)
  293.     {
  294.         return querySum(0,sz-1,0,l,r);
  295.     }
  296. #undef inf
  297. };
  298. signed main()
  299. {
  300.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  301.     int n,q;cin>>n>>q;
  302.     vector<int>s(n+1);
  303.     SegmentTree tree(n+5);
  304.     for(int i=1;i<=n;i++)
  305.     {
  306.         cin>>s[i];
  307.         tree.update(i,i,s[i]);
  308.     }
  309.     vector<int>v(n+1);
  310.     SegmentTreeBeats beats(v);
  311.     while(q--)
  312.     {
  313.         int op;cin>>op;
  314.         if(op==1)
  315.         {
  316.             int l,r,x;cin>>l>>r>>x;
  317.             tree.update(l,r,x);
  318.             beats.updateAdd(l,r,-x);
  319.             beats.updateMax(l,r,0);
  320.         }
  321.         else
  322.         {
  323.             int l,r;cin>>l>>r;
  324.             cout<<tree.query(l,r)+beats.querySum(l,r)<<'\n';
  325.         }
  326.     }
  327.     return 0;
  328. }
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
1 5
1
1 1 1 99
1 1 1 -99
2 1 1
1 1 1 100
2 1 1
stdout
copy 
100
101
https://ideone.com/aAVENq
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!