CF1208D

系统管理员 2024-04-20 10:24 76阅读 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 条评论，76人围观）

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

相关阅读

相关 CF1214D

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

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

相关 CF1208C

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

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

相关 CF1208A

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

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

相关 CF981D

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

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

相关 CF1208D

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

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

相关 cf1208B B. Uniqueness（1500）

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

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

相关【构造】CF1798 D

[Problem - D - Codeforces][] 题意： ![ee9f61a4f71440ea8d521c072445781b.png][] 思路：首先如果

超、凢脫俗/ 2024年03月23日 20:15/ 0 赞/ 78 阅读

相关【构造】CF1758 D

[Problem - D - Codeforces][] 题意： ![0f1d5284e9964d37a6889cff4db258a4.png][] 思路：如果需要构

亦凉/ 2024年03月22日 23:16/ 0 赞/ 45 阅读

相关 D. AB-string——CF1238D

https://codeforces.com/problemset/problem/1238/D 思路： 1、每个字符存在回文串的最地条件是： AA ， BB， ABA

小灰灰/ 2023年06月06日 10:35/ 0 赞/ 5 阅读

相关 CF1110D Jongmah

题意给出\\(n\\)个在\\(1\\)到\\(m\\)范围内的数\\(a\_i\\)，定义一个三元组为\\((x,x,x)\\)或者\\((x,x+1,x+2)\\)

深藏阁楼爱情的钟/ 2022年01月12日 09:29/ 0 赞/ 205 阅读