比赛 |
树形数据结构拔高 |
评测结果 |
AAAAAAAAAA |
题目名称 |
高速公路 |
最终得分 |
100 |
用户昵称 |
李奇文 |
运行时间 |
0.796 s |
代码语言 |
C++ |
内存使用 |
9.03 MiB |
提交时间 |
2025-04-17 21:59:11 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
/*typedef long long ll;
const int Maxn=1e5+5;
struct tree {
ll l,r,tb,lazy;
} f[Maxn*4];
ll n,m;
ll gcd(ll x,ll y){
if(y==0){
return x;
}
return gcd(y,x%y);
}
void pushup(ll p){
f[p].tb=f[p*2].tb+f[p*2+1].tb;
}
void pushdown(ll p){
if(!f[p].lazy){
return;
}else{
ll lp=p*2,rp=p*2+1;
f[lp].lazy+=f[p].lazy;
f[rp].lazy+=f[p].lazy;
ll mid=(f[p].l+f[p].r)>>1;
f[lp].tb+=(mid-f[p].l+1)*f[p].lazy;
f[rp].tb+=(f[p].r-mid)*f[p].lazy;
f[p].lazy=0;
}
return;
}
void build(ll p,ll l,ll r) {
f[p].l=l,f[p].r=r;
if(l==r) {
f[p].tb=0;
return;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
return;
}
ll query(ll p,ll x,ll y){
if(x<=f[p].l&&f[p].r<=y) {
return f[p].tb;
}
pushlazy(p);
ll mid=(f[p].l+f[p].r)/2,sum=0;
if(x<=mid) {
sum+=ptt(p*2,x,y);
}
if(mid<y) {
sum+=ptt(p*2+1,x,y);
}
return sum;
}
void change(ll p,ll l,ll r,ll k){
if(l<=f[p].l&&f[p].r<=r){
f[p].lazy+=k;
f[p].tb+=(f[p].r-f[p].l+1)*k;
return;
}else{
pushlazy(p);
ll mid=(f[p].l+f[p].r)/2;
if(l<=mid) change(p*2,l,r,k);
if(mid<r) change(p*2+1,l,r,k);
f[p].tb=f[p*2].tb+f[p*2+1].tb;
}
return;
}
void solve(int i,int j){
ll fz,fm,ac=j-i;
fm=(ac+1)*ac/2;
printf("%lld/%lld",);
}
int main(){
scanf("%lld%lld",&n,&m);
build(1,1,n-1);
while(m--){
char op;
ll l,r;
scanf("%c%lld%lld",&op,&l,&r);
if(op=='C'){
ll v;
scanf("%d",&v);
change(1,l,r,k);
}else{
solve(l,r);
}
}
return 0;
}*/
typedef long long ll;
const int N=100010;
int n,m;
ll cnt[N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
struct node
{
ll sum,ans,lans,rans;
int tag,len;
}tr[N<<2];
void build(int u,int l,int r)
{
tr[u].len=(r-l+1);
if(l==r) return;
int mid=(l+r)>>1;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
}
inline void add(int u,int v)
{
tr[u].sum+=1ll*tr[u].len*v;
tr[u].tag+=v;
tr[u].lans+=1ll*(tr[u].len+1)*tr[u].len/2*v;
tr[u].rans+=1ll*(tr[u].len+1)*tr[u].len/2*v;
tr[u].ans+=cnt[tr[u].len]*v;
}
inline void pushdown(int u)
{
if(!tr[u].tag) return;
add(u<<1,tr[u].tag); add(u<<1|1,tr[u].tag);
tr[u].tag=0;
}
inline void pushup(node &u,node ls,node rs)
{
u.len=ls.len+rs.len;
u.sum=ls.sum+rs.sum;
u.ans=(ls.ans+rs.ans+ls.rans*rs.len+ls.len*rs.lans);
u.lans=ls.lans+(ls.sum*rs.len+rs.lans);
u.rans=rs.rans+(rs.sum*ls.len+ls.rans);
}
void modify(int u,int l,int r,int ml,int mr,int v)
{
if(ml<=l&&r<=mr) {add(u,v); return;}
pushdown(u);
int mid=(l+r)>>1;
if(ml<=mid) modify(u<<1,l,mid,ml,mr,v);
if(mr>mid) modify(u<<1|1,mid+1,r,ml,mr,v);
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
node query(int u,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return tr[u];
pushdown(u);
int mid=(l+r)>>1;
if(ql<=mid&&qr>mid)
{
node res={0,0,0,0,0,min(r,ql)-max(l,ql)+1};
pushup(res,query(u<<1,l,mid,ql,qr),query(u<<1|1,mid+1,r,ql,qr));
return res;
}
if(ql<=mid) return query(u<<1,l,mid,ql,qr);
else return query(u<<1|1,mid+1,r,ql,qr);
}
int main()
{
freopen("roadxw.in","r",stdin);
freopen("roadxw.out","w",stdout);
scanf("%d%d",&n,&m);
build(1,1,n);
ll now=0;
for(int i=1;i<=n;i++)
{
now+=1ll*i*(i-1);
cnt[i]=(1ll*i*i*(i+1)/2)-now;
}
char ch[5]; int l,r,v;
while(m--)
{
scanf("%s%d%d",ch,&l,&r);
if(ch[0]=='C') scanf("%d",&v),modify(1,1,n,l,r-1,v);
else
{
ll son=query(1,1,n,l,r-1).ans,mom=1ll*(r-l+1)*(r-l)/2;
ll d=gcd(son,mom);
printf("%lld/%lld\n",son/d,mom/d);
}
}
return 0;
}