【BZOJ2752】[HAOI2012]高速公路

本文主要是介绍【BZOJ2752】[HAOI2012]高速公路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门
题解：
对于l到r中的第i段公路，贡献是
$(i−l+1)∗(r−i)∗v[i]=v[i]∗(r−l∗r)+v[i]∗i∗(l+r−1)−v[i]∗i*i$
线段树随便维护一下就好了

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define gmid int mid=(l+r)>>1
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010;
int n,m;
LL b[N],c[N],w;
inline int in()
{char ch=getchar();int f=1,tmp=0;while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}return tmp*f;
}
char s[10];
struct node
{LL a,b,c,col;
}t[N*4+5];void pushdown(int rt,int l,int r,int mid)
{if(!t[rt].col) return;LL x=t[rt].col;t[rt].col=0;t[L(rt)].col+=x;t[R(rt)].col+=x;t[L(rt)].a+=(mid-l+1)*x;t[R(rt)].a+=(r-mid)*x;t[L(rt)].b+=(b[mid]-b[l-1])*x;t[R(rt)].b+=(b[r]-b[mid])*x;t[L(rt)].c+=(c[mid]-c[l-1])*x;t[R(rt)].c+=(c[r]-c[mid])*x;
}void upd(int rt)
{t[rt].a=t[L(rt)].a+t[R(rt)].a;t[rt].b=t[L(rt)].b+t[R(rt)].b;t[rt].c=t[L(rt)].c+t[R(rt)].c;
}void add(LL val,LL L,LL R,int l,int r,int rt)
{if(L<=l&&R>=r){t[rt].a+=(r-l+1)*val;t[rt].b+=(b[r]-b[l-1])*val;t[rt].c+=(c[r]-c[l-1])*val;t[rt].col+=val;return;}gmid;pushdown(rt,l,r,mid);if(L<=mid) add(val,L,R,lson);if(R>mid)  add(val,L,R,rson);upd(rt);
}LL query(int op,LL L,LL R,int l,int r,int rt)
{if(L<=l&&R>=r){if(op==1) return t[rt].a;if(op==2) return t[rt].b;if(op==3) return t[rt].c;       }gmid;pushdown(rt,l,r,mid);LL ans=0;if(L<=mid) ans+=query(op,L,R,lson);if(R>mid)  ans+=query(op,L,R,rson);return ans;
}LL gcd(LL a,LL b) {return (b)?gcd(b,a%b):a;}
void gi(LL l,LL r)
{LL ans=-1ll*query(3,l,r-1,1,n-1,1)+(r+l-1)*query(2,l,r-1,1,n-1,1)+(r-l*r)*query(1,l,r-1,1,n-1,1);LL k=(r-l+1)*(r-l)/2ll;LL G=gcd(ans,k);printf("%lld/%lld\n",ans/G,k/G);
}int main()
{n=in(),m=in();for(LL i=1;i<=n;i++) b[i]=b[i-1]+i,c[i]=c[i-1]+i*i;LL l,r;for(int i=1;i<=m;i++){scanf("%s",s);l=in(),r=in();if(s[0]=='C'){w=in();add(w,l,r-1,1,n-1,1);}else gi(l,r);}return 0;
}