CF1208D 系统管理员 2024-04-20 10:24 20阅读 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
还没有评论,来说两句吧...