线段树是用来维护区间信息的数据结构

洛谷P3372

区间加+区间查询

#includetypedef long long LL;
const int N = 100005;
LL tree[N * 4], lazy[N * 4];void push_down(int rt, int l, int r) {if (lazy[rt]) {int mid = l + ((r - l) >> 1);tree[rt << 1] += (mid - l + 1) * lazy[rt];lazy[rt << 1] += lazy[rt];tree[rt << 1 | 1] += (r - mid) * lazy[rt];lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;}
}void push_up(int rt) {tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}void build(int rt, int l, int r) {if (l == r) {scanf("%lld", &tree[rt]);return;}int mid = l + ((r - l) >> 1);build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt);
}//当前在rt,代表区间[l,r], 给[s,t]上每一个节点+val
void update(int rt, int l, int r, int s, int t, LL val) {if (s <= l && r <= t) {tree[rt] += (r - l + 1) * val;lazy[rt] += val;return;}if (t < l || r < s)return;push_down(rt, l, r);int mid = l + ((r - l) >> 1);if (s <= mid)update(rt << 1, l, mid, s, t, val);if (mid < t)update(rt << 1 | 1, mid + 1, r, s, t, val);push_up(rt);
}//当前在rt,代表区间[l,r], 查[s,t]
LL query(int rt, int l, int r, int s, int t) {if (s <= l && r <= t) {return tree[rt];}if (t < l || r < s)return 0;push_down(rt, l, r);int mid = l + ((r - l) >> 1);LL ans = 0;if (s <= mid)ans += query(rt << 1, l, mid, s, t);if (mid < t)ans += query(rt << 1 | 1, mid + 1, r, s, t);return ans;
}int main() {int n, m, q, x, y, k;scanf("%d%d", &n, &m);build(1, 1, n);while (m--) {scanf("%d%d%d", &q, &x, &y);if (q == 1) {scanf("%d", &k);update(1, 1, n, x, y, k);}else printf("%lld\n", query(1, 1, n, x, y));}return 0;
}

洛谷P3373

区间乘+区间加+区间查询

#include
typedef long long LL;
const int N = 100005;
int sum[N << 2], mul[N << 2], lazy[N << 2], p;void push_down(int rt, int l, int r) {int left_rt = rt << 1, right_rt = rt << 1 | 1, mid = l + ((r - l) >> 1);if (mul[rt] != 1) {mul[left_rt] = 1LL * mul[left_rt] * mul[rt] % p;mul[right_rt] = 1LL * mul[right_rt] * mul[rt] % p;lazy[left_rt] = 1LL * lazy[left_rt] * mul[rt] % p;lazy[right_rt] = 1LL * lazy[right_rt] * mul[rt] % p;sum[left_rt] = 1LL * sum[left_rt] * mul[rt] % p;sum[right_rt] = 1LL * sum[right_rt] * mul[rt] % p;mul[rt] = 1;}if (lazy[rt]) {sum[left_rt] = (sum[left_rt] + 1LL * lazy[rt] * (mid - l + 1) % p) % p;sum[right_rt] = (sum[right_rt] + 1LL * lazy[rt] * (r - mid) % p) % p;lazy[left_rt] = (lazy[left_rt] + lazy[rt]) % p;lazy[right_rt] = (lazy[right_rt] + lazy[rt]) % p;lazy[rt] = 0;}
}void push_up(int rt) {sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
}void build(int rt, int l, int r) {mul[rt] = 1;if (l == r) {LL temp;scanf("%lld", &temp);sum[rt] = temp % p;return;}int mid = l + ((r - l) >> 1);build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt);
}void multiply(int rt, int l, int r, int s, int t, int val) {if (s <= l && r <= t) {sum[rt] = 1LL * sum[rt] * val % p;mul[rt] = 1LL * mul[rt] * val % p;lazy[rt] = 1LL * lazy[rt] * val % p;return;}if (t < l || r < s)return;push_down(rt, l, r);int mid = l + ((r - l) >> 1);if (s <= mid)multiply(rt << 1, l, mid, s, t, val);if (mid < t)multiply(rt << 1 | 1, mid + 1, r, s, t, val);push_up(rt);
}void add(int rt, int l, int r, int s, int t, int val) {if (s <= l && r <= t) {sum[rt] = (sum[rt] + 1LL * (r - l + 1) * val % p) % p;lazy[rt] = (lazy[rt] + val) % p;return;}if (t < l || r < s)return;push_down(rt, l, r);int mid = l + ((r - l) >> 1);if (s <= mid) add(rt << 1, l, mid, s, t, val);if (mid < t) add(rt << 1 | 1, mid + 1, r, s, t, val);push_up(rt);
}int query(int rt, int l, int r, int s, int t) {if (s <= l && r <= t) {return sum[rt];}if (t < l || r < s)return 0;push_down(rt, l, r);int mid = l + ((r - l) >> 1);int ans = 0;if (s <= mid) ans = (ans + query(rt << 1, l, mid, s, t)) % p;if (mid < t) ans = (ans + query(rt << 1 | 1, mid + 1, r, s, t)) % p;return ans;
}int main() {int n, m, q, x, y;LL k;scanf("%d%d%d", &n, &m, &p);build(1, 1, n);while (m--) {scanf("%d%d%d", &q, &x, &y);if (q == 3)printf("%d\n", query(1, 1, n, x, y));else {scanf("%lld", &k);k %= p;if (q == 1)multiply(1, 1, n, x, y, k);else add(1, 1, n, x, y, k);}}return 0;
}

poj2528

区间修改成一个值
这里数据量加大，使用离散化，但是普通的离散化会出问题
比如[1,10],[1,4],[6,10][1,10],[1,4],[6,10][1,10],[1,4],[6,10]，离散化了是[1,4],[1,2],[3,4][1,4],[1,2],[3,4][1,4],[1,2],[3,4],然而[1,2],[3,4][1,2],[3,4][1,2],[3,4]就能把[1,4][1,4][1,4]全部覆盖了
所以如果两个数字之间差大于一就补一个数字，比如1,4,6,101,4,6,101,4,6,10,就补成1,2,4,5,6,7,101,2,4,5,6,7,101,2,4,5,6,7,10，离散化完了[1,7],[1,3],[5,7][1,7],[1,3],[5,7][1,7],[1,3],[5,7]

#include
#include
using namespace std;
const int N = 10005;
bool visit[N];
int id[N << 2], left[N], right[N];
int lazy[N << 4];
void push_down(int rt) {if (lazy[rt]) {lazy[rt << 1] = lazy[rt];lazy[rt << 1 | 1] = lazy[rt];lazy[rt] = 0;}
}
void update(int rt, int l, int r, int s, int t, int val) {if (s <= l && r <= t) {lazy[rt] = val;return;}if (t < l || r < s)return;push_down(rt);int mid = l + ((r - l) >> 1);if (s <= mid)update(rt << 1, l, mid, s, t, val);if (mid < t)update(rt << 1 | 1, mid + 1, r, s, t, val);
}int ans;
void query(int rt, int l, int r) {if (lazy[rt]) {if (!visit[lazy[rt]]) {visit[lazy[rt]] = true;++ans;}return;}if (l == r)return;int mid = l + ((r - l) >> 1);query(rt << 1, l, mid);query(rt << 1 | 1, mid + 1, r);
}int main() {int T, n, cnt;scanf("%d", &T);while (T--) {cnt = ans = 0;memset(lazy, 0, sizeof(lazy));memset(visit, false, sizeof(visit));scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d%d", &left[i], &right[i]);id[cnt++] = left[i];id[cnt++] = right[i];}sort(id, id + cnt);cnt = unique(id, id + cnt) - id;for (int i = cnt - 1; i > 1; --i) {if (id[i] > id[i - 1] + 1) {id[cnt++] = id[i - 1] + 1;}}sort(id, id + cnt);for (int i = 0; i < n; ++i) {int l = lower_bound(id, id + cnt, left[i]) - id;int r = lower_bound(id, id + cnt, right[i]) - id;update(1, 1, cnt, l + 1, r + 1, i + 1);}query(1, 1, cnt);printf("%d\n", ans);}return 0;
}

poj2828

单点修改

#include
const int N = 200005;
int lazy[N << 2], p[N], v[N], res[N];void push_up(int rt) {lazy[rt] = lazy[rt << 1] + lazy[rt << 1 | 1];
}void build(int rt, int l, int r) {if (l == r) {lazy[rt] = 1;return;}int mid = l + ((r - l) >> 1);build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt);
}int query(int rt, int l, int r, int val) {if (l == r) {lazy[rt] = 0;return l;}int mid = l + ((r - l) >> 1);int ans;if (lazy[rt << 1] >= val) ans = query(rt << 1, l, mid, val);else ans = query(rt << 1 | 1, mid + 1, r, val - lazy[rt << 1]);push_up(rt);return ans;
}int main() {int n;while (~scanf("%d", &n)) {build(1, 1, n);for (int i = 0; i < n; ++i) {scanf("%d%d", &p[i], &v[i]);}for (int i = n - 1; i >= 0; --i) {res[query(1, 1, n, p[i] + 1) - 1] = v[i];}for (int i = 0; i < n; ++i) {if (i > 0)printf(" ");printf("%d", res[i]);}printf("\n");}return 0;
}

poj1151

扫描线，按照y方向排序
对x离散化

记录区间的覆盖次数

#include
#include
using namespace std;
const int N = 205;
double sum[N << 2];//总长度
int flag[N << 2];//区间覆盖次数
double x[N];
class Line {
public:double x1, x2, y;int flag;Line(const double& x1 = 0, const double& x2 = 0, const double& y = 0, const int& flag = 1) :x1(x1), x2(x2), y(y), flag(flag) {}bool operator< (const Line& o)const {return y < o.y;}
}line[N];void push_up(int rt, int l, int r) {if (flag[rt]) {//区间至少被覆盖了一次sum[rt] = x[r + 1 - 1] - x[l - 1];}else if (l == r) {//一个点sum[rt] = 0;}else {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
}void update(int rt, int l, int r, int s, int t, int val) {if (s <= l && r <= t) {flag[rt] += val;push_up(rt, l, r);return;}if (t < l || r < s)return;int mid = l + ((r - l) >> 1);if (s <= mid)update(rt << 1, l, mid, s, t, val);if (mid < t)update(rt << 1 | 1, mid + 1, r, s, t, val);push_up(rt, l, r);
}int main() {int n, t = 0;while (scanf("%d", &n), n) {memset(sum, 0, sizeof(sum));memset(flag, 0, sizeof(flag));int cnt = 0;for (int i = 0; i < n; ++i) {double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);line[cnt] = Line(x1, x2, y1, 1);x[cnt++] = x1;line[cnt] = Line(x1, x2, y2, -1);x[cnt++] = x2;}sort(line, line + cnt);sort(x, x + cnt);int k = unique(x, x + cnt) - x;double ans = 0;for (int i = 0; i + 1 < cnt; ++i) {int x1 = lower_bound(x, x + k, line[i].x1) - x + 1;int x2 = lower_bound(x, x + k, line[i].x2) - x + 1;update(1, 1, k, x1, x2 - 1, line[i].flag);ans += sum[1] * (line[i + 1].y - line[i].y);}++t;printf("Test case #%d\nTotal explored area: %.2lf\n\n", t, ans);}return 0;
}