Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- T k=1;char gc;x=0;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c))x=x*10+c-'0',gc;x*=k;
- }
- const int N=1e5+7;
- inline ll s0(ll x){
- return x;
- }
- inline ll s1(ll x){
- return x*(x+1)/2;
- }
- inline ll s2(ll x){
- return x*(x+1)*(2*x+1)/6;
- }
- struct Info{
- ll v0,v1,v2;
- };
- inline Info operator + (const Info &a,const Info &b){
- return Info{a.v0+b.v0,a.v1+b.v1,a.v2+b.v2};
- }
- struct Node{
- Info sum;
- ll tag;
- }tr[N<<2];
- int a[N];
- #define ls (rt<<1)
- #define rs (rt<<1|1)
- inline void update(int rt){
- tr[rt].sum=tr[ls].sum+tr[rs].sum;
- }
- inline void pushdown(int rt,int l,int r){
- if(tr[rt].tag){
- int mid=(l+r)>>1;
- tr[ls].sum.v0+=tr[rt].tag*(s0(mid)-s0(l-1));
- tr[ls].sum.v1+=tr[rt].tag*(s1(mid)-s1(l-1));
- tr[ls].sum.v2+=tr[rt].tag*(s2(mid)-s2(l-1));
- tr[rs].sum.v0+=tr[rt].tag*(s0(r)-s0(mid));
- tr[rs].sum.v1+=tr[rt].tag*(s1(r)-s1(mid));
- tr[rs].sum.v2+=tr[rt].tag*(s2(r)-s2(mid));
- tr[ls].tag+=tr[rt].tag;
- tr[rs].tag+=tr[rt].tag;
- tr[rt].tag=0;
- }
- }
- void modify(int rt,int l,int r,int x,int y,ll v){
- if(x<=l&&r<=y){
- tr[rt].sum.v0+=v*(s0(r)-s0(l-1));
- tr[rt].sum.v1+=v*(s1(r)-s1(l-1));
- tr[rt].sum.v2+=v*(s2(r)-s2(l-1));
- tr[rt].tag+=v;
- return ;
- }
- int mid=(l+r)>>1;
- pushdown(rt,l,r);
- if(x<=mid)modify(ls,l,mid,x,y,v);
- if(y>mid)modify(rs,mid+1,r,x,y,v);
- update(rt);
- }
- Info query(int rt,int l,int r,int x,int y){
- if(x<=l&&r<=y)return tr[rt].sum;
- int mid=(l+r)>>1;
- pushdown(rt,l,r);
- if(y<=mid)return query(ls,l,mid,x,y);
- if(x>mid)return query(rs,mid+1,r,x,y);
- return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
- }
- inline char GetChar(){
- char gc;
- while(c!='C'&&c!='Q')gc;
- return c;
- }
- int main(){
- freopen("snaker.in","r",stdin);
- freopen("snaker.out","w",stdout);
- int n,m;r(n),r(m);
- --n;
- while(m--){
- char c=GetChar();
- int l,r;r(l),r(r),--r;
- if(c=='C'){
- int x;r(x);
- // for(int i=l;i<=r;++i){
- // a[i]+=x;
- // }
- modify(1,1,n,l,r,x);
- }
- else {
- // ll sum0,sum1,sum2,ans,tot;
- // sum2=sum1=sum0=0;
- // for(int i=l;i<=r;++i){
- // sum2+=(ll)i*i*a[i];
- // sum1+=(ll)i*a[i];
- // sum0+=a[i];
- // }
- Info sum=query(1,1,n,l,r);
- ll ans=-sum.v2+sum.v1*(l+r)-sum.v0*(r+1)*(l-1);
- ll tot=(ll)(r-l+1)*(r-l+2)/2;
- ll g=__gcd(ans,tot);
- ans/=g,tot/=g;
- printf("%lld/%lld\n",ans,tot);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment