(WA)BZOJ 4821: [Sdoi2017]相关分析

二次联通门 : BZOJ 4821: [Sdoi2017]相关分析

2017.8.23 Updata

妈妈！！这道题卡我!!!就是不然我过！！！！！

#include <cstdio>

#include <iostream>

const int BUF = ;

char Buf[BUF], *buf = Buf;

inline void read (int &now)

{

    bool temp = false;

    for (now = ; !isdigit (*buf); ++ buf)

        if (*buf == '-')  temp = true;

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

    if (temp) now = -now;

}

#define Max 100050

double _x[Max], _y[Max];

double i2[Max], _i[Max];

struct S_D

{

    S_D *Left, *Right;

    double x, x2, y, xy, ss, st, ts, tt;

    int l, r, Mid;

    bool tag;

    S_D (int _l, int _r)

    {

        x = x2 = ss = st = ts = tt = y = xy = ;

        Left = Right = NULL;

        l = _l, r = _r, Mid = l + r >> ;

        tag = false;

    }

    inline void Up ()

    {

        x = Left->x + Right->x, xy = Left->xy + Right->xy;

        y = Left->y + Right->y;

        x2 = Left->x2 + Right->x2;

    }

    inline void Down ()

    {

        S_D *L = Left, *R = Right;

        double ls = L->r - L->l + , rs = R->r - R->l + ;

        if (tag)

        {

            L->x = ts * ls + _i[L->r] - _i[L->l - ];

               L->y = tt * ls + _i[L->r] - _i[L->l - ];

            L->xy = ts * tt * ls + (_i[L->r] - _i[L->l - ]) * (ts + tt) + i2[L->r] - i2[L->l - ];

            L->x2 = ts * ts * ls + (_i[L->r] - _i[L->l - ]) * ts * 2.0 + i2[L->r] - i2[L->l - ];

            R->x = ts * rs + _i[R->r] - _i[R->l - ];

            R->y = tt * rs + _i[R->r] - _i[R->l - ];

            R->xy = ts * tt * rs + (_i[R->r] - _i[R->l - ]) * (ts + tt) + i2[R->r] - i2[R->l - ];

            R->x2 = ts * ts * rs + (_i[R->r] - _i[R->l - ]) * ts * 2.0 + i2[R->r] - i2[R->l - ];

            L->ts = R->ts = ts, L->tt = R->tt = tt;

            L->ss = R->st = L->st = R->ss = ;

            tt = ts = , tag = false;

            L->tag = R->tag = true;

        }

        if (ss || st)

        {

            L->xy += st * L->x + ss * L->y + ss * st * ls;

            L->x2 += ss * L->x + ss * L->x + ss * ss * ls;

            R->xy += st * R->x + ss * R->y + ss * st * rs;

            R->x2 += ss * R->x + ss * R->x + ss * ss * rs;

            L->x += ss * ls, R->x += ss * rs;

            L->y += st * ls, L->y += st * rs;

            L->ss += ss, R->ss += ss;

            L->st += st, R->st += st;

            ss = st = ;

        }

    }

};

struct D

{

    double x, y, x2, xy;

    D () : x (), y (), x2 (), xy () {}

    D (double a, double b, double c, double d) : x (a), y (b), x2 (c), xy (d) {}

};

#define DE printf ("%lf %lf %lf %lf\n", now->x, now->y, now->x2, now->xy);

class Segment_Tree

{

    private :

        S_D *Root;

        void Build (S_D *&now, int l, int r)

        {

            now = new S_D (l, r);

            if (l == r)

            {

                now->x = (double)_x[l], now->y = (double)_y[r];

                now->x2 = now->x * now->x;

                now->xy = now->x * now->y;

                return ;

            }

            Build (now->Left, l, now->Mid);

            Build (now->Right, now->Mid + , r);

            now->Up ();

        }

        void Change_1 (S_D *&now, int l, int r, double s, double t)

        {

            if (l <= now->l && now->r <= r)

            {

                double L = (now->r - now->l + );

                now->xy += t * now->x + s * now->y + s * t * L;

                now->x2 += s * now->x + s * now->x + s * s * L;

                now->x += s * L, now->y += t * L;

                now->ss += s, now->st += t;

                return ;

            }

            now->Down ();

            if (l <= now->Mid) Change_1 (now->Left, l, r, s, t);

            if (r > now->Mid) Change_1 (now->Right, l, r, s, t);

            now->Up ();

        }

        void Change_2 (S_D *&now, int l, int r, double s, double t)

        {

            if (l <= now->l && now->r <= r)

            {

                double L = (now->r - now->l + );

                now->tag = true;

                now->ss = now->st = , now->ts = s, now->tt = t;

                now->x = L * s + _i[now->r] - _i[now->l - ];

                now->y = L * t + _i[now->r] - _i[now->l - ];

                now->xy = L * s * t + (s + t) * (_i[now->r] - _i[now->l - ]) + i2[now->r] - i2[now->l - ];

                now->x2 = L * s * s +  * s * (_i[now->r] - _i[now->l - ]) + i2[now->r] - i2[now->l - ];

                return ;

            }

            now->Down ();

            if (l <= now->Mid) Change_2 (now->Left, l, r, s, t);

            if (r > now->Mid) Change_2 (now->Right, l, r, s, t);

            now->Up ();

        }

        D Query (S_D *&now, int l, int r)

        {

            if (l <= now->l && now->r <= r)

                return     D (now->x, now->y, now->x2, now->xy);

            now->Down ();

            D A, B;

            if (l <= now->Mid) A = Query (now->Left, l, r);

            if (r > now->Mid) B = Query (now->Right, l, r);

            A.x += B.x, A.y += B.y;

            A.x2 += B.x2, A.xy += B.xy;

            return A;

        }

    public :

        inline void Build (int l, int r) { return Build (Root, l, r); }

        inline void Change_1 (int l, int r, double s, double t)

        {

            return Change_1 (Root, l, r, s, t);

        }

        inline void Change_2 (int l, int r, double s, double t)

        {

            return Change_2 (Root, l, r, s, t);

        }

        inline void Query (int l, int r)

        {

            D res = Query (Root, l, r); double s = r - l + ;

            double b = res.xy - s * (res.x / s) * (res.y / s);

            b /= res.x2 - s * (res.x / s) * (res.x / s);

            printf ("%.10lf\n", b);

        }

};

Segment_Tree Seg;

int Main ()

{

    fread (buf, , BUF, stdin);

    int N, M; read (N), read (M);

    register int i; int x;

    for (i = ; i <= N; ++ i)

        read (x), _x[i] = (double) x;

    for (i = ; i <= N; ++ i)

        read (x), _y[i] = (double) x;

    int type, y, s, t;

    for (i = ; i <= N; ++ i)

        _i[i] = _i[i - ] + i;

    for (i = ; i <= N; ++ i)

        i2[i] = i2[i - ] + i * i;

    Seg.Build (, N);

    for (i = ; i <= M; ++ i)

    {

        read (type);

        if (type == )

        {

            read (x), read (y);

            Seg.Query (x, y);

        }

        else if (type == )

        {

            read (x), read (y), read (s), read (t);

            Seg.Change_1 (x, y, (double) s, (double) t);

        }

        else if (type == )

        {

            read (x), read (y), read (s), read (t);

            Seg.Change_2 (x, y, (double) s, (double) t);

        }

    }

    return ;

}

int ZlycerQan = Main ();

int main (int argc, char *argv[]) {;}

/*

    BZOJ 4821: [Sdoi2017]相关分析

    耗费了整整一下午的时间+晚上的些时间

    实在是调不出来了。。。

*/

#include <cstdio>

#define Max 100090

#define INF 1e9

#define DEBUG printf ("%lf %lf %lf %lf\n", now->x, now->y, now->xy, now->pow_two_x);

void read (int &now)

{

    register char word = getchar ();

    bool temp = false;

    for (now = ; word < '' || word > ''; word = getchar ())

        if (word == '-')

            temp = true;

    for (; word >= '' && word <= ''; now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

int N, M;

double _x[Max], _y[Max];

double sum_i[Max], sum_i_2[Max];

struct Data

{

    double S, T;

};

struct S_D

{

    S_D *Left, *Right;

    int l, r, Mid;

    Data Tag_1, Tag_2;

    double xy;

    double x, y;

    double pow_two_x;

    inline void Up ()

    {

        this->x = this->Left->x + this->Right->x;

        this->y = this->Left->y + this->Right->y;

        this->xy = this->Left->xy + this->Right->xy;

        this->pow_two_x = this->Left->pow_two_x + this->Right->pow_two_x;

    }

    S_D (int __l, int __r) : l (__l), r (__r)

    {

        Left = Right = NULL;

        Mid = __l + __r >> ;

        x = y = 0.0;

        pow_two_x = xy = 0.0;

        Tag_1.S = Tag_1.T = 0.0;

        Tag_2.S = Tag_2.T = INF;

    }

    inline void Push_Down_2 (double S, double T)

    {

        this->x = (this->r - this->l + ) * S + sum_i[this->r] - sum_i[this->l - ];

        this->y = (this->r - this->l + ) * T + sum_i[this->r] - sum_i[this->l - ];

        this->xy = (this->r - this->l + ) * S * T + (S + T) * (sum_i[this->r] - sum_i[this->l - ]) + sum_i_2[this->r] - sum_i_2[this->l - ];

        this->pow_two_x = (this->r - this->l + ) * S * S +  * S * (sum_i[this->r] - sum_i[this->l - ]) + sum_i_2[this->r] - sum_i_2[this->l - ];

        this->Tag_1.S = this->Tag_1.T = 0.0;

        this->Tag_2.S = S;

        this->Tag_2.T = T;

    }

    inline void Down ()

    {

        if (this->Tag_1.S || this->Tag_1.T)

        {

            bool temp = false;

            if (this->Left->Tag_2.S != INF || this->Left->Tag_2.T != INF)

            {

                temp = true;

                this->Left->Push_Down_2 (this->Tag_1.S + this->Left->Tag_2.S, this->Tag_1.T + this->Left->Tag_2.T);

            }

            if (temp == false)

            {

                this->Left->xy += this->Tag_1.T * this->Left->x + this->Tag_1.S * this->Left->y + (this->Left->r - this->Left->l + ) * this->Tag_1.S * this->Tag_1.T;

                this->Left->pow_two_x += 2.0 * this->Tag_1.S * this->Left->x + (this->Left->r - this->l + ) * this->Tag_1.S * this->Tag_1.S;

                this->Left->x += (this->Left->r - this->Left->l + ) * this->Tag_1.S;

                this->Left->y += (this->Left->r - this->Left->l + ) * this->Tag_1.T;

                this->Left->Tag_1.S += this->Tag_1.S;

                this->Left->Tag_1.T += this->Tag_1.T;

            }

            temp = false;

            if (this->Right->Tag_2.S != INF || this->Right->Tag_2.T != INF)

            {

                temp = true;

                this->Right->Push_Down_2 (this->Tag_1.S + this->Right->Tag_2.S, this->Tag_1.T + this->Right->Tag_2.T);

            }

            if (temp == false)

            {

                this->Right->xy += this->Tag_1.T * this->Right->x + this->Tag_1.S * this->Right->y + (this->Right->r - this->Right->l + ) * this->Tag_1.S * this->Tag_1.T;

                this->Right->pow_two_x += 2.0 * this->Tag_1.S * this->Right->x + (this->Right->r - this->l + ) * this->Tag_1.S * this->Tag_1.S;

                this->Right->x += (this->Right->r - this->Right->l + ) * this->Tag_1.S;

                this->Right->y += (this->Right->r - this->Right->l + ) * this->Tag_1.T;

                this->Right->Tag_1.S += this->Tag_1.S;

                this->Right->Tag_1.T += this->Tag_1.T;

            }

            this->Tag_1.S = this->Tag_1.T = 0.0;

        }

        if (this->Tag_2.S != INF || this->Tag_2.T != INF)

        {

            this->Left->Push_Down_2 (this->Tag_2.S, this->Tag_2.T);

            this->Right->Push_Down_2 (this->Tag_2.S, this->Tag_2.T);

            this->Tag_2.S = this->Tag_2.T = INF;

        }

    }

};

#define DE printf ("%lf %lf %lf %lf\n", Answer_x, Answer_y, Answer_xy, Answer_x_2);

double Answer_x, Answer_y;

double Answer_xy, Answer_x_2;

class Segment_Tree_Type

{

    private :

        S_D *Root;

        void __Build_ (S_D *&now, int l, int r)

        {

            now = new S_D (l, r);

            if (l == r)

            {

                now->x = _x[l];

                now->y = _y[r];

                now->xy = now->x * now->y;

                now->pow_two_x = now->x * now->x;

                return ;

            }

            __Build_ (now->Left, l, now->Mid);

            __Build_ (now->Right, now->Mid + , r);

            now->Up ();

        }

        void __Change_1_ (S_D *&now, int l, int r, double S, double T)

        {

            if (l <= now->l && now->r <= r)

            {

                bool temp = false;

                if (now->Tag_2.S != INF || now->Tag_2.T != INF)

                {

                    temp = true;

                    now->Push_Down_2 (now->Tag_2.S + S, now->Tag_2.T + T);

                }

                if (temp == false)

                {

                    now->xy += T * now->x + S * now->y + (now->r - now->l + ) * S * T;

                    now->pow_two_x +=  * S * now->x + (now->r - now->l + ) * S * S;

                    now->x += (now->r - now->l + ) * S;

                    now->y += (now->r - now->l + ) * T;

                    now->Tag_1.S += S;

                    now->Tag_1.T += T;

                }

//                DEBUG

                return ;

            }

            now->Down ();

            if (l <= now->Mid)

                __Change_1_ (now->Left, l, r, S, T);

            if (r > now->Mid)

                __Change_1_ (now->Right, l, r, S, T);

            now->Up ();

        }

        void __Change_2_ (S_D *&now, int l, int r, double S, double T)

        {

            if (l <= now->l && now->r <= r)

            {

                now->Push_Down_2 (S, T);

//                DEBUG

                return ;

            }

            now->Down ();

            if (l <= now->Mid)

                __Change_2_ (now->Left, l, r, S, T);

            if (r > now->Mid)

                __Change_2_ (now->Right, l, r, S, T);

            now->Up ();

        }

        void __Query_ (S_D *&now, int l, int r)

        {

            if (l <= now->l && now->r <= r)

            {

                Answer_x += now->x;

                Answer_y += now->y;

                Answer_xy += now->xy;

                Answer_x_2 += now->pow_two_x;

//                DEBUG

                return ;

            }

            now->Down ();

            if (l <= now->Mid)

                __Query_ (now->Left, l, r);

            if (r > now->Mid)

                __Query_ (now->Right, l, r);

            now->Up ();

        }

    public :

        inline void Build (int l, int r)

        {

            return __Build_ (Root, l, r);

        }

        inline void Change_First (int l, int r, double S, double T)

        {

            return __Change_1_ (Root, l, r, S, T);

        }

        inline void Change_Second (int l, int r, double S, double T)

        {

            return __Change_2_ (Root, l, r, S, T);

        }

        inline double Query (int l, int r)

        {

            Answer_x = Answer_y = ;

            Answer_xy = Answer_x_2 = ;

            __Query_ (Root, l, r);

//            DE

            double a = (r - l + ) * Answer_xy - Answer_x * Answer_y;

            double b = (r - l + ) * Answer_x_2 - Answer_x * Answer_x;

            return a / b;

        }

};

Segment_Tree_Type Seg;

#define Local

int main (int argc, char *argv[])

{

#ifdef Local

    freopen ("relative.in", "r", stdin);

    freopen ("relative.out", "w", stdout);

#endif

    read (N);

    read (M);

    int x;

    for (int i = ; i <= N; i ++)

    {

        sum_i[i] = sum_i[i - ] + i;

        sum_i_2[i] = sum_i_2[i - ] + 1.0 * i * i;

    }

    for (int i = ; i <= N; i ++)

        scanf ("%lf", &_x[i]);

    for (int i = ; i <= N; i ++)

        scanf ("%lf", &_y[i]);

    Seg.Build (, N);

    for (int y, z, s, type; M --; )

    {

        read (type);

        if (type == )

        {

            read (x);

            read (y);

            printf ("%.10lf\n", Seg.Query (x, y));

        }

        else if (type == )

        {

            read (x);

            read (y);

            read (z);

            read (s);

            Seg.Change_First (x, y, z, s);

        }

        else

        {

            read (x);

            read (y);

            read (z);

            read (s);

            Seg.Change_Second (x, y, z, s);

        }

    }

    return ;

}