BZOJ2752: [HAOI2012]高速公路(road)【线段树】

dzy posted @ 2013年6月09日 10:21 in BZOJ with tags BZOJ 线段树 期望 , 1793 阅读

题意:修改区间内的数、询问区间内任意子段和的期望值。

然后我们尝试把每次的答案求出来。然后对这个式子乱搞。发现对于每个数a[i],维护a[i],i*a[i],i*i*a[i]就好了、

那么线段树维护就行了。好了没了。(其实是我懒得写题解了、、、

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,1
typedef long long ll;
const int maxn=500005;
ll a[maxn]={0},b[maxn]={0},c[maxn]={0},add[maxn]={0};
char buf[5000000],*pt=buf,buf2[5000000],*o=buf2;
inline ll getint(){
    ll r=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++; if(*pt=='-')f=-1, pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;   return r*f;
}inline char getop(){
    while(*pt!='C'&&*pt!='Q')pt++;  return *pt;
}inline void print(ll x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void pushup(ll rt){
    a[rt]=a[ls]+a[rs], b[rt]=b[ls]+b[rs], c[rt]=c[ls]+c[rs];
}inline void pushdown(ll l,ll r,ll rt){
    ll lc=mid-l+1, rc=r-mid, rr=mid, ll=mid+1;  
    if(add[rt]){
        add[ls]+=add[rt];
        a[ls]+=lc*add[rt];
        b[ls]+=(l+rr)*lc*add[rt]>>1;
        c[ls]+=(rr*(rr+1)*(rr<<1|1)-(l-1)*l*(l-1<<1|1))/6*add[rt];
        add[rs]+=add[rt];
        a[rs]+=rc*add[rt];
        b[rs]+=(ll+r)*rc*add[rt]>>1;
        c[rs]+=(r*(r+1)*(r<<1|1)-(ll-1)*ll*(ll-1<<1|1))/6*add[rt];
        add[rt]=0;
    }
}void update(ll L,ll R,ll d,ll l,ll r,ll rt){
    if(L<=l&&r<=R){
        add[rt]+=d;
        a[rt]+=(r-l+1)*d;
        b[rt]+=(l+r)*(r-l+1)*d>>1;
        c[rt]+=(r*(r+1)*(r<<1|1)-(l-1)*l*(l-1<<1|1))/6*d;
        return;
    }pushdown(l,r,rt);
    if(L<=mid)  update(L,R,d,lson);
    if(mid<R)   update(L,R,d,rson);
    pushup(rt);
}void query(ll L,ll R,ll&A,ll&B,ll&C,ll l,ll r,ll rt){
    if(L<=l && r<=R){
        A=a[rt],B=b[rt],C=c[rt]; return;
    }pushdown(l,r,rt);
    ll SA=0,SB=0,SC=0,TA,TB,TC;
    if(L<=mid)  query(L,R,TA,TB,TC,lson), SA+=TA, SB+=TB, SC+=TC;
    if(mid<R)   query(L,R,TA,TB,TC,rson), SA+=TA, SB+=TB, SC+=TC;
    A=SA,B=SB,C=SC;
}inline ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}int main(){ 
    fread(pt,1,5000000,stdin);  ll n,q,u,v,w,TA,TB,TC,A,B,C;
    for(n=getint(),q=getint();q;q--){
        if(getop()=='C'){
            u=getint(),v=getint(),w=getint();
            update(u,v-1,w,root);
        }else{
            u=getint(),v=getint();
            query(u,v-1,TA,TB,TC,root);
            A=(u+v-1)*TB+TA*(v-v*u)-TC;
            B=(v-u+1)*(v-u)>>1;
            C=gcd(A,B);
            print(A/C);*o++='/';print(B/C);*o++='\n';
        }
    }fwrite(buf2,1,o-buf2,stdout);return 0;
}
Avatar_small
Emma 说:
2023年1月31日 21:32

Expressway (road) [line segment tree] is a great example of using line segment tree to solve a problem. It can be used to solve problems related to roads and foods to avoid with gout expressways, such as finding the optimal route between two points. This solution is both efficient and effective, making it an ideal choice for those looking to reduce their travel time. Additionally, its implementation is straightforward, making it a great choice for those just getting started with line segment tree algorithms. With its help, you can find the best path to take in no time!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter