【Luogu】P2221高速公路（线段树乱搞）

　　题目链接

　　这题……我从一开始就想歪了qwq。

　　为了缅怀逝去的一小时我就把我的30分暴力思路放上来。

　　首先我们观察枚举的区间。假设我们要枚举的范围是1~5之间的四条路，为了方便我们把它们叫做abcd。

　　那么观察我们枚举的区间。

　　a　　ab　　abc　　abcd　　b　　bc　　bcd　　c　　cd　　d

　　观察有一些区间是可以合起来的。

　　然后观察a出现4次，b出现6次，c出现6次，d出现4次。

　　是有一定规律的qwq

　　然后就$\frac{nm}{2}的复杂度搞搞　　就三十分

　　正确思路是，观察一条路选不选上（设这条路左点x）：左区间在(l,x)，右区间在(x+1,r)

　　这些区间会把这条路选上。

　　于是这条路选上的次数就等于(x-l+1)(r-x)s[x]

　　化简得到x*s[x]、s[x]、x^2*s[x]三种可以用线段树维护的东西

　　然后线段树搞

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cstdlib>

#define left (rt<<1)

#define right (rt<<1|1)

#define mid ((l+r)>>1)

#define lson l,mid,left

#define rson mid+1,r,right

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long gcd(long long a,long long b){    return b==?a:gcd(b,a%b);    }

long long sum[];

long long mul[];

long long tree[];

long long sree[];

long long mree[];

long long tag[];

inline void pushup(int rt){

    tree[rt]=tree[left]+tree[right];

    sree[rt]=sree[left]+sree[right];

    mree[rt]=mree[left]+mree[right];

}

void pushdown(int rt,int l,int r){

    if(tag[rt]==)    return;

    tag[left]+=tag[rt];

    tag[right]+=tag[rt];

    tree[left]+=tag[rt]*((r-l+)-((r-l+)>>));

    tree[right]+=tag[rt]*((r-l+)>>);

    sree[left]+=tag[rt]*(sum[mid]-sum[l-]);

    sree[right]+=tag[rt]*(sum[r]-sum[mid]);

    mree[left]+=tag[rt]*(mul[mid]-mul[l-]);

    mree[right]+=tag[rt]*(mul[r]-mul[mid]);

    tag[rt]=;

}

void update(int from,int to,long long num,int l,int r,int rt){

    if(from<=l&&to>=r){

        tag[rt]+=num;

        tree[rt]+=num*(r-l+);

        sree[rt]+=num*(sum[r]-sum[l-]);

        mree[rt]+=num*(mul[r]-mul[l-]);

        return;

    }

    pushdown(rt,l,r);

    if(from<=mid)    update(from,to,num,lson);

    if(to>mid)        update(from,to,num,rson);

    pushup(rt);

}

struct Ans{

    long long x,y,z;

    void clear(){x=y=z=;}

    Ans operator +(const Ans a){

        Ans ans=(Ans){x+a.x,y+a.y,z+a.z};

        return ans;

    }

};

Ans query(int from,int to,int l,int r,int rt){

    if(from<=l&&to>=r)    return(Ans){tree[rt],sree[rt],mree[rt]};

    pushdown(rt,l,r);

    Ans opt; opt.clear();

    if(from<=mid)    opt=query(from,to,lson);

    if(to>mid)        opt=opt+query(from,to,rson);

    return opt;

}

int main(){

    int n=read(),m=read();

    for(int i=;i<=n;++i){

        sum[i]=sum[i-]+i;

        mul[i]=mul[i-]+1LL*i*i;

    }

    for(int i=;i<=m;++i){

        char ch[];

        scanf("%s",ch);int x=read(),y=read();

        if(ch[]=='C'){

            long long z=read();

            update(x,y-,z,,n-,);

        }

        else{

            Ans now=query(x,y-,,n-,);

            long long ans=;

            ans+=now.y*(long long)(x+y-);

            ans+=now.x*(long long)(1LL*y-1LL*x*y);

            ans-=now.z;

            long long len=y-x+;

            long long cnt=len*(len-)/;

            long long gc=gcd(ans,cnt);

            ans/=gc; cnt/=gc;

            printf("%lld/%lld\n",ans,cnt);

        }

    }

    return ;

}

巴特西

【Luogu】P2221高速公路（线段树乱搞）

最新文章

热门文章