UOJ Logo shq的博客

博客

A+B Problem

2018-02-11 16:23:49 By shq

这里是Shq的第一个题解!


首先,我们来看到这道题,着明显就是个线段树啊2333 线段树:


#include<iostream>
#include<cstdio>
#include<cstring>
struct SegmentTree {
    int left,right,sum,tag;
    SegmentTree *lc,*rc;
    SegmentTree(int left,int right,SegmentTree *lc,SegmentTree *rc) : left(left), right(right), lc(lc), rc(rc), sum(0), tag(0) {}
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return l == r ? new SegmentTree(l,r,NULL,NULL) : new SegmentTree(l,r,build(l,mid),build(mid+1,r));
    }
    void cover(int delta){
        sum += (right - left + 1) * delta;
        tag += delta;
    }
    void pushDown(){
        if(tag){
            lc->cover(tag);
            rc->cover(tag);
            tag = 0;
        }
    }
    void modify(int l,int r,int delta){
        if(l > right || r < left) return;
        if(l <= left && r >= right) cover(delta);
        else{
            pushDown();
            lc->modify(l,r,delta);
            rc->modify(l,r,delta);
            sum = lc->sum + rc->sum;
        }
    }
    int query(int l,int r){
        if(l > right || r < left) return 0;
        if(l <= left && r >= right) return sum;
        else{
            pushDown();
            return lc->query(l,r) + rc->query(l,r);
        }
    }
};
int main(){
    std::ios::sync_with_stdio(false);
    int a;
    SegmentTree *segt;
    segt = SegmentTree::build(1,2);
    for(int i = 1;i <= 2;i++){
        std::cin >> a;
        segt->modify(i,i,a);
    }
    std::cout << segt->query(1,2) << std::endl;
    return 0;
}

好了,题解到这里就结束了233

评论

WrongAnswer
只查询一次,为何不把线段树换成暴力?
lyx_cjz
只有前缀加法和单点修改,为何不用树状数组
larryzhong
只查询一次,为什么不分块?
huangsi
只查询一次,为什么不用圆方树维护动态仙人掌?
oscar
只查询一次,为什么不用在线仙人球嵌套动态网络路径剖分优化的分支定界贪心剪枝启发式迭代加深人工智能搜索决策算法?
lyx_cjz
这似乎是A + B Problem而不是A+B Problem。。。
skyline
你的代码AC不了 你标题写着A+B Problem 明显指的是#77 A+B Problem 而不是 #1 A + B Problem
function5
单点查询,为什么不树状数组?..............................................................................................................................................................................................................................................................................
mathematician
只查询一次,为什么不用Top tree?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。