BZOJ 4636: 蒟蒻的数列分快，int64线段树

2019-11-08 01:15:07

字体：大中小

来源：转载

供稿：网友

Description 蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列题目描述 DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。

Input 第一行一个整数N，然后有N行，每行三个正整数a、b、k。 N<=40000 , a、b、k<=10^9 Output 一个数，数列中所有元素的和

Sample Input 4

2 5 1

9 10 4

6 8 2

4 6 3 Sample Output 16

解法1：动态开点线段树，直接在线段树上打标记,最后dfs一遍整棵线段树即可.因为区间长度比较大,所以需要动态开点.注意一些没有建立的节点也是有贡献的,要把这些加进去.

//151288 kb 788ms O(nsqrt(n))#include <bits/stdc++.h>using namespace std;const int maxn = 50000;const int inf = 1e9;long long ans;int n, a, b, k;namespace int64segmenttree{ int sum[maxn<<8], son[maxn<<8][2], root, sz; void insert(int &rt, int l, int r, int L, int R, int x){ if(L > R) return; if(!rt) rt = ++sz; if(l == L && r == R){ sum[rt] = max(sum[rt], x); return ; } int mid = (l + r) / 2; if(R <= mid) insert(son[rt][0], l, mid, L, R, x); else if(L > mid) insert(son[rt][1], mid + 1, r, L, R, x); else{ insert(son[rt][0], l, mid, L, mid, x); insert(son[rt][1], mid + 1, r, mid + 1, R, x); } } void query(int rt, int l, int r, int x){ if(!rt) return ; sum[rt] = max(sum[rt], x); if(!son[rt][0] && !son[rt][1]){ ans += 1LL * (r - l + 1) * sum[rt]; return ; } int mid = (l + r) / 2; query(son[rt][0], l, mid, sum[rt]); query(son[rt][1], mid + 1, r, sum[rt]); if(!son[rt][0]) ans += 1LL * (mid - l + 1) * sum[rt]; if(!son[rt][1]) ans += 1LL * (r - mid) * sum[rt]; }}using namespace int64segmenttree;int main(){ int n, a, b, k; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d%d", &a, &b, &k); insert(root, 1, inf, a, b - 1, k); } query(root, 1, inf, 0); PRintf("%lld/n", ans); return 0;}

解法2：离散化+分块 15072kb 2356ms

#include <bits/stdc++.h>using namespace std;const int maxn = 2e5+7;int n, m, num, belong[maxn], block, l[maxn], r[maxn], low[maxn];vector <int> V;//离散化map <int, int> H1; //存下标map <int, int> H2; //存值int A[maxn], B[maxn], K[maxn], a[maxn];void build(){ block = sqrt(n); num = n / block; if(n%block) num++; for(int i = 1; i <= num; i++) l[i] = (i - 1) * block + 1, r[i] = i * block; r[num] = n; for(int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;}void update(int L, int R, int k){ if(L > R) return; if(belong[L] == belong[R]){ for(int i = l[belong[L]]; i <= r[belong[L]]; i++) a[i] = max(a[i], low[belong[L]]); low[belong[L]] = 0; for(int i = L; i <= R; i++) a[i] = max(a[i], k); return; } for(int i = l[belong[L]]; i <= r[belong[L]]; i++) a[i] = max(a[i], low[belong[L]]); low[belong[L]] = 0; for(int i = l[belong[R]]; i <= r[belong[R]]; i++) a[i] = max(a[i], low[belong[R]]); low[belong[R]] = 0; for(int i = L; i <= r[belong[L]]; i++) a[i] = max(a[i], k); for(int i = l[belong[R]]; i <= R; i++) a[i] = max(a[i], k); for(int i = belong[L] + 1; i < belong[R]; i++) low[i] = max(low[i], k);}int main(){ scanf("%d", &m); for(int i = 1; i <= m; i++){//懒得离散化，学卿学姐直接将每个询问扔3个点进去就好 scanf("%d%d%d", &A[i], &B[i], &K[i]); V.push_back(A[i]), V.push_back(B[i]), V.push_back(B[i] - 1); } n = 3*m; build(); sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end()); for(int i = 0; i < (int) V.size(); i++){ H1[V[i]] = i + 1, H2[i + 1] = V[i]; } long long ans = 0; for(int i = 1; i <= m; i++) update(H1[A[i]], H1[B[i] - 1], K[i]); for(int i = 0; i < (int) (V.size()); i++) a[i + 1] = max(a[i + 1], low[belong[i + 1]]); for(int i = 0; i < (int) (V.size() - 1); i++) ans += (H2[i + 2] - H2[i + 1]) * a[i + 1]; printf("%lld/n", ans); return 0;}

上一篇：guava的坑

下一篇：PAT甲级C语言.1001. 害死人不偿命的(3n+1)猜想