P3932 浮游大陆的68号岛
妖精仓库的储物点可以看做在一个数轴上。每一个储物点会有一些东西，同时他们之间存在距离。
每次他们会选出一个小妖精，然后剩下的人找到区间[l,r]储物点的所有东西，清点完毕之后问她，把这个区间内所有储物点的东西运到另外一个仓库的代价是多少？
比如储物点 i 有 x 个东西，要运到储物点 j ，代价为
\[x \times \mathrm{dist}( i , j )\]
dist就是仓库间的距离。当然啦，由于小妖精们不会算很大的数字，因此您的答案需要对19260817取模。
错误日志： 题目取模太毒瘤了（其实是因为-1s）
Solution
线段树可做
每个线段树节点维护区间总大小， 区间左右端点， 把物品搬到左端点 / 右端点的代价 那么合并就很显然了， 把东西先挪到子端点再模拟一下搬过去（跨越区间）即可 关于询问 若是点 \(x\) 在区间外， 分情况讨论在左边和在右边， 搞清楚坐标谁减谁即可 若是点 \(x\) 在区间内， 在 \(x\) 处断开， 就相当于两个上一个情况了第一次用 \(dalao\) 代码风哦
也是第一次见到如此毒瘤的取模题 引用题解的一句话， 把你能想到的所有运算取模Code
#include#include #include #include #include #include #define LL long long#define REP(i, x, y) for(LL i = (x);i <= (y);i++)using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 400019, M = 19260817;LL num, na;LL p[maxn], v[maxn];#define lid (id << 1)#define rid (id << 1) | 1struct seg_tree{ LL l, r; LL p[2];//左右端点位置 LL sum; LL move[2];//移动到左右花费 }tree[maxn << 2];void pushup(LL id){ tree[id].sum = ((tree[lid].sum + tree[rid].sum) % M + M) % M; tree[id].p[0] = tree[lid].p[0]; tree[id].p[1] = tree[rid].p[1]; tree[id].move[0] = ((tree[lid].move[0] + tree[rid].move[0]) % M + M) % M + ((tree[rid].sum * (((tree[rid].p[0] - tree[lid].p[0]) % M + M) % M)) % M + M) % M; tree[id].move[0] = (tree[id].move[0] % M + M) % M; tree[id].move[1] = ((tree[rid].move[1] + tree[lid].move[1]) % M + M) % M + ((tree[lid].sum * (((tree[rid].p[1] - tree[lid].p[1]) % M + M) % M)) % M + M) % M; tree[id].move[1] = (tree[id].move[1] % M + M) % M; }void build(LL id, LL l, LL r){ tree[id].l = l, tree[id].r = r; if(l == r){ tree[id].p[0] = tree[id].p[1] = p[l]; tree[id].sum = v[l]; tree[id].move[0] = tree[id].move[1] = 0; return ; } LL mid = (l + r) >> 1; build(lid, l, mid), build(rid, mid + 1, r); pushup(id); }seg_tree query(LL id, LL l, LL r){ if(tree[id].l == l && tree[id].r == r)return tree[id]; LL mid = (tree[id].l + tree[id].r) >> 1; if(mid < l)return query(rid, l, r); else if(mid >= r)return query(lid, l, r); else{ seg_tree ret, L = query(lid, l, mid), R = query(rid, mid + 1, r); ret.sum = ((L.sum + R.sum) % M + M) % M; ret.p[0] = L.p[0]; ret.p[1] = R.p[1]; ret.move[0] = ((L.move[0] + R.move[0]) % M + M) % M + ((R.sum * (((R.p[0] - L.p[0]) % M + M) % M)) % M + M) % M; ret.move[0] = (ret.move[0] % M + M) % M; ret.move[1] = ((R.move[1] + L.move[1]) % M + M) % M + ((L.sum * (((R.p[1] - L.p[1]) % M + M) % M)) % M + M) % M; ret.move[1] = (ret.move[1] % M + M) % M; return ret; } }void init(){ num = RD(), na = RD(); p[1] = 1; REP(i, 2, num)p[i] = p[i - 1] + RD(); REP(i, 1, num)v[i] = RD() % M; build(1, 1, num); }void solve(){ while(na--){ LL x = RD(), l = RD(), r = RD(); if(x <= l){ seg_tree ans = query(1, l, r); LL output = ans.move[0] + ((ans.sum * (((ans.p[0] - p[x]) % M + M) % M)) % M + M) % M; printf("%lld\n", (output % M + M) % M); } else if(x >= r){ seg_tree ans = query(1, l, r); LL output = ans.move[1] + ((ans.sum * (((p[x] - ans.p[1]) % M + M) % M)) % M + M) % M; printf("%lld\n", (output % M + M) % M); } else{ seg_tree ans = query(1, l, x); LL output = ans.move[1] + ((ans.sum * (((p[x] - ans.p[1]) % M + M) % M)) % M + M) % M; output = (output % M + M) % M; ans = query(1, x, r); output = ((output + ans.move[0]) % M + M) % M + ((ans.sum * (((ans.p[0] - p[x]) % M + M) % M)) % M + M) % M; printf("%lld\n", (output % M + M) % M); } } }int main(){ init(); solve(); return 0; }