[luoguP2221] [HAOI2012]高速公路（线段树）

传送门

考虑每一段对答案的贡献

用每一段的左端点来表示当前这一段，那么区间就变成了[1,n1]

如果询问区间[l,r]，其中一个点的位置为x，则它对答案的贡献为(xl)*(rx)*s[x]（s[x]为这一段的权值）

化简后得x*s[x]*(l+r1)s[x]*(l*rr)x*x*s[x]

那么我们就需要维护x*s[x]，s[x]，x*x*s[x]

其中还需要预处理出来x和x*x

然后就ok了

#include <cstdio>#include <cstring>#include <iostream>#define N 500001#define LL long long#define root 1, 1, n  1#define ls now << 1, l, mid#define rs now << 1 | 1, mid + 1, rusing namespace std;int n, m;LL s, xs, xxs, ans1, ans2;LL x1[N], x2[N], sum1[N], sum2[N], sum3[N], add[N];//x1表示 x//x2表示 x^2 //sum1表示 s[x]//sum2表示 x * s[x]//sum3表示 x^2 * s[x]inline int read()inline void push_down(int now, int l, int r)}inline void push_up(int now)inline void update(int now, int l, int r, int x, int y, LL z)push_down(now, l, r);int mid = (l + r) >> 1;if(x <= mid) update(ls, x, y, z);if(mid < y) update(rs, x, y, z);push_up(now);}inline void build(int now, int l, int r)int mid = (l + r) >> 1;build(ls);build(rs);x1[now] = x1[now << 1] + x1[now << 1 | 1];x2[now] = x2[now << 1] + x2[now << 1 | 1];}inline void query(int now, int l, int r, int x, int y)push_down(now, l, r);int mid = (l + r) >> 1;if(x <= mid) query(ls, x, y);if(mid < y) query(rs, x, y);}inline LL gcd(LL x, LL y)int main()else}return 0;}

一个longlong调了我45min，WNM

上一篇：[luoguP2219] [HAOI2007]修筑绿化带（单调队列）

下一篇：[luoguP2325] [SCOI2005]王室联邦（树分块乱搞）