1.HDU1166 敌兵布阵 单点修+区间查询+IO优化
题目要求单点修改,区间查询。按照线段树板子打下来即可。注意IO优化,关闭缓冲流后不可混用
stdio
和
iostream
,否则WA的飞起。。
以及 注意开四倍空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 50000 + 10;
int n, tree[N << 2], tt = 0;
inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }
inline void build(int rt, int l, int r){
if(l == r){
cin >> tree[rt];
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
inline void update(int rt, int l, int r, int pos, int val){
if(l == r){
tree[rt] += val;
return;
}
int mid = l + r >> 1;
if(pos <= mid) update(rt << 1, l, mid, pos, val);
else update(rt << 1 | 1, mid + 1, r, pos, val);
push_up(rt);
}
inline int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int mid = l + r >> 1, ans = 0;
if(mid >= L) ans += query(rt << 1, l, mid, L, R);
if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
return ans;
}
inline void solve(){
cin >> n;
build(1, 1, n);
cout << "Case " << ++tt << ":" << endl;
//printf("%d:\n", ++tt);
char strr[10];
while(cin >> strr){
if(!strcmp(strr, "End")) break;
else if(!strcmp(strr, "Add")){
int a, b; cin >> a >> b;
update(1, 1, n, a, b);
}
else if(!strcmp(strr, "Sub")){
int a, b; cin >> a >> b;
update(1, 1, n, a, -b);
}
else{
int a, b; cin >> a >> b;
int ans = query(1, 1, n, a, b);
cout << ans << endl;
}
}
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--) solve();
return 0;
}
2.HDU1754 I Hate It 单点修改+区间查询+维护区间最小值+IO优化
线段树模板题,维护区间最小值+单点修改无标记,一路打下来就可以,注意空间限制比较大,建树直接读数据,不要单独存。
数据量不小,考虑IO优化。
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int n, m, tree[N << 2];
inline int read() {
int f = 1, x = 0; char s = getchar();
while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); }
while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
return x *= f;
}
inline void push_up(int rt){ tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]); }
void build(int rt, int l, int r){
if(l == r){
tree[rt] = read();
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
void update(int rt, int l, int r, int pos, int val){
if(l == r){
tree[rt] = val;
return;
}
int mid = l + r >> 1;
if(pos <= mid) update(rt << 1, l, mid, pos, val);
else update(rt << 1 | 1, mid + 1, r, pos, val);
push_up(rt);
}
int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int ans = -1, mid = l + r >> 1;
if(mid >= L) ans = max(ans, query(rt << 1, l, mid, L, R));
if(mid < R) ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
return ans;
}
inline void solve(){
//for(int i = 0; i <= n; i++) cin >> a[i];
build(1, 1, n);
while(m--){
char op; scanf("%c", &op);
if(op == 'Q'){
int aa = read(), b = read();
cout << query(1, 1, n, aa, b) << endl;
}
else{
int aa = read(), b = read();
//a[aa] = b;
update(1, 1, n, aa, b);
}
}
}
signed main(){
while(~scanf("%d%d", &n, &m)) solve();
return 0;
}
3.HDU1689 Just a Hook 区间修改+Lazy标记+根节点查询
Problem Description
题目大意: 默认区间的每一个数的权值为1,不断的修改区间的某一范围,求最终的区间权值和
思路: 线段树区间更新。但是不能修改到底,数据范围约束导致彻底修改会超时,因此需要打标记,注意这里标记不存倍数、加数,而是修改之后的值。每次更新到点的时候下放即可。
关于标记这里不展开叙述,具体见OIWIKI。
Accepted Code
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int f = 1, x = 0; char s = getchar();
while(s < '0'||s > '9'){ if(s == '-') f = -1; s = getchar(); }
while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
return x *= f;
}
const int N = 1e5 + 10;
int n, q, k = 0, tree[N << 2], lazy[N << 2];
inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }
inline void push_down(int rt, int m){
if(lazy[rt]){
lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
tree[rt << 1] = lazy[rt] * (m - (m >> 1));
tree[rt << 1 | 1] = lazy[rt] * (m >> 1);
lazy[rt] = 0;
}
}
void build(int rt, int l, int r){
if(l == r){
tree[rt] = 1;
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
lazy[rt] = 0;
push_up(rt);
}
void update(int rt, int l, int r, int L, int R, int val){
if(l >= L && r <= R){
lazy[rt] = val;
tree[rt] = val * (r - l + 1);
return;
}
push_down(rt, r - l + 1);
int mid = (l + r) >> 1;
if(mid >= L) update(rt << 1, l, mid, L, R, val);
if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R, val);
push_up(rt);
}
inline void solve(){
n = read(), q = read();
build(1, 1, n);
while(q--){
int a = read(), b = read(), c = read();
update(1, 1, n, a, b, c);
}
printf("Case %d: The total value of the hook is %d.\n", ++k, tree[1]);
}
signed main(){
int t = 0; cin >> t;
while(t--) solve();
}
4.POJ3468 A Simple Problem with Integers 维护区间和+区间修改+Lazy标记+区间查询
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, q, tree[N << 2], lazy[N << 2];
inline int read() {
int f = 1, x = 0; char s = getchar();
while(s < '0'||s > '9'){ if(s =='-') f = -1; s = getchar(); }
while(s >= '0' && s <= '9'){ x = x * 10 + s - '0'; s = getchar();}
return x *= f;
}
inline void push_up(int rt){ tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]; }
inline void push_down(int rt, int m){
if(lazy[rt]){
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
tree[rt << 1] += lazy[rt] * (m - (m >> 1));
tree[rt << 1 | 1] += lazy[rt] * (m >> 1);
lazy[rt] = 0;
}
}
void build(int rt, int l, int r){
lazy[rt] = 0;
if(l == r){
tree[rt] = read();
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
void update(int rt, int l, int r, int L, int R, int val){
if(l >= L && r <= R){
lazy[rt] += val;
tree[rt] += (r - l + 1) * val;
return;
}
int mid = l + r >> 1;
push_down(rt, r - l + 1);
if(mid >= L) update(rt << 1, l, mid, L, R, val);
if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R, val);
push_up(rt);
}
int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int mid = l + r >> 1, ans = 0;
push_down(rt, r - l + 1);
if(mid >= L) ans += query(rt << 1, l, mid, L, R);
if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R);
return ans;
}
inline void solve(){
build(1, 1, n);
while(q--){
char op[2]; scanf("%s", op);
if(op[0] == 'Q'){
int a = read(), b = read();
cout << query(1, 1, n, a, b) << endl;
}
else{
int a = read(), b = read(), c = read();
update(1, 1, n, a, b, c);
}
}
}
signed main(){
while(~scanf("%d%d", &n, &q)) solve();
return 0;
}