首页 > 代码库 > [jzoj5073 GDOI2017第二轮模拟] 影魔
[jzoj5073 GDOI2017第二轮模拟] 影魔
Solution
把所有询问离线
用单调栈分别做两次，求出对于排列数组的单个元素从自己开始到左边和到右边的最远的端点
为了处理贡献对应询问的区间建出一颗线段树
按左端点排序询问，枚举区间内的元素，设当前元素为最大值，那么，从它到区间端点（端点作为最大值）的这个区间的都可以打上p2贡献的标记
设当前元素为次小值，那么，对区间端点打上p1-p2-p2的标记（作为次小有两次重复）
#include <stdio.h>#include <string.h>#include <algorithm>#define _L long long#define _RG register int#define lson s, mid, k << 1#define rson mid + 1, t, k << 1 | 1const int N = 200010;int n, m, p1, p2, a[N], l[N], r[N], steck[N], sec, nex[N], tim;_L tag[N << 2], sum[N << 2], ans[N];struct Q { int l, r, id; }que[N];inline void downt(_RG s, _RG t, _RG k) { sum[k] += tag[k] * (_L)(t - s + 1); if(s ^ t) tag[k << 1] += tag[k], tag[k << 1 | 1] += tag[k]; tag[k] = 0; }void updat(_RG s, _RG t, _RG k, _RG x, _RG y, _RG z) { _RG mid = s + t >> 1; downt(s, t, k); if(s ^ t) downt(s, mid, k << 1), downt(mid + 1, t, k << 1 | 1); if(s == x && t == y) { tag[k] += z; downt(s, t, k); return; } if(y <= mid) updat(lson, x, y, z); else if(x > mid) updat(rson, x, y, z); else updat(lson, x, mid, z), updat(rson, mid + 1, y, z); sum[k] = sum[k << 1] + sum[k << 1 | 1]; }_L query(_RG s, _RG t, _RG k, _RG x, _RG y) { _RG mid = s + t >> 1; downt(s, t, k); if(s ^ t) downt(s, mid, k << 1), downt(mid + 1, t, k << 1 | 1); if(s == x && t == y) return sum[k]; if(y <= mid) return query(lson, x, y); if(x > mid) return query(rson, x, y); return query(lson, x, mid) + query(rson, mid + 1, y); }void solve() { for(_RG i = 1; i <= m; ++i) que[i] = (Q) {l[i], r[i], i}; std::sort(que + 1, que + 1 + m, [](const Q &u, const Q &v) {return u.l > v.l;}); steck[sec = 1] = n + 1; a[n + 1] = 1e9; for(_RG i = n; i; --i) { while(sec && a[steck[sec]] < a[i]) --sec; nex[i] = steck[sec]; steck[++sec] = i; } tim = 1; for(_RG i = n; i; --i) { updat(1, n + 1, 1, i + 1, nex[i], p2); updat(1, n + 1, 1, nex[i], nex[i], p1 - p2 - p2); while(tim <= m && que[tim].l == i) { ans[que[tim].id] += query(1, n + 1, 1, i, que[tim].r); ++tim; } if(tim > m) break; } }int main() { scanf("%d%d%d%d", &n, &m, &p1, &p2); for(_RG i = 1; i <= n; ++i) scanf("%d", a + i); for(_RG i = 1; i <= m; ++i) scanf("%d%d", l + i, r + i); solve(); memset(sum, 0LL, sizeof sum), memset(tag, 0LL, sizeof tag); for(_RG i = 1; i <= n / 2; ++i) std::swap(a[i], a[n - i + 1]); for(_RG i = 1; i <= m; ++i) l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, std::swap(l[i], r[i]); solve(); for(_RG i = 1; i <= m; ++i) printf("%lld\n", ans[i]); return 0; }
枚举当前数为次小值，则可以直接为区间加上贡献，用线段树覆盖，
[jzoj5073 GDOI2017第二轮模拟] 影魔
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。