a+b problem
看看好多大佬都写了a+b,我这个蒟蒻也不能坐以待毙啊
献上线段树:
#include<iostream>
#include<algorithm>
#include<string>
#define rep(i, a, b) for(int i = a;i <= b;i++)
using namespace std;
const int maxn = 10010;
struct note{
int left;
int right;
int flag;
int sum;
}tree[maxn << 2];
int a[maxn];
void pushup(int root){
tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
return ;
}
void build(int l, int r, int root){
tree[root].left = l, tree[root].right = r;
tree[root].sum = 0, tree[root].flag = 0;
if(l == r){
tree[root].sum = a[l];
return ;
}
int mid = (l + r) >> 1;
build(l, mid, root<<1);
build(mid + 1, r, root<<1|1);
pushup(root);
}
void pushdown(int root){
if(tree[root].flag){
tree[root<<1].sum += tree[root].flag * (tree[root<<1].right - tree[root<<1].left + 1);
tree[root<<1|1].sum += tree[root].flag * (tree[root<<1|1].right - tree[root<<1|1].left + 1);
tree[root<<1].flag += tree[root].flag;
tree[root<<1|1].flag += tree[root].flag;
tree[root].flag = 0;
}
return ;
}
int qur(int l, int r, int root){
int left = tree[root].left;
int right = tree[root].right;
if(left <= l && r >= right) return tree[root].sum;
pushdown(root);
int mid = (left + right) >> 1;
int sum = 0;
if(mid >= r) sum += qur(l, r, root<<1);
else if(l > mid) sum += qur(l, r, root<<1|1);
else sum += (qur(l, mid, root<<1) + qur(mid + 1, r, root<<1|1));
return sum;
}
int main(){
int n = 2;
rep(i, 1, n) cin >> a[i];
build(1, n, 1);
cout << qur(1, n, 1) << endl;
return 0;
}