首页 > 代码库 > bzoj 2752
bzoj 2752
传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=2752
这道题其实想到线段树并不难,而且如果正确的推出了公式写起来也就是有点恶心而已= =实现不太容易出错。但是公式推起来确实比较的酸爽,加上我的公式又比较的迷,然后跑的飞慢= =
这道题对于一个区间的期望,是整个区间的路径和除上区间的路径数目。数目可以O(1), 然后就在线段树中维护这个路径和。考虑区间合并(线段树都是这样= =),那么对于两个区间l, r, 那么路径和首先等于l的路径和加上r路径和,然后对于l中的一段路径,那么它的更新就是这条路径左边点的个数(包括左端点)* r中点的个数 * v,而出了r中的点的个数以外,其余部分作为一个元素up进行维护。 同样右边同理一个down 维护。 同时在更新这两个值的时候还需要维护一个区间和sum= =
然后lazy 标记的下放:sum 直接搞,然后up 和down 都是 * len[区间长度]* (len - 1) * v;
ans += lazy * (1 * len * + 2 * (len - 1) + 3 * (len - 3) ... + (len - 1) * 2 + len * 1) = len * (len + 1) * (len + 2) / 6 * lazy
然后就搞搞= =
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long qword;const qword maxn = 101000;struct node { qword up, down, ans, lazy, sum; node *l, *r;}e[maxn * 3]; qword ne = 0;node* root;node* build(qword l, qword r) { node* now = e + ne ++; if(l ^ r) { qword mid = (l + r) >> 1; now-> l = build(l, mid); now-> r = build(mid + 1, r); } return now;}void update(node* x, qword l, qword r, qword mid) { if(l ^ r) { x-> ans = x-> l-> ans + x-> r-> ans + x-> l-> up * (r - mid) + x-> r-> down * (mid - l + 1); x-> sum = x-> l-> sum + x-> r-> sum; x-> up = x-> l-> up + x-> r-> up + x-> r-> sum * (mid - l + 1); x-> down = x-> l-> down + x-> r-> down + x-> l-> sum * (r - mid); }}void pushdown(node* x, qword l, qword r) { if(x-> l) { qword mid = (l + r) >> 1, v = x-> lazy, ln = mid - l + 1, rn = r - mid; x-> l-> ans += ln * (ln + 1) / 2 * (ln + 2) / 3 * v; x-> r-> ans += rn * (rn + 1) / 2 * (rn + 2) / 3 * v; x-> l-> sum += ln * v; x-> r-> sum += rn * v; x-> l-> up += ln * (ln + 1) / 2 * v; x-> r-> up += rn * (rn + 1) / 2 * v; x-> l-> down += ln * (ln + 1) / 2 * v; x-> r-> down += rn * (rn + 1) / 2 * v; x-> l-> lazy += v, x-> r-> lazy += v; x-> lazy = 0; }}void addlazy(node* now, qword l, qword r, qword ls, qword rs, qword v) { if(now-> lazy != 0) pushdown(now, l, r); if(l == ls && r == rs) { qword nn = rs - ls + 1; now-> ans += nn * (nn + 1) / 2 * (nn + 2) / 3 * v; now-> sum += nn * v; now-> up += nn * (nn + 1) / 2 * v; now-> down += nn * (nn + 1) / 2 * v; now-> lazy += v; } else { qword mid = (l + r) >> 1; if(rs <= mid) addlazy(now-> l, l, mid, ls, rs, v); else if(ls > mid) addlazy(now-> r, mid + 1, r, ls, rs, v); else addlazy(now-> l, l, mid, ls, mid, v), addlazy(now-> r, mid + 1, r, mid + 1, rs, v); update(now, l, r, mid); }}node ask(node* now, qword l, qword r, qword ls, qword rs) { if(now-> lazy != 0) pushdown(now, l, r); node ret; if(l == ls && r == rs) ret = *now; else { qword mid = (l + r) >> 1; if(rs <= mid) ret = ask(now-> l, l, mid, ls, rs); else if(ls > mid) ret = ask(now-> r, mid + 1, r, ls, rs); else { node lr = ask(now-> l, l, mid, ls, mid); node rr = ask(now-> r, mid + 1, r, mid + 1, rs); ret.l = &lr, ret.r = &rr; update(&ret, ls, rs, mid); } } return ret;}qword qword_get() { qword x = 0; char c = (char)getchar(); qword f = 0; while(!isdigit(c) && c != ‘-‘) c = (char)getchar(); if(c == ‘-‘) c =(char)getchar(), f = 1; while(isdigit(c)) { x = x * 10 + (qword)(c - ‘0‘); c = (char)getchar(); } if(f) x = -x; return x;}qword n, m;qword gcd(qword a, qword b) { return a % b == 0 ? b : gcd(b, a % b);}void test(node* now, qword l, qword r) { cout << l <<" "<< r <<" "<< now-> ans <<" "<< now-> sum <<" " << now-> up <<" "<< now-> down <<" "<< now-> lazy << endl; if(l ^ r) { qword mid = (l + r) >> 1; test(now-> l, l, mid), test(now-> r, mid + 1, r); }}void sov() { n = qword_get(), m = qword_get(); root = build(1, n - 1); char s[10]; while(m --) { scanf("%s", s + 1); if(s[1] ==‘C‘) { qword ls, rs, v; ls = qword_get(); rs = qword_get(); v = qword_get(); rs --; addlazy(root, 1, n - 1, ls, rs, v); } if(s[1] == ‘Q‘) { qword ls, rs; ls = qword_get(), rs = qword_get(); rs --; node ret = ask(root, 1, n - 1, ls, rs); qword a = ret.ans; qword b = (rs - ls + 1) * (rs - ls + 2) / 2; qword g = gcd(a, b); printf("%lld/%lld\n", a / g, b / g); } }}int main() { //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); sov(); return 0;}
bzoj 2752
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。