UOJ Logo Teddy的博客

博客

新博客

2018-10-06 18:44:22 By Teddy

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;
}

评论

teddyxu
Markdown 了解一下?
  • 2018-10-11 20:35:18