BZOJ 2752 [HAOI 2012] 고속도로 선분 수

링크
방법: 선분 수
해석:
이 문 제 는 처음에 뇌 추출 에서 O (n / 2 * (logn) * m) 의 뇌 추출 알고리즘 을 생각해 서 제출 했다.
그런데 그때 저 는 신기 하 게 도 종이 에 O (sqrt (n) / 2 * (logn) * m 라 고 썼 습 니 다.
그 때 는 또 다른 무언 가 를 생각 하 다가 머리 를 쓰 지 않 았 어 요.
규칙 을 찾 아 보 죠.
가중치 를 점 에 맞 추 는 것 도 무방 하 다.
그 다음 에 한 가지 공헌 이 무엇 인지 생각해 보 세 요.
그 왼쪽 에는 몇 개의 점 이 있 고, 오른쪽 에는 몇 개의 점 의 곱셈 이 있다.
이것 은 매우 분명 하 다. 바로 긴 선분 의 좌우 점 을 매 거 하고 있 는 것 이다.
그래서 어떤 점 의 가중치 가 val 이 라 고 가정 합 니 다.
그럼 발 [i] (i - x + 1) (y - i + 1) 맞 죠?
그 다음은 펼 쳐 진다.
펼 쳐 보 니 우 리 는 val [i] 의 구간 과, val [i] * i 의 구간 과, val [i] * i 의 구간 과 만 유지 하면 된다.
지난 두 개의 수학 공식 으로 해결 되 었 다.
코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100100
using namespace std;
typedef long long ll;
ll sumv[N<<2];
ll sumvi[N<<2];
ll sumvii[N<<2];
ll col[N<<2];
ll c[N][4]; 
int n,m;
char s[5];
ll gcd(ll x,ll y)
{
    while(y)
    {
        ll t=y;
        y=x%y;
        x=t;
    }
    return x;
}
void getc()
{
    c[1][0]=c[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=2;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
}
void pushup(int rt)
{
    sumv[rt]=sumv[rt<<1]+sumv[rt<<1|1];
    sumvi[rt]=sumvi[rt<<1]+sumvi[rt<<1|1];
    sumvii[rt]=sumvii[rt<<1]+sumvii[rt<<1|1];
}
void pushdown(int rt,ll l,ll r)
{
    if(col[rt]!=0)
    {
        ll mid=(l+r)>>1;
        ll tmpmid=mid+1;
        sumv[rt<<1]+=(mid-l+1)*col[rt];
        sumv[rt<<1|1]+=(r-tmpmid+1)*col[rt];
        sumvi[rt<<1]+=(((l+mid)*(mid-l+1))/2ll)*col[rt];
        sumvi[rt<<1|1]+=(((tmpmid+r)*(r-tmpmid+1))/2ll)*col[rt];
        sumvii[rt<<1]+=(((mid*(mid+1)*(2*mid+1))/6ll)-((((l-1)*l*(2*l-1))/6ll)))*col[rt];
        sumvii[rt<<1|1]+=(((r*(r+1)*(2*r+1))/6ll)-((((tmpmid-1)*tmpmid*(2*tmpmid-1))/6ll)))*col[rt];
        col[rt<<1]+=col[rt];
        col[rt<<1|1]+=col[rt];
        col[rt]=0;
    }
}
void update(int L,int R,ll d,ll l,ll r,int rt)
{
    if(L<=l&&r<=R)
    {
        sumv[rt]+=d*(r-l+1);
        sumvi[rt]+=d*(r-l+1)*(l+r)/2ll;
        sumvii[rt]+=d*(r*(r+1)*(2*r+1)-(l-1)*(l)*(2*l-1))/6ll;
        col[rt]+=d;
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)update(L,R,d,l,mid,rt<<1);
    if(R>mid)update(L,R,d,mid+1,r,rt<<1|1);
    pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    ll ret=0;
    if(L<=l&&r<=R)
    {
        return sumv[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)ret+=query(L,R,l,mid,rt<<1);
    if(R>mid)ret+=query(L,R,mid+1,r,rt<<1|1);
    pushup(rt);
    return ret;
}
ll queryi(int L,int R,int l,int r,int rt)
{
    ll ret=0;
    if(L<=l&&r<=R)
    {
        return sumvi[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)ret+=queryi(L,R,l,mid,rt<<1);
    if(R>mid)ret+=queryi(L,R,mid+1,r,rt<<1|1);
    pushup(rt);
    return ret;
}
ll queryii(int L,int R,int l,int r,int rt)
{
    ll ret=0;
    if(L<=l&&r<=R)
    {
        return sumvii[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)ret+=queryii(L,R,l,mid,rt<<1);
    if(R>mid)ret+=queryii(L,R,mid+1,r,rt<<1|1);
    pushup(rt);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    getc();
    for(int i=1;i<=m;i++)
    {
        ll x,y;
        ll z;
        scanf("%s",s);
        switch(s[0])
        {
            case 'C':
                scanf("%lld%lld%lld",&x,&y,&z);
                y--;
                update(x,y,z,1,n,1);
                break;
            case 'Q':
                scanf("%lld%lld",&x,&y);
                y--;
                ll ans=(y-x-x*y+1)*query(x,y,1,n,1)+queryi(x,y,1,n,1)*(y+x)-queryii(x,y,1,n,1); 
                ll c_cnt=c[y-x+2][2];
                ll tmpgcd=gcd(ans,c_cnt);
                ans/=tmpgcd;
                c_cnt/=tmpgcd;
                if(c_cnt==1)printf("%lld/1
",ans);
                else printf("%lld/%lld
",ans,c_cnt);
                break;
        }
    } 
}