线段树
题目链接
普通的线段树，跑了2000ms...
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <set> #include <vector> #include <string> #include <cmath> #include <queue> #define rep(i, s, e) for(int i = s; i < e; ++i) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define P pair<int, int> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; static const int N = 2020; static const int MAX_N = 5e5 + 5; static const ll Mod = 1e9 + 7; int n; int lazy[MAX_N << 2], maxv[MAX_N << 2]; ll sumv[MAX_N << 2]; void push_down(int l, int r, int rt){ int m = l + r >> 1; if(lazy[rt]){ lazy[rt << 1] = max(lazy[rt << 1], lazy[rt]); lazy[rt << 1 | 1] = max(lazy[rt << 1 | 1], lazy[rt]); maxv[rt << 1] = max(maxv[rt << 1], lazy[rt]); maxv[rt << 1 | 1] = max(maxv[rt << 1 | 1], lazy[rt]); sumv[rt << 1] = 1LL * (m - l + 1) * maxv[rt << 1]; sumv[rt << 1 | 1] = 1LL * (r - m) * maxv[rt << 1 | 1]; lazy[rt] = 0; } } void push_up(int rt){ maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); sumv[rt] = sumv[rt << 1] + sumv[rt << 1 | 1]; } void build(int l, int r, int rt){ lazy[rt] = 0; if(l == r){ sumv[rt] = maxv[rt] = l; return ; } int m = l + r >> 1; build(lson); build(rson); push_up(rt); } void update(int l, int r, int rt, int L, int R, int v){ if(l >= L && r <= R){ lazy[rt] = max(lazy[rt], v); maxv[rt] = max(maxv[rt], v); sumv[rt] = 1LL * (r - l + 1) * maxv[rt]; return ; } push_down(l, r, rt); int m = l + r >> 1; if(L <= m) update(lson, L, R, v); if(m < R) update(rson, L, R, v); push_up(rt); } ll query(int l, int r, int rt, int L, int R){ if(l >= L && r <= R) return sumv[rt]; push_down(l, r, rt); int m = l + r >> 1; ll ans = 0; if(L <= m) ans += query(lson, L, R); if(m < R) ans += query(rson, L, R); push_up(rt); return ans; } int get_pos(int l, int r, int rt, int p){ push_down(l, r, rt); if(l == r) return maxv[rt]; int m = l + r >> 1; if(p <= m) return get_pos(lson, p); return get_pos(rson, p); } int bin_search(int l, int r, int L, int R){ int p = 0; while(l <= r){ int m = l + r >> 1; if(get_pos(1, n, 1, m) >= R) r = m - 1; else{ p = m; l = m + 1; } } return p; } void solve(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //ios::sync_with_stdio(false); int q; while(scanf("%d%d", &n, &q) != EOF){ build(1, n, 1); while(q--){ int L, R; scanf("%d%d", &L, &R); int p = min(bin_search(1, n, L, R), R); if(p < L) puts("0"); else{ printf("%lld\n", 1LL * (p - L + 1) * R - query(1, n, 1, L, p)); update(1, n, 1, L, p, R); } } } } int main() { solve(); return 0; } View Code吉司机线段树，500ms，在更新的时候得出答案
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <set> #include <vector> #include <string> #include <cmath> #include <queue> #define rep(i, s, e) for(int i = s; i < e; ++i) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define P pair<int, int> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; static const int N = 2020; static const int MAX_N = 5e5 + 5; static const ll Mod = 1e9 + 7; int sumv[MAX_N << 2], maxv[MAX_N << 2]; void push_up(int rt){ maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); } void build(int l, int r, int rt){ if(l == r){ sumv[rt] = maxv[rt] = l; return ; } int m = l + r >> 1; build(lson); build(rson); push_up(rt); } ll update(int l, int r, int rt, int L, int R, int p){ if(p >= maxv[rt]) return 0; ll ans = 0; if(l == r){ ans += sumv[rt] - p; sumv[rt] = maxv[rt] = p; return ans; } int m = l + r >> 1; if(l >= L && r <= R){ ans += update(lson, L, R, p); ans += update(rson, L, R, p); push_up(rt); return ans; } if(m >= L) ans += update(lson, L, min(R, m), p); if(m < R) ans += update(rson, max(L, m + 1), R, p); push_up(rt); return ans; } void solve(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //ios::sync_with_stdio(false); int n, q; while(scanf("%d%d", &n, &q) != EOF){ build(1, n, 1); while(q--){ int L, R; scanf("%d%d", &L, &R); printf("%lld\n", update(1, n, 1, L, R, L)); } } } int main() { solve(); return 0; } View Code
转载于:https://www.cnblogs.com/xorxor/p/10946956.html
相关资源：各显卡算力对照表！