Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #define MAXH 20 // 1+ceil(log2(400001))
- typedef long long ll;
- ll memosum[600001];
- ll sum(ll n)
- {
- if(n==0)
- return 0;
- if(memosum[n]!=0)
- return memosum[n];
- return memosum[n]=(n*(n+1))/2;
- }
- int n;
- struct Node
- {
- ll sum;
- int a,b,x;
- ll delta;
- bool c;
- }T[1 << MAXH];
- void propagate(int n,int a,int b)
- {
- if(!T[n].c && !T[n].a && !T[n].b)
- return;
- if(T[n].c)
- {
- ll val=T[n].x;
- val *=(b-a+1);
- T[n].sum=val;
- }
- /*
- During set_range(type 'C') we cleared node.a , node.b and node.delta. So, if these are not found cleared during propagate,
- then some query of type 'A' or 'B' must have been called after query 'C'.
- Sum+=(k*delta_t + (nA+nB)*((k*(k+1))/2)
- where k=(b-a+1);
- */
- T[n].sum+=(b-a+1) * T[n].delta;
- T[n].sum+=sum(b-a+1) * (T[n].a+T[n].b);
- if(a!=b)
- {
- int lt=(n<<1),rt=lt+1,m=(a+b)/2;
- if(T[n].c)
- {
- T[lt].c=T[rt].c=true;
- T[lt].a=T[rt].a=T[lt].b=T[rt].b=0;
- T[lt].delta=T[rt].delta=0;
- T[lt].x=T[rt].x=T[n].x;
- }
- T[lt].a+=T[n].a;
- T[lt].b+=T[n].b;
- T[rt].a+=T[n].a;
- T[rt].b+=T[n].b;
- ll delta=m+1-a;
- delta *=T[n].a;
- T[rt].delta+=T[n].delta+delta;
- delta=b-m;
- delta *=T[n].b;
- T[lt].delta+=T[n].delta+delta;
- }
- T[n].delta=0;
- T[n].a=T[n].b=T[n].x=0;
- T[n].c=false;
- }
- void increment_from_left(int i,int j,int n,int a,int b)
- {
- propagate(n,a,b);
- if(j < a || i > b)
- return;
- if(a==b)
- {
- T[n].sum+=a-i+1;
- return;
- }
- int lt=(n<<1),rt=lt+1,m=(a+b)/2;
- if(a >=i && b <=j)
- {
- T[n].sum+=sum(b-i+1)-sum(a-i);
- T[lt].delta+=a-i;
- ++T[lt].a;
- T[rt].delta+=m+1-i;
- ++T[rt].a;
- return;
- }
- increment_from_left(i,j,lt,a,m);
- increment_from_left(i,j,rt,m+1,b);
- T[n].sum=T[rt].sum+T[lt].sum;
- }
- void increment_from_right(int i,int j,int n,int a,int b)
- {
- propagate(n,a,b);
- if(j < a || i > b)
- return;
- if(a==b)
- {
- T[n].sum+=j-b+1;
- return;
- }
- int lt=(n<<1),rt=lt+1,m=(a+b)/2;
- if(a >=i && b <=j)
- {
- T[n].sum+=sum(j-a+1)-sum(j-b);
- T[lt].delta+=j-m;
- ++T[lt].b;
- T[rt].delta+=j-b;
- ++T[rt].b;
- return;
- }
- increment_from_right(i,j,lt,a,m);
- increment_from_right(i,j,rt,m+1,b);
- T[n].sum=T[rt].sum+T[lt].sum;
- }
- void set_range(int i,int j,int sum,int n,int a,int b)
- {
- propagate(n,a,b);
- if(j < a || i > b)
- return;
- if(a==b)
- {
- T[n].sum=sum;
- return;
- }
- int lt=(n<<1),rt=lt|1,m=(a+b)/2;
- if(a >=i && b <=j)
- {
- T[n].sum=(sum*(b-a+1));
- T[lt].x=T[rt].x=sum;
- T[lt].c=T[rt].c=true;
- T[lt].a=T[lt].b=0;
- T[rt].a=T[rt].b=0;
- T[lt].delta=T[rt].delta=0;
- return;
- }
- set_range(i,j,sum,lt,a,m);
- set_range(i,j,sum,rt,m+1,b);
- T[n].sum=T[rt].sum+T[lt].sum;
- }
- ll query(int i,int j,int n,int a,int b)
- {
- if(j < a || i > b)
- return 0;
- propagate(n,a,b);
- if(a>=i && b<=j)
- return T[n].sum;
- int lt=(n<<1),rt=lt+1,m=(a+b)/2;
- return query(i,j,lt,a,m)+query(i,j,rt,m+1,b);
- }
- int main()
- {
- int i,j,x,m,t,op;
- n=400000;
- scanf("%d",&m);
- while (m--)
- {
- scanf("%d%d%d",&op,&i,&j);
- switch(op)
- {
- case 1:
- increment_from_left(i,j,1,1,n);
- break;
- case 2:
- increment_from_right(i,j,1,1,n);
- break;
- case 3:
- scanf("%d",&x);
- set_range(i,j,x,1,1,n);
- break;
- case 4:
- printf("%lld\n",query(i,j,1,1,n));
- break;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment