洛谷P2221 [HAOI2012]高速公路

时间:2022-09-24 19:02:42

线段树

 #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define INF 0x7f7f7f7f
#define MAXN 100005
#define rint register int
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define ft first
#define sc second
#define ll long long
using namespace std;
ll read(){
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct Node{
int L,R;
ll vl,sum;
ll lv,rv;
ll tag;
Node(){
L=R=;
vl=sum=lv=rv=tag=0LL;
}
}st[MAXN<<];
ll cnt[MAXN];
void work(int k,ll v){
int len=st[k].R-st[k].L+;
st[k].vl+=cnt[len]*v;
st[k].sum+=len*v;
st[k].lv+=(+len)*len/*v;
st[k].rv+=(+len)*len/*v;
st[k].tag+=v;
}
Node Merge(Node A,Node B){
if(!A.L&&!A.R)return B;
if(!B.L&&!B.R)return A;
Node r;r.L=A.L,r.R=B.R;
int len1=A.R-A.L+,len2=B.R-B.L+;
r.sum=A.sum+B.sum;
r.vl=A.vl+B.vl+len2*A.rv+len1*B.lv;
r.lv=A.lv+len2*A.sum+B.lv;
r.rv=B.rv+len1*B.sum+A.rv;
return r;
}
void pushdown(int k){
if(st[k].tag){
work(k<<,st[k].tag);
work(k<<|,st[k].tag);
st[k].tag=;
}
}
void build(int k,int L,int R){
st[k].L=L,st[k].R=R;
if(L==R){
st[k].vl=,st[k].sum=;
st[k].lv=,st[k].rv=;
st[k].tag=;
}
else{
int mid=(L+R)>>;
build(k<<,L,mid);
build(k<<|,mid+,R);
st[k]=Merge(st[k<<],st[k<<|]);
}
}
Node query(int k,int a,int b){
int L=st[k].L,R=st[k].R;
if(a<=L&&R<=b){
return st[k];
}
else{
pushdown(k);
Node r;
int mid=(L+R)>>;
if(a<=mid)r=Merge(r,query(k<<,a,b));
if(b>mid)r=Merge(r,query(k<<|,a,b));
return r;
}
}
void add(int k,int a,int b,ll v){
int L=st[k].L,R=st[k].R;
if(a<=L&&R<=b){
work(k,v);
}
else{
pushdown(k);
int mid=(L+R)>>;
if(a<=mid)add(k<<,a,b,v);
if(b>mid)add(k<<|,a,b,v);
st[k]=Merge(st[k<<],st[k<<|]);
}
}
int n,m;
ll s1[MAXN],s2[MAXN];
void init(){
n=read(),m=read();
for(rint i=;i<=n;i++){
s1[i]=s1[i-]+i;
s2[i]=s2[i-]+1LL*i*i;
}
for(rint i=;i<=n;i++){
cnt[i]=(i+)*s1[i]-s2[i];
}
build(,,n);
}
ll gcd(ll a,ll b){return (!b?a:gcd(b,a%b));}
void solve(){
char s[];
int x,y;ll v;
while(m--){
scanf("%s%d%d",s,&x,&y);
y--;
if('C'==s[]){
scanf("%lld",&v);
add(,x,y,v);
}
else{
Node r=query(,x,y);
ll a=1LL*(y-x+)*(y-x+)/;
ll b=r.vl;
ll c=gcd(a,b);
a/=c,b/=c;
printf("%lld/%lld\n",b,a);
}
}
}
int main()
{
// freopen("data.in","r",stdin);
init();
solve();
return ;
}