二次联通门 : BZOJ 4821: [Sdoi2017]相关分析
2017.8.23 Updata
妈妈！！这道题卡我!!!就是不然我过！！！！！
#include <cstdio> #include <iostream> const int BUF = 12312312; char Buf[BUF], *buf = Buf; inline void read (int &now) { bool temp = false; for (now = 0; !isdigit (*buf); ++ buf) if (*buf == '-') temp = true; for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ 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 = 0; Left = Right = NULL; l = _l, r = _r, Mid = l + r >> 1; 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 + 1, rs = R->r - R->l + 1; if (tag) { L->x = ts * ls + _i[L->r] - _i[L->l - 1]; L->y = tt * ls + _i[L->r] - _i[L->l - 1]; L->xy = ts * tt * ls + (_i[L->r] - _i[L->l - 1]) * (ts + tt) + i2[L->r] - i2[L->l - 1]; L->x2 = ts * ts * ls + (_i[L->r] - _i[L->l - 1]) * ts * 2.0 + i2[L->r] - i2[L->l - 1]; R->x = ts * rs + _i[R->r] - _i[R->l - 1]; R->y = tt * rs + _i[R->r] - _i[R->l - 1]; R->xy = ts * tt * rs + (_i[R->r] - _i[R->l - 1]) * (ts + tt) + i2[R->r] - i2[R->l - 1]; R->x2 = ts * ts * rs + (_i[R->r] - _i[R->l - 1]) * ts * 2.0 + i2[R->r] - i2[R->l - 1]; L->ts = R->ts = ts, L->tt = R->tt = tt; L->ss = R->st = L->st = R->ss = 0; tt = ts = 0, 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 = 0; } } }; struct D { double x, y, x2, xy; D () : x (0), y (0), x2 (0), xy (0) {} D (double a, double b, double c, double d) : x (a), y (b), x2 (c), xy (d) {} }; #define DE printf ("%lf %lf %lf %lf ", 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 + 1, 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 + 1); 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 + 1); now->tag = true; now->ss = now->st = 0, now->ts = s, now->tt = t; now->x = L * s + _i[now->r] - _i[now->l - 1]; now->y = L * t + _i[now->r] - _i[now->l - 1]; now->xy = L * s * t + (s + t) * (_i[now->r] - _i[now->l - 1]) + i2[now->r] - i2[now->l - 1]; now->x2 = L * s * s + 2 * s * (_i[now->r] - _i[now->l - 1]) + i2[now->r] - i2[now->l - 1]; 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 + 1; double b = res.xy - s * (res.x / s) * (res.y / s); b /= res.x2 - s * (res.x / s) * (res.x / s); printf ("%.10lf ", b); } }; Segment_Tree Seg; int Main () { fread (buf, 1, BUF, stdin); int N, M; read (N), read (M); register int i; int x; for (i = 1; i <= N; ++ i) read (x), _x[i] = (double) x; for (i = 1; i <= N; ++ i) read (x), _y[i] = (double) x; int type, y, s, t; for (i = 1; i <= N; ++ i) _i[i] = _i[i - 1] + i; for (i = 1; i <= N; ++ i) i2[i] = i2[i - 1] + i * i; Seg.Build (1, N); for (i = 1; i <= M; ++ i) { read (type); if (type == 1) { read (x), read (y); Seg.Query (x, y); } else if (type == 2) { read (x), read (y), read (s), read (t); Seg.Change_1 (x, y, (double) s, (double) t); } else if (type == 3) { read (x), read (y), read (s), read (t); Seg.Change_2 (x, y, (double) s, (double) t); } } return 0; } 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 ", now->x, now->y, now->xy, now->pow_two_x); void read (int &now) { register char word = getchar (); bool temp = false; for (now = 0; word < '0' || word > '9'; word = getchar ()) if (word == '-') temp = true; for (; word >= '0' && word <= '9'; now = now * 10 + word - '0', 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 >> 1; 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 + 1) * S + sum_i[this->r] - sum_i[this->l - 1]; this->y = (this->r - this->l + 1) * T + sum_i[this->r] - sum_i[this->l - 1]; this->xy = (this->r - this->l + 1) * S * T + (S + T) * (sum_i[this->r] - sum_i[this->l - 1]) + sum_i_2[this->r] - sum_i_2[this->l - 1]; this->pow_two_x = (this->r - this->l + 1) * S * S + 2 * S * (sum_i[this->r] - sum_i[this->l - 1]) + sum_i_2[this->r] - sum_i_2[this->l - 1]; 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 + 1) * 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 + 1) * this->Tag_1.S * this->Tag_1.S; this->Left->x += (this->Left->r - this->Left->l + 1) * this->Tag_1.S; this->Left->y += (this->Left->r - this->Left->l + 1) * 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 + 1) * 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 + 1) * this->Tag_1.S * this->Tag_1.S; this->Right->x += (this->Right->r - this->Right->l + 1) * this->Tag_1.S; this->Right->y += (this->Right->r - this->Right->l + 1) * 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 ", 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 + 1, 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 + 1) * S * T; now->pow_two_x += 2 * S * now->x + (now->r - now->l + 1) * S * S; now->x += (now->r - now->l + 1) * S; now->y += (now->r - now->l + 1) * 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 = 0; Answer_xy = Answer_x_2 = 0; __Query_ (Root, l, r); // DE double a = (r - l + 1) * Answer_xy - Answer_x * Answer_y; double b = (r - l + 1) * 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 = 1; i <= N; i ++) { sum_i[i] = sum_i[i - 1] + i; sum_i_2[i] = sum_i_2[i - 1] + 1.0 * i * i; } for (int i = 1; i <= N; i ++) scanf ("%lf", &_x[i]); for (int i = 1; i <= N; i ++) scanf ("%lf", &_y[i]); Seg.Build (1, N); for (int y, z, s, type; M --; ) { read (type); if (type == 1) { read (x); read (y); printf ("%.10lf ", Seg.Query (x, y)); } else if (type == 2) { 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 0; }