首页 > 代码库 > uva11992线段树
uva11992线段树
诶 !线段树 建 20个 ,随便搞搞就好了。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include <math.h>using namespace std;typedef long long LL;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 1111111;const int INF = 1000000009;int color[22][maxn << 2], Min[22][maxn << 2], Max[22][maxn << 2];int add[22][maxn << 2], sum[22][maxn << 2];int Sum; int mmax; int mmin;void down(int l, int r, int rt, int ks){ int len = r - l + 1; if (color[ks][rt] != -1){ color[ks][rt << 1] = color[ks][rt << 1 | 1] = color[ks][rt]; sum[ks][rt << 1] = color[ks][rt] * (len - (len >> 1)); sum[ks][rt << 1 | 1] = color[ks][rt] * (len >> 1); add[ks][rt << 1] = add[ks][rt << 1 | 1] = 0; Min[ks][rt << 1] = Min[ks][rt << 1 | 1] = color[ks][rt]; Max[ks][rt << 1] = Max[ks][rt << 1 | 1] = color[ks][rt]; color[ks][rt] = -1; } if (add[ks][rt]){ add[ks][rt << 1] += add[ks][rt]; add[ks][rt << 1 | 1] += add[ks][rt]; sum[ks][rt << 1] += (len - (len >> 1)) *add[ks][rt]; sum[ks][rt << 1 | 1] += (len >> 1)*add[ks][rt]; Max[ks][rt << 1] += add[ks][rt]; Max[ks][rt << 1 | 1] += add[ks][rt]; Min[ks][rt << 1] += add[ks][rt]; Min[ks][rt << 1 | 1] += add[ks][rt]; add[ks][rt] = 0; }}void up(int l, int r, int rt, int ks){ sum[ks][rt] = sum[ks][rt << 1] + sum[ks][rt << 1 | 1]; Max[ks][rt] = max(Max[ks][rt << 1], Max[ks][rt << 1 | 1]); Min[ks][rt] = min(Min[ks][rt << 1], Min[ks][rt << 1 | 1]);}void build(int l, int r, int rt, int ks){ color[ks][rt] = -1; add[ks][rt] = 0; sum[ks][rt] = Max[ks][rt] = Min[ks][rt] = 0; if (l == r)return; int mid = (l + r) >> 1; build(lson, ks); build(rson, ks);}void update(int L, int R, int l, int r, int rt, int ks, int ans, int ret){ if (L <= l&&r <= R){ if (ans == 1){ add[ks][rt] += ret; sum[ks][rt] += ret*(r - l + 1); Min[ks][rt] += ret; Max[ks][rt] += ret; //color[ks][rt]=-1; } else{ add[ks][rt] = 0; color[ks][rt] = ret; sum[ks][rt] = ret*(r - l + 1); Max[ks][rt] = ret; Min[ks][rt] = ret; } return; } down(l, r, rt, ks); int mid = (l + r) >> 1; if (L <= mid) update(L, R, lson, ks, ans, ret); if (R > mid) update(L, R, rson, ks, ans, ret); up(l, r, rt, ks);}void ask(int L, int R, int l, int r, int rt, int ks){ if (L <= l&&r <= R){ Sum += sum[ks][rt]; mmax = max(mmax, Max[ks][rt]); mmin = min(mmin, Min[ks][rt]); return; } int mid = (l + r) >> 1; down(l, r, rt, ks); if (L <= mid) ask(L, R, lson, ks); if (R > mid) ask(L, R, rson, ks);}int main(){ int n, m, q; int a, b, c, d, e; while (cin >> n >> m >> q){ for (int i = 1; i <= n; i++) build(1, m + 1, 1, i); for (int i = 0; i < q; i++){ scanf("%d%d%d%d%d", &a, &b, &c, &d, &e); if (a != 3){ int f; scanf("%d", &f); for (int j = b; j <= d; j++){ update(c, e, 1, m + 1, 1, j, a, f); } continue; } Sum = 0; mmax = -1; mmin = INF; for (int j = b; j <= d; j++){ ask(c, e, 1, m + 1, 1, j); } printf("%d %d %d\n", Sum, mmin, mmax); } } return 0;}
uva11992线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。