Submit Info #12852

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum cpp kaage AC 839 ms 39.84 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.72 MiB
max_random_00 AC 820 ms 39.80 MiB
max_random_01 AC 839 ms 39.84 MiB
max_random_02 AC 832 ms 39.80 MiB
medium_00 AC 7 ms 0.84 MiB
medium_01 AC 6 ms 0.68 MiB
medium_02 AC 4 ms 0.67 MiB
random_00 AC 528 ms 20.67 MiB
random_01 AC 585 ms 39.10 MiB
random_02 AC 371 ms 10.64 MiB
small_00 AC 1 ms 0.72 MiB
small_01 AC 5 ms 0.67 MiB
small_02 AC 2 ms 0.67 MiB
small_03 AC 1 ms 0.67 MiB
small_04 AC 1 ms 0.68 MiB
small_05 AC 9 ms 0.70 MiB
small_06 AC 1 ms 0.67 MiB
small_07 AC 1 ms 0.68 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 1 ms 0.43 MiB

#define _CRT_SECURE_NO_WARNINGS #pragma tarquery("avx") #pragma optimize("O3") #pragma optimize("unroll-loops") #include <algorithm> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define rep(i,n) for(int i=0;i<(lint)(n);i++) #define REP(i,n) for(int i=1;i<=(lint)(n);i++) #define all(V) V.begin(),V.end() typedef long long lint; typedef unsigned long long ulint; typedef std::pair<lint, lint> P; constexpr int INF = INT_MAX/2; constexpr lint LINF = LLONG_MAX/2; constexpr double eps = DBL_EPSILON; constexpr double PI=3.141592653589793238462643383279; template<class T> class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {}; template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } inline lint gcd(lint a, lint b) { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) { return a / gcd(a, b) * b; } bool isprime(lint n) { if (n == 1)return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0)return false; } return true; } template<typename T> T mypow(T a, unsigned int b) { if (!b)return T(1); if (b & 1)return mypow(a, b - 1) * a; T memo = mypow(a, b >> 1); return memo * memo; } lint modpow(lint a, lint b, lint m) { if (!b)return 1; if (b & 1)return modpow(a, b - 1, m) * a % m; lint memo = modpow(a, b >> 1, m); return memo * memo % m; } template<typename T> void printArray(std::vector<T>& vec) { rep(i, vec.size() - 1)std::cout << vec[i] << " "; std::cout << vec.back() << std::endl; } template<typename T> void printArray(T l, T r) { T rprev = r; rprev--; for (T i = l; i != rprev; i++) { std::cout << *i << " "; } std::cout << *rprev << std::endl; } class SegTreeBeats{ unsigned int n; std::vector<lint> width,min[2],minc,max[2],maxc,sum,addlazy; void eval(int k){ if(n-1<=k)return; if(addlazy[k]){ update_node_add(2*k+1,addlazy[k]); update_node_add(2*k+2,addlazy[k]); addlazy[k]=0; } if(max[0][k]<max[0][2*k+1]){ update_node_max(2*k+1,max[0][k]); } if(min[0][k]>min[0][2*k+1]){ update_node_min(2*k+1,min[0][k]); } if(max[0][k]<max[0][2*k+2]){ update_node_max(2*k+2,max[0][k]); } if(min[0][k]>min[0][2*k+2]){ update_node_min(2*k+2,min[0][k]); } } void combine(int k){ sum[k]=sum[2*k+1]+sum[2*k+2]; if(min[0][2*k+1]<min[0][2*k+2]){ min[0][k]=min[0][2*k+1]; minc[k]=minc[2*k+1]; min[1][k]=std::min(min[1][2*k+1],min[0][2*k+2]); } else if(min[0][2*k+1]>min[0][2*k+2]){ min[0][k]=min[0][2*k+2]; minc[k]=minc[2*k+2]; min[1][k]=std::min(min[0][2*k+1],min[1][2*k+2]); } else{ min[0][k]=min[0][2*k+1]; minc[k]=minc[2*k+1]+minc[2*k+2]; min[1][k]=std::min(min[1][2*k+1],min[1][2*k+2]); } if(max[0][2*k+1]>max[0][2*k+2]){ max[0][k]=max[0][2*k+1]; maxc[k]=maxc[2*k+1]; max[1][k]=std::max(max[1][2*k+1],max[0][2*k+2]); } else if(max[0][2*k+1]<max[0][2*k+2]){ max[0][k]=max[0][2*k+2]; maxc[k]=maxc[2*k+2]; max[1][k]=std::max(max[0][2*k+1],max[1][2*k+2]); } else{ max[0][k]=max[0][2*k+1]; maxc[k]=maxc[2*k+1]+maxc[2*k+2]; max[1][k]=std::max(max[1][2*k+1],max[1][2*k+2]); } } void update_node_max(int k,lint x){ sum[k]+=(x-max[0][k])*maxc[k]; if(max[0][k]==min[0][k])min[0][k]=x; else if(max[0][k]==min[1][k])min[1][k]=x; max[0][k]=x; } void update_node_min(int k,lint x){ sum[k]+=(x-min[0][k])*minc[k]; if(min[0][k]==max[0][k])max[0][k]=x; else if(min[0][k]==max[1][k])max[1][k]=x; min[0][k]=x; } void update_node_add(int k,lint x){ min[0][k]+=x; if(min[1][k]!=LINF)min[1][k]+=x; max[0][k]+=x; if(max[1][k]!=-LINF)max[1][k]+=x; sum[k]+=x*width[k]; addlazy[k]+=x; } public: SegTreeBeats(unsigned int size,lint def=0){ n=1; while(n<size)n*=2; width.resize(2*n-1); min[0].resize(2*n-1,def);min[1].resize(2*n-1,LINF); minc.resize(2*n-1); max[0].resize(2*n-1,def);max[1].resize(2*n-1,-LINF); maxc.resize(2*n-1); sum.resize(2*n-1); addlazy.resize(2*n-1); width[0]=n; REP(i,2*n-2)width[i]=width[(i-1)/2]/2; minc=maxc=width; rep(i,2*n-1)sum[i]=def*width[i]; } SegTreeBeats(std::vector<lint> initvec){ n=1; while(n<initvec.size())n*=2; width.resize(2*n-1); min[0].resize(2*n-1);min[1].resize(2*n-1,LINF); minc.resize(2*n-1); max[0].resize(2*n-1);max[1].resize(2*n-1,-LINF); maxc.resize(2*n-1); sum.resize(2*n-1); addlazy.resize(2*n-1); for(int i=n-1;i<n-1+initvec.size();i++){ min[0][i]=max[0][i]=sum[i]=initvec[i-n+1]; minc[i]=maxc[i]=1; } for(int i=n-2;i>=0;i--){ combine(i); } width[0]=n; REP(i,2*n-2)width[i]=width[(i-1)/2]/2; } void update_min(int a,int b,lint x,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a||max[0][k]<=x)return; if(a<=l&&r<=b&&max[1][k]<x){ update_node_max(k,x); return; } eval(k); update_min(a,b,x,2*k+1,l,(l+r)/2); update_min(a,b,x,2*k+2,(l+r)/2,r); combine(k); } void update_max(int a,int b,lint x,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a||x<=min[0][k])return; if(a<=l&&r<=b&&x<min[1][k]){ update_node_min(k,x); return; } eval(k); update_max(a,b,x,2*k+1,l,(l+r)/2); update_max(a,b,x,2*k+2,(l+r)/2,r); combine(k); } void update_add(int a,int b,lint x,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a)return; if(a<=l&&r<=b){ update_node_add(k,x); return; } eval(k); update_add(a,b,x,2*k+1,l,(l+r)/2); update_add(a,b,x,2*k+2,(l+r)/2,r); combine(k); } lint query_sum(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a)return 0; if(a<=l&&r<=b)return sum[k]; eval(k); lint vl=query_sum(a,b,2*k+1,l,(l+r)/2); lint vr=query_sum(a,b,2*k+2,(l+r)/2,r); return vl+vr; } lint query_min(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a)return LINF; if(a<=l&&r<=b)return min[0][k]; eval(k); lint vl=query_min(a,b,2*k+1,l,(l+r)/2); lint vr=query_min(a,b,2*k+2,(l+r)/2,r); return std::min(vl,vr); } lint query_max(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(b<=l||r<=a)return -LINF; if(a<=l&&r<=b)return max[0][k]; eval(k); lint vl=query_max(a,b,2*k+1,l,(l+r)/2); lint vr=query_max(a,b,2*k+2,(l+r)/2,r); return std::max(vl,vr); } void print(){ rep(i,2*n-1)std::cout<<sum[i]<<" "; std::cout<<std::endl; rep(i,2*n-1)std::cout<<min[0][i]<<" "; std::cout<<std::endl; rep(i,2*n-1)std::cout<<max[0][i]<<" "; std::cout<<std::endl; } }; int n,q; int main(){ std::cin>>n>>q; std::vector<lint> vec(n); rep(i,n)std::cin>>vec[i]; SegTreeBeats beats(vec); rep(i,q){ //beats.print(); int t; std::cin>>t; if(t==0){ lint l,r,b; std::cin>>l>>r>>b; beats.update_min(l,r,b); } else if(t==1){ lint l,r,b; std::cin>>l>>r>>b; beats.update_max(l,r,b); } else if(t==2){ lint l,r,b; std::cin>>l>>r>>b; beats.update_add(l,r,b); } else{ lint l,r; std::cin>>l>>r; std::cout<<beats.query_sum(l,r)<<std::endl; } } return 0; }