[AHOI/HNOI2017]影魔 题解
2022/2/5 6:15:16
本文主要是介绍[AHOI/HNOI2017]影魔 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门QAQ
思路
首先有一个套路(我自己总结的,错了别骂窝 qwq):
统计满足类似 \(i \lt j \lt k\) 且 \(a_i \lt a_j \lt a_k\) 的关系的 \((i,j,k)\) 数量的这类题一般来说突破点都是中间的 \(j\),并且一般会采用单调栈处理。
这道题的预处理就是这个套路:
首先对于每个 \(i\),求出左边离 \(i\) 最近的满足 \(a_{L_i} \gt a_i\) 的 \(L_i\) 和右边离 \(i\) 最近的满足 \(a_{R_i}\gt a_i\) 的 \(R_i\),这个过程可以用单调栈 \(O(N)\) 实现。
然后分别考虑两种贡献:
-
对于每组 \((L_i,R_i)\),它们会产生 \(p_1\) 的贡献。
-
-
\(\forall k \in (i,R_i)\),每组 \((L_i,k)\) 会产生 \(p_2\) 的贡献。
-
\(\forall k \in (L_i,i)\),每组 \((k,R_i)\) 会产生 \(p_2\) 的贡献。
-
题目中并没有要求在线,所以我们可以离线处理。
首先将询问 \((l,r)\) 按照前缀和拆分成 \(l-1\) 和 \(r\) 两部分,这样前后前缀和相减就是 \([l,r]\) 中的贡献。
考虑每种情况的贡献如何处理:
-
遇到 \(R_i\) 时,对 \(L_i\) 产生 \(p_1\) 的贡献。
-
遇到 \(L_i\) 时,对 \((i,R_i)\) 产生 \(p_2\) 的贡献。遇到 \(R_i\) 时,对 \((L_i,i)\) 产生 \(p_2\) 的贡献。
将贡献也存入数组中,让贡献和询问分别按位置升序排序。
最后用类似 HH的项链 的方式一边遍历询问一边更进贡献,用一个树状数组实现区间修改即可。时间复杂度 \(O(N\log N)\)
CODE
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 200005; typedef long long ll; int n,m,a[maxn]; struct query { int l,r,x,v,id; query() { l = r = x = v = id = 0; } query(int l,int r,int x,int v,int id):l(l),r(r),x(x),v(v),id(id){} bool operator < (const query& p)const { return x < p.x; } }Q[maxn << 2],s[maxn << 2]; int cnt,tot; int stk[maxn],top = 0,L[maxn],R[maxn]; ll ans[maxn],p1,p2; ll sum1[maxn],sum2[maxn]; int lowbit(int x) { return x & -x; } void add(int x,int y) { for(int i = x;i <= n;i += lowbit(i)) { sum1[i] += y; sum2[i] += (x - 1) * y; } return ; } ll Query(int x) { ll Ans = 0; for(int i = x;i;i -= lowbit(i)) { Ans += 1ll * x * sum1[i] - sum2[i]; } return Ans; } int main() { scanf("%d%d%lld%lld",&n,&m,&p1,&p2); for(int i = 1;i <= n;++ i) { scanf("%d",&a[i]); } stk[top = 0] = n + 1; for(int i = n;i;-- i) { for(;top&&a[stk[top]] < a[i];-- top)L[stk[top]] = i; R[i] = stk[top]; stk[++ top] = i; } for(int i = 1;i <= m;++ i) { int l,r; scanf("%d%d",&l,&r); ans[i] = 1ll * (r - l) * p1; Q[++ cnt] = query(l , r , l - 1 , -1 , i); Q[++ cnt] = query(l , r , r , 1 , i); } sort(Q + 1 , Q + 1 + cnt); for(int i = 1;i <= n;++ i) { if(L[i] >= 1&&R[i] <= n)s[++ tot] = query(L[i] , L[i] , R[i] , p1 , i); if(L[i] >= 1&&R[i] > i + 1)s[++ tot] = query(i + 1 , R[i] - 1 , L[i] , p2 , i); if(L[i] < i - 1&&R[i] <= n)s[++ tot] = query(L[i] + 1 , i - 1 , R[i] , p2 , i); } sort(s + 1 , s + 1 + tot); for(int i = 1,j = 1;i <= cnt;++ i) { for(;j <= tot&&s[j].x <= Q[i].x;++ j) { add(s[j].l , s[j].v); add(s[j].r + 1 , -s[j].v); } ans[Q[i].id] += 1ll * Q[i].v * (Query(Q[i].r) - Query(Q[i].l - 1)); } for(int i = 1;i <= m;++ i)printf("%lld\n",ans[i]); return 0; }
完结撒花✿✿ヽ(°▽°)ノ✿
这篇关于[AHOI/HNOI2017]影魔 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南