【题解】 [JOISC2020] 星座 3
程序员文章站
2024-03-19 08:46:58
...
solution:
考虑怎样的一对星星会形成星座。
记 l [ i ] l[i] l[i] 和 r [ i ] r[i] r[i] 分别表示从第 i i i 个星星出发,能扩展到的最左和最右节点。
考虑反悔贪心,尽量使得答案更大。换句话说,当前点覆盖的区间一定比之前 [ l [ i ] , r [ i ] ] [l[i],r[i]] [l[i],r[i]] 内所有点管辖的区间的并集还大,所以如果 w ≥ c w\geq c w≥c 那么答案直接加上 c c c ;否则强行选择当前星星,自然而然地对 [ l [ i ] , r [ i ] ] [l[i],r[i]] [l[i],r[i]] 加上 C − W C-W C−W 的价值表示翻转的代价。(定义反转操作为弃掉 s 而把选择 s 所弃掉的全部选回来)。
然后并查集细节比较多,但是 高度有单调性,应该是在 a [ i ] a[i] a[i] 处取出来,合并前把 y y y 处星星取出来,然后单点查询 + 区间修改。(因为这里有传递性,所以选这个星星就只有不选它和将 [ l [ i ] , r [ i ] ] [l[i],r[i]] [l[i],r[i]] 全部弃掉两种情况)。
不知道理解得对不对 qwq …
#include<bits/stdc++.h>
#define PII pair<int,int>
#define ll long long
using namespace std;
const int mx=2e5+5;
int n,m,a[mx],l[mx],r[mx];
ll res,bit[mx];
vector<PII> s[mx];
vector<int> h[mx];
void upd(int x,ll k) {
for(int i=x;i<=n;i+=i&-i) bit[i]+=k;
}
ll qry(int x) {
ll tot(0);
for(int i=x;i;i-=i&-i) tot+=bit[i];
return tot;
}
int find(int x,int *fa) {
return fa[x]==x?x:fa[x]=find(fa[x],fa);
}
int main() {
// freopen("data.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),h[a[i]].push_back(i);
for(int i=0;i<=n+1;i++) l[i]=i,r[i]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++) {
int x,y,c; scanf("%d%d%d",&x,&y,&c);
s[y].push_back(make_pair(x,c));
}
for(int i=1;i<=n;i++) {
for(auto x:s[i]) {
ll w=qry(x.first),c=x.second;
if(w>=c) res+=c;
else res+=w,upd(find(x.first,l)+1,c-w),upd(find(x.first,r),w-c);
}
for(auto x:h[i]) {
l[x]=x-1,r[x]=x+1;
}
}
printf("%lld",res);
}
推荐阅读
-
python3 在macOS 中使用pyenv安装遇到的问题解决
-
【题解】[JOISC2020] 扫除
-
【题解】 [JOISC2020] 星座 3
-
3月24日 模拟赛题解
-
YOLOv3 使用COCO数据集 Model accepts 80 classes labeled from 0 - 79, however you labeled a class**问题解决
-
空格和换行符造成3像素距离问题解决
-
LeetCode[字符串] - #3 Longest Substring Without Repeating Characters 博客分类: LeetCode LeetCodeJavaAlgorithm题解String
-
dev/sda3 磁盘占满问题解决
-
详解Spring MVC3返回JSON数据中文乱码问题解决
-
详解Spring MVC3返回JSON数据中文乱码问题解决