fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long int ll;
  3. typedef long double ld;
  4. using namespace std;
  5. const ll mod=1e9+7;
  6. const ll inf = (ll)1e17;
  7. const ld eps = 1e-12;
  8. const ld PI = 3.14159265358979323846;
  9. ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  10. ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  11. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  12. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  13.  
  14. const int N=100005;
  15. pair<ll,ll> tree[4*N];
  16. pair<ll,ll> lazy[4*N];
  17. int n;
  18. vector<ll>arr;
  19.  
  20. void push(int node,int l,int r){
  21.     if(lazy[node].first){
  22.         lazy[2*node].second=lazy[2*node+1].second=0;
  23.         int mid=(l+r)/2;
  24.         tree[2*node].first=(mid-l+1)*lazy[node].first;
  25.         tree[2*node].second=(mid-l+1)*lazy[node].first*lazy[node].first;
  26.         tree[2*node+1].first=(r-mid)*lazy[node].first;
  27.         tree[2*node+1].second=(r-mid)*lazy[node].first*lazy[node].first;
  28.         lazy[2*node].first=lazy[node].first;
  29.         lazy[2*node+1].first=lazy[node].first;
  30.         lazy[node].first=0;
  31.     }
  32.     if(lazy[node].second){
  33.         int mid=(l+r)/2;
  34.         tree[2*node].second+=(tree[2*node].first*(2*lazy[node].second))+(mid-l+1)*powmod(lazy[node].second,2);
  35.         tree[2*node+1].second+=(tree[2*node].first*(2*lazy[node].second))+(r-mid)*powmod(lazy[node].second,2);
  36.         tree[2*node].first+=((mid-l+1)*lazy[node].second);
  37.         tree[2*node+1].first+=((r-mid)*lazy[node].second);
  38.         lazy[2*node].second+=lazy[node].second;
  39.         lazy[2*node+1].second+=lazy[node].second;
  40.         lazy[node].second=0;
  41.     }
  42. }
  43.  
  44.  
  45. void build(int node,int l,int r){
  46.     if(l==r){
  47.         tree[node].first=arr[l];
  48.         tree[node].second=arr[l]*arr[l];
  49.         lazy[node].first=lazy[node].second=0;
  50.         return;
  51.     }
  52.     int mid=(l+r)/2;
  53.     build(2*node,l,mid);
  54.     build(2*node+1,mid+1,r);
  55.     tree[node].first=tree[2*node].first+tree[2*node+1].first;
  56.     tree[node].second=tree[2*node].second+tree[2*node+1].second;
  57.     lazy[node].first=lazy[node].second=0;
  58.     }
  59.  
  60.  
  61. void update(int node,int l,int r,int l1,int r1,ll val,int type){
  62.     if(l1>r1 || l>r1|| l1>r)return ;
  63.     if(l1<=l && r<=r1){
  64.         if(type==0){
  65.             tree[node].first=(r-l+1)*val;
  66.             tree[node].second=(r-l+1)*val*val;
  67.             lazy[node].second=0;
  68.             lazy[node].first=val;
  69.         }
  70.         else{
  71.             tree[node].second+=(tree[node].first*2*val)+((r-l+1)*val*val);
  72.             tree[node].first+=((r-l+1)*val);
  73.             lazy[node].second+=val;
  74.         }
  75.         return;
  76.     }
  77.     push(node,l,r);
  78.     int mid=(r+l)/2;
  79.     update(2*node,l,mid,l1,r1,val,type);
  80.     update(2*node+1,mid+1,r,l1,r1,val,type);
  81.     tree[node].first=tree[2*node].first+tree[2*node+1].first;
  82.     tree[node].second=tree[2*node].second+tree[2*node+1].second;
  83.     }
  84.  
  85.  
  86. ll query(int node,int l,int r,int l1,int r1){
  87.     if(l1>r1 ||l>r1||l1>r)return ll(0);
  88.     if(l1<=l && r<=r1){
  89.         return tree[node].second;
  90.     }
  91.     push(node,l,r);
  92.     int mid=(l+r)/2;
  93.     return query(2*node,l,mid,l1,r1)+query(2*node+1,mid+1,r,l1,r1);
  94.     }
  95.  
  96.  
  97. int main(){
  98.     ios::sync_with_stdio(false);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101.     int t;
  102.     cin>>t;
  103.     for(int z=0;z<t;z++){
  104.         int q;
  105.         cin>>n>>q;
  106.         for(int i=0;i<n;i++){
  107.             ll a;
  108.             cin>>a;
  109.             arr.push_back(a);
  110.         }
  111.         build(1,0,n-1);
  112.         cout<<"case "<<z+1<<":"<<endl;
  113.         for(int i=0;i<q;i++){
  114.             int type;
  115.             cin>>type;
  116.             if(type==1){
  117.                 int l,r;
  118.                 ll val;
  119.                 cin>>l>>r>>val;
  120.                 l--;
  121.                 r--;
  122.                 update(1,0,n-1,l,r,val,1);
  123.             }
  124.             else if(type==0){
  125.                 int a,b;
  126.                 cin>>a>>b;
  127.                 ll val;
  128.                 cin>>val;
  129.                 a--;
  130.                 b--;
  131.                 update(1,0,n-1,a,b,val,0);
  132.             }
  133.             else{
  134.                 int l,r;
  135.                 cin>>l>>r;
  136.                 l--,r--;
  137.                 cout<<query(1,0,n-1,l,r)<<endl;
  138.             }
  139.         }
  140.         arr.clear();
  141.         for(int i=0;i<=4*N;i++){
  142.             tree[i].first=tree[i].second=0;
  143.             lazy[i].first=lazy[i].second=0;
  144.         }
  145.     }
  146.     return 0;
  147.     }
  148.  
Success #stdin #stdout 0s 16004KB
comments (?)
stdin
copy 
1
4 2
1 2 3 4
1 1 4 1
2 4 4
stdout
copy 
case 1:
23
https://ideone.com/GuxeYO
problem SEGSQRSS, based on SPOJ submission 24866735 (CPP14), 2019-11-15 02:37:55
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!