//线段树主要是解决动态查询问题，基本操作的复杂度O(logn)
//在数组某个区间上[a,b]找最小值，数组的大小固定，但是元素可以更新
//预处理时间O(n)，查询和更新操作为O(logn),需要的额外空间为O(n)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
int n,q;
ll sum;
inline int L(int l){
return l << 1;
}
inline int R(int r){
return (r << 1) + 1;
}
inline int MID(int l,int r){
return (l + r) >> 1;
}
//线段树的节点结构
struct node{
int left;
int right;
ll val;
ll add;
}tree[maxn << 2];
ll arr[maxn << 2];
//建一棵树，从根节点开始，平分区间
void Built(int l, int r, int root){
tree[root].left = l;
tree[root].right = r;
tree[root].add = 0;
if(l == r){//叶子节点
tree[root].val = arr[l];
return;
}else{
//递归建立左右子树
int mid = MID(l,r);
Built(l,mid,L(root));
Built(mid + 1,r,R(root));
//更新root
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
void Update(int root){
//更新子树
if(tree[root].add){
tree[L(root)].add += tree[root].add;
tree[R(root)].add += tree[root].add;
tree[L(root)].val += (tree[L(root)].right - tree[L(root)].left + 1) * tree[root].add;
tree[R(root)].val += (tree[R(root)].right - tree[R(root)].left + 1) * tree[root].add;
tree[root].add = 0;
}
}
//加上v
void Add(int l,int r,ll v,int root){
if(l <= tree[root].left && r >= tree[root].right){
tree[root].add += v;
tree[root].val += v * (tree[root].right - tree[root].left + 1);
return;
}else{
//分别在左右子树上增加
Update(root);
if(tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left,tree[root].right);
if(l > mid)
Add(l,r,v,R(root));
else if(r <= mid)
Add(l,r,v,L(root));
else{
Add(l,mid,v,L(root));
Add(mid + 1,r,v,R(root));
}
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
//查询线段树
void Solve(int l,int r,int root){
if(l <= tree[root].left && r >= tree[root].right){
sum += tree[root].val;
return;
}else{
Update(root);
if(tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left,tree[root].right);
if(l > mid)
Solve(l,r,R(root));
else if(r <= mid)
Solve(l,r,L(root));
else{
Solve(l,mid,L(root));
Solve(mid + 1,r,R(root));
}
}
}
int main() {
//freopen("in", "r", stdin);
while (scanf("%d%d",&n,&q)!=EOF) {
for (int i = 1; i <= n; i++)
scanf("%lld",&arr[i]);
Built(1, n, 1);
string c;
while (q--) {
cin >> c;
if (c[0] == 'C') {
int l, f;
ll v;
scanf("%d%d%lld",&l,&f,&v);
Add(l, f, v, 1);
}
else {
int l, f;
scanf("%d%d",&l,&f);
sum = 0;
Solve(l, f, 1);
printf("%lld
",sum);
}
}
}
return 0;
}
HDU 1823
来自一位大佬的博客
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;
float meili[maxn][maxn<<2];//用二维数组表示身高和活力，结果表示缘分
int N;
double max(double a,double b){
return a > b ? a : b;
}
void build2(int l,int r,int deep,int rt){//活力方向上进行初始化
meili[deep][rt] = -1.0;//缘分为-1;查询不到最高的
if(l == r) return;
int mid = (l + r) >> 1;
build2(l,mid,deep,rt << 1);
build2(mid + 1,r,deep,rt << 1 | 1);
}
void build(int l,int r,int root){//在每一高度上，转移给活力进行初始化
build2(0,1000,root,1);
if(l == r) return;
int mid = (l+ r) >> 1;
build(l,mid,root << 1);
build(mid + 1,r,root << 1 | 1);
}
void I2(int act,float love,int l,int r,int deep,int rt){//对插入量活力上的定位，并对其相关进行更新
meili[deep][rt] = max(love,meili[deep][rt]);//根更新
if(l == r) return;
int mid = ( l + r) >> 1;
if(mid >= act) I2(act,love,l,mid,deep,rt << 1);
else I2(act,love,mid + 1,r,deep,rt << 1 | 1);
meili[deep][rt] = max(meili[deep][rt << 1],meili[deep][rt << 1 | 1]);//对根进行更新
}
void I(int h,int act,float love,int l,int r,int rt) {//身高，活泼度，缘分值,插入量位置的定位
I2(act,love,0,1000,rt,1);
if(l==r) return;
int mid = (l + r) >> 1;
if(mid >= h) I(h,act,love,l,mid,rt << 1);
else I(h,act,love,mid + 1,r, rt << 1 | 1);
}
float Q2(int act1,int act2,int l,int r,int deep,int rt){//在[act1,act2]范围，目前rt以[l,r]范围
if(act1 <= l && r <= act2) return meili[deep][rt];
int mid = (l + r) >> 1;
if(mid >= act2) return Q2(act1,act2,l,mid,deep,rt << 1);
else if(mid < act1) return Q2(act1,act2,mid + 1,r,deep,rt << 1 | 1);//不能取等号，如果相等不能递归给右子树
return max(Q2(act1,act2,l,mid,deep,rt << 1),Q2(act1,act2,mid + 1,r,deep,rt << 1 | 1));
}
float Q(int h1,int h2,int act1,int act2,int l,int r,int rt){//对高度进行定位，并将得到的根节点传给Q2的深度
if(h1 <= l && r <= h2) return Q2(act1,act2,0,1000,rt,1);
int mid = (l + r) >> 1;
if(h1 > mid) return Q(h1,h2,act1,act2,mid + 1,r,rt << 1 | 1);
else if(h2 <= mid) return Q(h1,h2,act1,act2,l,mid,rt << 1);
return max(Q(h1,h2,act1,act2,l,mid,rt << 1),Q(h1,h2,act1,act2,mid + 1,r,rt << 1 |1));
}
int main(){
while(scanf("%d",&N)!=EOF && N){
build(100,200,1);
string ch;
while(N--){
cin >> ch;
if(ch[0]=='I') {
int h;//身高
float x, y;//活泼度，缘分值
//scanf("%d%lf%lf", &h, &x, &y);
cin >> h >> x >> y;
I(h, (int) (x * 10), y, 100, 200, 1);
}else{
int h1,h2;//身高区间
float x1,x2;//活泼度区间
cin >> h1 >> h2 >> x1 >> x2;
if(h1 > h2) swap(h1,h2);
if(x1 > x2) swap(x1,x2);
float ans = Q(h1,h2,(int)(x1 * 10),(int)(x2 * 10),100,200,1);
if(ans == -1.0) puts("-1");
else printf("%.1f
",ans);
}
}
}
return 0;
}