HDU6315 Naive Operations(线段树 复杂度分析)
程序员文章站
2022-06-14 11:42:15
题意 "题目链接" Sol 这题关键是注意到题目中的$b$是个排列 那么最终的答案最多是$nlogn$(调和级数) 设$d_i$表示$i$号节点还需要加$d_i$次才能产生$1$的贡献 用线段树维护每个节点里$d_i$的最小值,每次当$d_i 1= 0$的时候往下递归即可 时间复杂度:$O(nlog ......
题意
sol
这题关键是注意到题目中的\(b\)是个排列
那么最终的答案最多是\(nlogn\)(调和级数)
设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献
用线段树维护每个节点里\(d_i\)的最小值,每次当\(d_i - 1= 0\)的时候往下递归即可
时间复杂度:\(o(nlog^2 n)\)
多组数据记得清空lazy标记啊qwq。。。。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, b[maxn]; #define ls k << 1 #define rs k << 1 | 1 struct node { int l, r, mn, sum, f; }t[maxn]; void update(int k) { t[k].mn = min(t[ls].mn, t[rs].mn); t[k].sum = t[ls].sum + t[rs].sum; } void add(int k, int val) { t[k].mn -= val; t[k].f += val; } void pushdown(int k) { if(!t[k].f) return ; add(ls, t[k].f); add(rs, t[k].f); t[k].f = 0; } void build(int k, int ll, int rr) { t[k].l = ll; t[k].r = rr; t[k].sum = 0; t[k].f = 0; if(ll == rr) {t[k].mn = b[ll]; return ;} int mid = ll + rr >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); update(k); } void dec(int k) { if(t[k].mn == 0) { if(t[k].l == t[k].r) t[k].sum++, t[k].mn = b[t[k].l]; else pushdown(k), dec(ls), dec(rs), update(k); } } void intervaladd(int k, int ll, int rr) { if(ll <= t[k].l && t[k].r <= rr) { add(k, 1); if(t[k].mn == 0) dec(k); return ; } pushdown(k); int mid = t[k].l + t[k].r >> 1; if(ll <= mid) intervaladd(ls, ll, rr); if(rr > mid) intervaladd(rs, ll, rr); update(k); } int query(int k, int ll, int rr) { if(ll <= t[k].l && t[k].r <= rr) return t[k].sum; pushdown(k); int mid = t[k].l + t[k].r >> 1; if(rr <= mid) return query(ls, ll, rr); else if(ll > mid) return query(rs, ll, rr); else return query(ls, ll, rr) + query(rs, ll, rr); } main() { while(scanf("%d %d", &n, &m) == 2) { for(int i = 1; i <= n; i++) b[i] = read(); build(1, 1, n); while(m--) { char s[6]; int l, r; scanf("%s", s + 1); l = read(), r = read(); if(s[1] == 'a') intervaladd(1, l, r); else printf("%d\n", query(1, l, r)); } } }