CF1208D

系统管理员 2024-04-20 10:24 130阅读 0赞

##  ##

CF1208D

### 题意； ###

> 给你一个数组，要求支持单点修改和单点查询

### 解法： ###

> 直接线段树搞一搞就没了。

### CODE： ###

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define lson x << 1 #define rson x << 1 | 1 #define mid (l + r)/2 #define LL long long using namespace std; const int N = 200010; struct Tree { LL minv; LL sum; }tree[N * 4]; int n, m, p[N]; LL s[N]; void pushup(int x) { tree[x].minv = min(tree[lson].minv, tree[rson].minv); } void pushdown(int x) { if (tree[x].sum) { tree[lson].sum += tree[x].sum; tree[rson].sum += tree[x].sum; tree[lson].minv += tree[x].sum; tree[rson].minv += tree[x].sum; tree[x].sum = 0; } } void build(int x, int l, int r) { if (l == r) { tree[x].minv = s[l]; return; } build(lson, l, mid); build(rson, mid + 1, r); pushup(x); } void update(int x, int l, int r, int ll, int rr, int v) { if (ll > rr)return; if (l >= ll && r <= rr) { tree[x].sum += v; tree[x].minv += v; return; } pushdown(x); if (ll <= mid) update(lson, l, mid, ll, rr, v); if (rr > mid) update(rson, mid + 1, r, ll, rr, v); pushup(x); } int query(int x, int l, int r) { if (l == r) { tree[x].minv = 1e18; return l; } pushdown(x); int ans = 0; if (tree[rson].minv == 0) ans = query(rson, mid + 1, r); else ans = query(lson, l, mid); pushup(x); return ans; } int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%lld",&s[i]); build(1, 1, n); for(int i = 1; i <= n; i++) { int x = query(1, 1, n); p[x] = i; update(1,1,n,x + 1,n,-i); } for(int i = 1; i <= n; i++) printf("%d ",p[i]); printf("\n"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11415139.html

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 133 阅读

相关 CF1208C

CF1208C > 这场杜老师大战tourist的比赛怎么这么多人类智慧题。。。题意： > 构造一个 $ n \\times n $ 的矩阵，使得该矩阵...

迈不过友情╰/ 2024年04月20日 10:31/ 0 赞/ 145 阅读

相关 CF1208A

CF1208A 题意： > 就是把斐波那契数列的+改成异或，求第n项的值。解法： > 又是一个人类智慧题，打表找规律。 > 可以发现答案在 $...

雨点打透心脏的1/2处/ 2024年04月20日 10:30/ 0 赞/ 128 阅读

相关 CF1208B

CF1208B 题意： > 给出n个数字，找出最小的一端连续区间进行删除操作，使其剩余元素不含重复元素，求要删除的最小区间长度解法： > 删除子段...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:28/ 0 赞/ 126 阅读

相关 CF981D

CF981D 题意： > 给你n个数，要求你分成k堆。每堆的内部加和，每堆之间是相与。问最大的值。解法： > 二进制下最大的数的所有位一定是1，所...

缺乏、安全感/ 2024年04月20日 10:26/ 0 赞/ 126 阅读

相关 CF427D

CF427D > SA的奇技淫巧，其实就是板子。题意： > 给定两个字符串，求最短的满足各只出现一次的连续公共字串解析： > 一般情况下，SA...

素颜马尾好姑娘i/ 2024年04月20日 10:25/ 0 赞/ 128 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 131 阅读

相关 cf1208B B. Uniqueness（1500）

题要逆向思维，不看删除的，要看保留的。 [讲解][Link 1] include<bits/stdc++.h> using namespace ...

傷城~/ 2024年04月18日 14:23/ 0 赞/ 133 阅读

相关线段树双tag+差分数组——cf1208E

写了一上午 / 对于每个数组a[],先排序然后从大到小把a[i]放进线段树更新设a[i]的位置是pos,那么其可更新的区间是[pos,w-(li-p

超、凢脫俗/ 2023年10月11日 09:04/ 0 赞/ 13 阅读

相关 CodeForces1208D

CodeForces1208D 也是挺吓人的一道题,我一开始以为给的是每个数字前比它小的数字有几个,然后我就苦苦看不懂样例... 然后我冷静了一下,重新分析,读题,发现

浅浅的花香味﹌/ 2023年06月02日 11:56/ 0 赞/ 84 阅读