yicongli

T165T1

Mar 31st, 2019
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     T k=1;char gc;x=0;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c))x=x*10+c-'0',gc;x*=k;
  14. }
  15.  
  16. const int N=1e5+7;
  17.  
  18. inline ll s0(ll x){
  19.     return x;
  20. }
  21.  
  22. inline ll s1(ll x){
  23.     return x*(x+1)/2;
  24. }
  25.  
  26. inline ll s2(ll x){
  27.     return x*(x+1)*(2*x+1)/6;
  28. }
  29.  
  30. struct Info{
  31.     ll v0,v1,v2;
  32. };
  33.  
  34. inline Info operator + (const Info &a,const Info &b){
  35.     return Info{a.v0+b.v0,a.v1+b.v1,a.v2+b.v2};
  36. }
  37.  
  38. struct Node{
  39.     Info sum;
  40.     ll tag;
  41. }tr[N<<2];
  42.  
  43. int a[N];
  44.  
  45. #define ls (rt<<1)
  46. #define rs (rt<<1|1)
  47.  
  48. inline void update(int rt){
  49.     tr[rt].sum=tr[ls].sum+tr[rs].sum;
  50. }
  51.  
  52. inline void pushdown(int rt,int l,int r){
  53.     if(tr[rt].tag){
  54.         int mid=(l+r)>>1;
  55.         tr[ls].sum.v0+=tr[rt].tag*(s0(mid)-s0(l-1));
  56.         tr[ls].sum.v1+=tr[rt].tag*(s1(mid)-s1(l-1));
  57.         tr[ls].sum.v2+=tr[rt].tag*(s2(mid)-s2(l-1));
  58.         tr[rs].sum.v0+=tr[rt].tag*(s0(r)-s0(mid));
  59.         tr[rs].sum.v1+=tr[rt].tag*(s1(r)-s1(mid));
  60.         tr[rs].sum.v2+=tr[rt].tag*(s2(r)-s2(mid));
  61.         tr[ls].tag+=tr[rt].tag;
  62.         tr[rs].tag+=tr[rt].tag;
  63.         tr[rt].tag=0;
  64.     }
  65. }
  66.  
  67. void modify(int rt,int l,int r,int x,int y,ll v){
  68.     if(x<=l&&r<=y){
  69.         tr[rt].sum.v0+=v*(s0(r)-s0(l-1));
  70.         tr[rt].sum.v1+=v*(s1(r)-s1(l-1));
  71.         tr[rt].sum.v2+=v*(s2(r)-s2(l-1));
  72.         tr[rt].tag+=v;
  73.         return ;
  74.     }
  75.     int mid=(l+r)>>1;
  76.     pushdown(rt,l,r);
  77.     if(x<=mid)modify(ls,l,mid,x,y,v);
  78.     if(y>mid)modify(rs,mid+1,r,x,y,v);
  79.     update(rt);
  80. }
  81.  
  82. Info query(int rt,int l,int r,int x,int y){
  83.     if(x<=l&&r<=y)return tr[rt].sum;
  84.     int mid=(l+r)>>1;
  85.     pushdown(rt,l,r);
  86.     if(y<=mid)return query(ls,l,mid,x,y);
  87.     if(x>mid)return query(rs,mid+1,r,x,y);
  88.     return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
  89. }
  90.  
  91. inline char GetChar(){
  92.     char gc;
  93.     while(c!='C'&&c!='Q')gc;
  94.     return c;
  95. }
  96.  
  97. int main(){
  98.     freopen("snaker.in","r",stdin);
  99.     freopen("snaker.out","w",stdout);
  100.     int n,m;r(n),r(m);
  101.     --n;
  102.     while(m--){
  103.         char c=GetChar();
  104.         int l,r;r(l),r(r),--r;
  105.         if(c=='C'){
  106.             int x;r(x);
  107.             // for(int i=l;i<=r;++i){
  108.             //  a[i]+=x;
  109.             // }
  110.             modify(1,1,n,l,r,x);
  111.         }
  112.         else {
  113.             // ll sum0,sum1,sum2,ans,tot;
  114.             // sum2=sum1=sum0=0;
  115.             // for(int i=l;i<=r;++i){
  116.             //  sum2+=(ll)i*i*a[i];
  117.             //  sum1+=(ll)i*a[i];
  118.             //  sum0+=a[i];
  119.             // }
  120.             Info sum=query(1,1,n,l,r);
  121.             ll ans=-sum.v2+sum.v1*(l+r)-sum.v0*(r+1)*(l-1);
  122.             ll tot=(ll)(r-l+1)*(r-l+2)/2;
  123.             ll g=__gcd(ans,tot);
  124.             ans/=g,tot/=g;
  125.             printf("%lld/%lld\n",ans,tot);
  126.         }
  127.     }
  128. }
Advertisement
Add Comment
Please, Sign In to add comment